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