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

Question

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

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

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

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

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 - Вы улучшили свое решение. ;-)

Алгоритмы Hill climbing действительно просты в реализации, но имеют несколько проблем с локальными максимумами! [Более подходящий подход, основанный на той же идее, - simulated annealing.]

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

Другим хорошим метаэвристического для решения ПБО является ant colony optimization

Answer 2

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

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

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

Затем алгоритм:

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

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

Answer 3

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

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

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

Answer 4

Я не уверен, почему вы хотели бы использовать алгоритм пониженного, так как алгоритм Djikstra является многочленом сложности O (| E | + | V | войти | 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