Алгоритм ближайшего соседа
| Сорт | Алгоритм аппроксимации |
|---|---|
| Структура данных | График |
| Худшая производительность | |
| Наихудшая пространственная сложность | |
| Оптимальный | Нет |
Алгоритм ближайшего соседа был одним из первых алгоритмов, использованных для приближенного решения задачи коммивояжера . В этой задаче продавец начинает со случайного города и неоднократно посещает ближайший город, пока не будут посещены все. Алгоритм быстро дает короткий тур, но обычно не оптимальный.
Алгоритм [ править ]
Вот шаги алгоритма:
- Инициализируйте все вершины как непосещенные.
- Выберите произвольную вершину, установите ее как текущую вершину 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.