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

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

Класс	Алгоритм приближения
Структура данных	График
Худший случай спектакль	${ Displaystyle Theta (N ^ {2})}$
Худший случай космическая сложность	${ Displaystyle Theta (N)}$

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

Алгоритм

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

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

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

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

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

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

Заметки

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

• Г. Гутин, А. Ео, А. Зверович, Коммивояжер не должен быть жадным: доминирующий анализ эвристик жадного типа для TSP. Дискретная прикладная математика 117 (2002), 81–86.
• Дж. Банг-Дженсен, Г. Гутин и А. Йео, Когда жадный алгоритм терпит неудачу. Дискретная оптимизация 1 (2004), 121–127.
• Дж. Бендалл и Ф. Марго, Жадное сопротивление комбинаторных задач, Дискретная оптимизация 3 (2006), 288–298.