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

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

Класс	Алгоритм аппроксимации
Структура данных	График
Худший случай производительность	$\Theta \; (N\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (N\; ^\; \{2\})\}$
Худший -case сложность пространства	$\Theta \; (N)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (N)\}$

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

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

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

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

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

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

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

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

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