Алгоритм ближайшего соседа — один из простейших эвристических алгоритмов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.
Формулируется следующим образом:
Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.
Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lower bound algorithm).
Для любого количества городов, большего трёх, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.[1]
Энциклопедичный YouTube
-
1/3Просмотров:1 8314 1181 253
-
12.2 Метод ближайших соседей - KNN
-
#7. Алгоритм Прима (ближайшего соседа) | Алгоритмы на Python
-
Задача коммивояжёра. Метод отжига
Субтитры
Алгоритм
Шаги алгоритма:
- Поставить все вершины как не посещённые.
- Выбрать начальную вершину v и пометить её, как посещённую.
- Выбрать наиближайшую не посещённую смежную вершину u к вершине v.
- Поставить u как текущую вершину и пометить как посещённую.
- Если все вершины посещены, то завершить алгоритм. Иначе, вернуться к шагу 3.
На выходе будем иметь последовательность вершин, предположительно оптимального решения.
Примечания
Ссылки
Обычно почти сразу, изредка в течении часа.