Алгоритмы скалолазания и однопарные кратчайшие пути

Question

У меня немного странный вопрос. Может кто-нибудь сказать мне, где можно найти информацию, или дать мне небольшое введение в использование алгоритмов кратчайшего пути, которые используют подход восхождения на гору? Я понимаю основы обоих, но я не могу соединить их вместе. В Википедии есть интересная часть о том, как решить проблему коммивояжера с помощью альпинизма, но не дается более подробное объяснение того, как именно это сделать.

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

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

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

Answer 1

Вы можете просто случайно обменять два города.

Ваш первый путь: A B C D E F A длиной 200

Теперь вы меняете его, меняя C и D: A B D C E F A длиной 350 - Хуже!

Следующий шаг: A B C D F E A: длина 150 - Вы улучшили свое решение. ; -)

Алгоритмы восхождения на холм действительно просты в реализации, но имеют несколько проблем с локальными максимумами! [Лучшим подходом, основанным на той же идее, является имитация отжига .]

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

Другая хорошая метаэвристика для решения TSP - Оптимизация муравьиных колоний

Answer 2

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

Решение проблемы коммивояжера в виде генетического алгоритма , для которого нам нужно:

• Представление решения в виде порядка посещенных городов, например, [Нью-Йорк, Чикаго, Денвер, Солт-Лейк-Сити, Сан-Франциско]
• Фитнес-функция в качестве пройденного расстояния
• Выбор лучших результатов осуществляется путем случайного выбора элементов в зависимости от их пригодности, чем выше пригодность, тем выше вероятность того, что решение выбрано для выживания
• Мутация будет переключаться на города в списке, как [A, B, C, D] становится [A, C, B, D]
• Пересечение двух возможных решений [B, A, C, D] и [A, B, D, C] приводит к [B, A, D, C], т.е. разрезание обоих списков в середина и использовать начало одного из родителей и конец другого родителя, чтобы сформировать ребенка

Алгоритм тогда:

• инициализация исходного набора раствора
• расчет пригодности каждого решения
• до желаемой максимальной физической формы или до тех пор, пока не произойдет никаких изменений
  • подбор лучших решений
  • скрещивание и мутация
  • Фитнес-расчет каждого решения

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

Answer 3

Я не уверен, почему вы хотите использовать алгоритм восхождения на холм, поскольку алгоритм Джикстры имеет полиномиальную сложность O (| E | + | V | log | V |) с использованием очередей Фибоначчи: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Если вы ищете эвристический подход к проблеме с одним путем, то вы можете использовать A *: http://en.wikipedia.org/wiki/A*_search_algorithm

но повышение эффективности зависит от допустимой эвристической оценки расстояния до цели. http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 4

Для подъема на холм TSP у вас должен быть стартовый маршрут. Конечно, выбор «умного» маршрута не повредит.

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

Очевидно, что с TSP вы, скорее всего, достигнете локального максимума. Но можно получить приличные результаты.