Учебный класс | Алгоритм приближения |
---|---|
Структура данных | График |
Наихудшая производительность | |
Сложность пространства в наихудшем случае |
Ближайший алгоритм соседа был один из первых алгоритмов , используемых для решения задачи коммивояжера примерно. В этой задаче продавец начинает со случайного города и неоднократно посещает ближайший город, пока все не будут посещены. Алгоритм быстро дает короткий тур, но обычно не самый оптимальный.
Алгоритм [ править ]
Это шаги алгоритма:
- Инициализировать все вершины как непосещенные.
- Выберите произвольную вершину, установите ее как текущую вершину u . Отметить U как посещенные.
- Найдите кратчайшее ребро, соединяющее текущую вершину u и непосещенную вершину v .
- Установите v как текущую вершину u . Отметить v как посещенное.
- Если все вершины в домене посещены, то завершаем работу. В противном случае перейдите к шагу 3.
Последовательность посещенных вершин является выходом алгоритма.
Алгоритм ближайшего соседа легко реализовать и выполняется быстро, но иногда он может пропускать более короткие маршруты, которые легко заметить с человеческой проницательностью из-за его «жадной» природы. В качестве общего ориентира, если последние несколько этапов тура сопоставимы по продолжительности с первыми этапами, тогда тур является разумным; если их намного больше, то, вероятно, существуют гораздо лучшие туры. Другая проверка - использовать такой алгоритм, как алгоритм нижней границы , чтобы оценить, достаточно ли хорош этот тур.
В худшем случае алгоритм дает обход, который намного длиннее оптимального. Чтобы быть точным, для каждой константы r существует такой пример задачи коммивояжера, что длина маршрута, вычисленная алгоритмом ближайшего соседа, больше, чем r, умноженная на длину оптимального маршрута. Более того, для каждого количества городов существует присвоение расстояний между городами, для которых эвристика ближайшего соседа дает уникальный наихудший возможный маршрут. (Если алгоритм применяется к каждой вершине в качестве начальной, лучший найденный путь будет лучше, чем по крайней мере N / 2-1 других обходов, где N - количество вершин.) [1]
Алгоритм ближайшего соседа может вообще не найти подходящего маршрута, даже если он существует.
Заметки [ править ]
- ^ Г. Гутин, А. Ео и А. Зверович, 2002
Ссылки [ править ]
- Г. Гутин, А. Йео и А. Зверович, Экспоненциальные окрестности и анализ доминирования для TSP, в Проблема коммивояжера и ее вариации, Г. Гутин и А. П. Пуннен (ред.), Kluwer (2002) и Springer (2007) .
- Г. Гутин, А. Ео и А. Зверович, Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP . Дискретная прикладная математика 117 (2002), 81–86.
- Дж. Банг-Дженсен, Г. Гутин и А. Йео, Когда жадный алгоритм дает сбой . Дискретная оптимизация 1 (2004), 121–127.
- Дж. Бендалл, Ф. Марго, Сопротивление комбинаторных задач жадного типа , Дискретная оптимизация 3 (2006), 288–298.