Спасибо. Ты делаешь то, на что у меня нет времени, а результат глянуть интересно. Сам люблю позаниматься подобными экспериментами.
4 years ago | 12
@vladimirviktorovichivanov7577
Мне кажется, можно сделать полиномальный алгоритм решения этой задачи методом триангуляции. Метод заключается в том, что для каждой точки ищется область в которой она является ближайшей. Таким образом у каждой точки будут границы с некоторым количеством соседей. Есть довольно эффективный способ нахождения соседей: триангуляция Делоне. Предлагается теорема, что оптимальный путь всегда проходит между соседними точками, и тогда число комбинаций возможных путей из экспоненциального превращается в полиномальное, так что становится возможным вычислить оптимальный путь перебором уже для довольно приличного числа точек.
4 years ago | 3
Суть жадных методов в скорости, лучше оценка, это не длина маршрута, а соотношение длины маршрута к времени работы или разницы между точным и приближённым к времени. Если вершин достаточно много, например 10000, то я сомневаюсь, что время работы муравьиного алгоритма будет приемлемо. Можно ещё взять алгоритм Литла, с разной глубиной разбития на множества, и если интересно сравнивать качество, то брать метод ветвей и границ (может не сойтись, в наихудшем случае равен полному перебору) и с ним сравнивать
4 years ago (edited) | 6
ООО, по идее для идеальных результатов, нужен алгоритм, мыслящий наперёд, то есть, человек видеть все точки, и анализирует расстояние от каждой до каждой, то есть если в первом случае мы возьмём наибольшее расстояние из возможных, то при последующих шагах, мы сэкономим расстояние.
4 years ago | 2
Пару лет назад столкнулся с этой задачей и решал её посредством муравьиного алгоритма. На полном графе всё было замечательно. Но как только 50% дорог исчезало и граф становился неполным - всё сразу приходило в безумие и отвагу. Даже среднего качества пути не простраивались. Так и не придумал тогда, как решить муравьями неполный граф
2 years ago | 0
Мне нравится что ты делаешь необычные и интересные штуки с компьютером, как будто играешь с ним, не слушай тех кто говорит что "существует и более оптимальный алгоритм" - они скучные :)
4 years ago | 0
Может муравьям ввести штрафы за использование готового пути? Муравьи подбирают некий путь и этот путь сохраняется. Со значением длины. Теперь любой муравей, который снова пойдет по этому пути при завершении прохода вместо добавления феромонов будет их отнимать со всех отрезков. Отдельные отрезки они все еще могут проходить, но и тут можно вводить ограничения на совпадения с найденным маршрутом. Муравьи найдут другой путь, т.к. первый обнулится. После N итераций этот путь запоминается и теперь за этот путь муравьи получают штрафы. Учитывать симметричность и замкнутость пути, т.е. он может начинаться в любой точке и идти в любом направлении (для круга). Будет ли после первой тысячи таких записей увеличиваться длина пути из-за нахождения всех наиболее оптимальных? Для графика: номер и длина пути. Первым найден путь такой-то длины. Пятым -- другая длина.
4 years ago | 0
Спасибо что объясняешь такие вещи простыми словами, для таких дегроидов как я)
4 years ago | 0
Такой вопрос где применять такой алгоритм? Т.е. в логистике все же нужен самый оптимальный маршрут, а не приближенные к нему. А время как раз не так критично.
4 years ago (edited) | 0
foo52ru ТехноШаман
В комментах писали, что есть более хорошие алгоритмы для поиска решений в задаче коммивояжёра.
Наверно есть, но мне было интересно разобраться с муравьиным алгоритмом, что я и сделал.
Также писали про "алгоритм ближайщего соседа" или "жадный алгоритм", когда выбор ориентируется только на близость следующего города.
Собственно, "муравьиный алгоритм" - это улучшение "алгоритма ближайщего соседа", в который добавили вероятностный выбор на основе не только близости следующего города, но ранее найденых хороших маршрутов.
В википедии даже статья есть про алгоритм ближайщего соседа для задачи коммивояжёра.
ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%…
Вот что там сказано:
"Для любого количества городов, большего трех, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение"
Вначале я поиграл также с жадным алгоритмом, но потом удалил этот материал из конечного ролика.
Что бы упростить задачу для алгоритма, я убрал требования возвращения в исходный город.
Это слабое место для алгоритма, он строит маршрут без учёта, что нужно будет возвращаться.
Никакой стратегии, прёт как танк :)
Но даже в этом случае, мои маршруты получаются короче.
Вот скриншоты, слева - маршруты алгоритма, справа - мои маршруты.
4 years ago (edited) | [YT] | 287