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

Эта статья посвящена аппроксимационному алгоритму решения задачи коммивояжера . Чтобы узнать о других значениях, см. « Ближайший сосед» .

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

Сорт	Алгоритм аппроксимации
Структура данных	График
Худшая производительность	$\Theta (N^{2})$
Наихудшая пространственная сложность	$\Theta (N)$
Оптимальный	Нет

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

Алгоритм

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

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

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

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

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

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

Ссылки

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