Алгоритм Рабина

Увеличение быстродействия в алгоритме Рабина достигается за счёт преимущественного распространения волны в направлении ячейки-цели.

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

Алгоритм Рабина, который реализует метод ветвей и границ, позволяет также, как и алгоритм Ли, находить глобальный оптимум целевой функции (L_min).

Пусть требуется найти путь min длины между ячейками А и В.

Рассмотрим некоторую ячейку С_i, включаемую в очередной фронт волны. Значение волновой функции С_i, приписываемое С_i ячейки фронта, определяется из выражения:

,

где L(I,A) – длина пройденного волной пути из ячейки А в ячейку С_i, а

- расстояние между С_i,В в ортогональной метрике.

Нетрудно увидеть, что является нижней оценкой пути из С_i в В, полученной в предположении отсутствия препятствий на этом пути.

Отсюда, выражение (1) в целом представляет собой нижнюю оценку пути из А в В, проходящую в ячейку С_i.

Согласно методу ветвей и границ, оптимальное решение следует искать в подмножестве решений, имеющем наилучшую оценку. В соответствии с этим в сформированном очередном фронте волны выделяют подмножество ячеек с min оценкой 1 и распространение волны на следующем шаге осуществляется из ячеек этого подмножества.

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

Последовательность просмотра соседних ячеек та же, что и в алгоритме Ли (например:,,,) - построение пути осуществляется с использованием путевых координат.

Эффективность алгоритма Рабина по сравнению с алгоритмом Ли показана на рис.3, на котором для каждой ячейки ДПР указано значение весовой функции P_i. Цифрами в правых углах ячеек обозначена последовательность рассмотрения ячеек на этапе распространения волны.

рисунок

Поиск по сайту: