Алгоритм ближайшего соседа - Nearest neighbour algorithm

Алгоритм ближайшего соседа
КлассАлгоритм приближения
Структура данныхГрафик
Худший случай спектакль
Худший случай космическая сложность

В алгоритм ближайшего соседа был одним из первых алгоритмы используется для решения задача коммивояжера примерно. В этой задаче продавец начинает со случайного города и неоднократно посещает ближайший город, пока не будут посещены все. Алгоритм быстро дает короткий тур, но обычно не самый оптимальный.

Алгоритм

Это шаги алгоритма:

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

Последовательность посещенных вершин является выходом алгоритма.

Алгоритм ближайшего соседа легко реализовать и выполняется быстро, но иногда он может пропускать более короткие маршруты, которые легко заметить с помощью человеческого понимания, из-за его «жадной» природы. В качестве общего ориентира, если последние несколько этапов тура сопоставимы по продолжительности с первыми этапами, тогда тур является разумным; если их намного больше, то, вероятно, существуют гораздо лучшие туры. Другая проверка - использовать такой алгоритм, как нижняя граница алгоритм, чтобы оценить, достаточно ли хорош этот тур.

В худшем случае алгоритм дает обход, который намного длиннее оптимального. Если быть точным, для каждой константы р существует такой пример задачи коммивояжера, что длина тура, вычисленная алгоритмом ближайшего соседа, больше, чем р раз больше длины оптимального тура. Более того, для каждого количества городов есть присвоение расстояний между городами, для которых эвристика ближайшего соседа дает уникальный наихудший возможный тур. (Если алгоритм применяется к каждой вершине в качестве начальной, лучший найденный путь будет лучше, чем по крайней мере N / 2-1 других обходов, где N - количество вершин)[1]

Алгоритм ближайшего соседа может вообще не найти подходящего маршрута, даже если он существует.

Заметки

  1. ^ Г. Гутин, А. Ео, А. Зверович, 2002 г.

использованная литература