В комментах писали, что есть более хорошие алгоритмы для поиска решений в задаче коммивояжёра.
Наверно есть, но мне было интересно разобраться с муравьиным алгоритмом, что я и сделал.
Также писали про "алгоритм ближайщего соседа" или "жадный алгоритм", когда выбор ориентируется только на близость следующего города.
Собственно, "муравьиный алгоритм" - это улучшение "алгоритма ближайщего соседа", в который добавили вероятностный выбор на основе не только близости следующего города, но ранее найденых хороших маршрутов.
Вот что там сказано:
"Для любого количества городов, большего трех, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение"
Вначале я поиграл также с жадным алгоритмом, но потом удалил этот материал из конечного ролика.
Что бы упростить задачу для алгоритма, я убрал требования возвращения в исходный город.
Это слабое место для алгоритма, он строит маршрут без учёта, что нужно будет возвращаться.
Никакой стратегии, прёт как танк :)
Но даже в этом случае, мои маршруты получаются короче.
Вот скриншоты, слева - маршруты алгоритма, справа - мои маршруты.
foo52ru ТехноШаман
В комментах писали, что есть более хорошие алгоритмы для поиска решений в задаче коммивояжёра.
Наверно есть, но мне было интересно разобраться с муравьиным алгоритмом, что я и сделал.
Также писали про "алгоритм ближайщего соседа" или "жадный алгоритм", когда выбор ориентируется только на близость следующего города.
Собственно, "муравьиный алгоритм" - это улучшение "алгоритма ближайщего соседа", в который добавили вероятностный выбор на основе не только близости следующего города, но ранее найденых хороших маршрутов.
В википедии даже статья есть про алгоритм ближайщего соседа для задачи коммивояжёра.
ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%…
Вот что там сказано:
"Для любого количества городов, большего трех, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение"
Вначале я поиграл также с жадным алгоритмом, но потом удалил этот материал из конечного ролика.
Что бы упростить задачу для алгоритма, я убрал требования возвращения в исходный город.
Это слабое место для алгоритма, он строит маршрут без учёта, что нужно будет возвращаться.
Никакой стратегии, прёт как танк :)
Но даже в этом случае, мои маршруты получаются короче.
Вот скриншоты, слева - маршруты алгоритма, справа - мои маршруты.
4 years ago (edited) | [YT] | 287