Давайте начнем с идеи более высокого порядка: мы не можем эффективно найти лучшее решение для проблемы по двум причинам:
- Мы не можем закодировать все реальные жизненные соображения в нашей целиfunction
- Даже если бы мы могли, проблема будет очень сложной в вычислительном отношении.
Ответ на оба эти вопроса в статье заключается в создании ряда «достаточно хороших» решенийиспользование некоторых базовых целевых функций (расстояние), чтобы люди могли выбирать среди них некоторые другие соображения.Чтобы это работало, мы хотим, чтобы решения были достаточно близки к лучшим и достаточно универсальными.Они эффективно используют «вероятностный жадный алгоритм » (я только что придумал этот термин, не уверенный, существует ли для этого официальное название).
Идея состоит в том, что мы хотим построить каждый набор лучших дорог, добавляя по одной дороге за раз.В истинно жадном алгоритме на каждом шаге мы добавили бы самую короткую дорогу из всех дорог, соединяющих некоторые новые блоки.К сожалению, таким образом, мы можем получить только одно решение, а жадные алгоритмы часто работают не так хорошо в такой сложной задаче (иногда вам нужно выбрать более длинный путь, чтобы выиграть, добавив в конце множество более коротких путей).Вместо этого они делают следующее:
Создайте набор потенциально хороших кандидатов на следующую дорогу: для каждого еще не связанного блока создайте несколько самых коротких дорог.
Получить случайную дорогу из этого набора кандидатов.Но все же ясно, что не все кандидаты одинаковы, и мы хотим отдать предпочтение более коротким (то есть выбирать их чаще).Чтобы учесть это, давайте добавим вес для каждой дороги, который обратно пропорционален ее длине, а затем возьмем средневзвешенное значение.На практике они используют вес Wi = Li^(-n) для n = 8.Это довольно жесткий фильтр, выбирающий более короткие пути (если дорога длиннее на 20%, вероятность того, что ее выберут в 4 раза меньше).Таким образом, вероятность того, что данная дорога будет выбрана, составляет
Pi = Wi/Sum(Wj) = Li^(-n)/Sum[Lj^(-n)]
Когда дорога добавлена, у вас возникла новая проблема меньшего размера, поэтому вы можете повторить все шаги снова.