Interested Article - Алгоритм ближайшего соседа в задаче коммивояжёра

Алгоритм ближайшего соседа — один из простейших эвристических алгоритмов решения задачи коммивояжёра . Относится к категории «жадных» алгоритмов .

Формулируется следующим образом:

Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма (lower bound algorithm).

Для любого количества городов, большего трёх, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.

Алгоритм

Шаги алгоритма:

  1. Поставить все вершины как не посещённые.
  2. Выбрать начальную вершину v и пометить её, как посещённую.
  3. Выбрать наиближайшую не посещённую смежную вершину u к вершине v .
  4. Поставить u как текущую вершину и пометить как посещённую.
  5. Если все вершины посещены, то завершить алгоритм. Иначе, вернуться к шагу 3.

На выходе будем иметь последовательность вершин, предположительно оптимального решения.

Примечания

  1. G. Gutin, A. Yeo, A. Zverovich. от 29 июля 2007 на Wayback Machine // Discrete Applied Mathematics 117 (2002)

Ссылки

Источник —

Same as Алгоритм ближайшего соседа в задаче коммивояжёра