Задача о поиске кратчайшего пути

На рис. 6 показан пример поведения конкурирующих процессов. Дана карта городов с расстояниями между ними, задача состоит в том, чтобы найти кратчайший маршрут из стартового города s в целевой город t. В качестве оценки стоимости остатка маршрута из города X до цели мы будем использовать расстояние по прямой расст(X, t) от X до t. Таким образом,

f(X) = g(X) + h(X) = g(X) + расст(X, t)

Мы можем считать, что в данном примере процесс поиска с предпочтением состоит из двух процессов. Каждый процесс прокладывает свой путь — один из двух альтернативных путей: Процесс 1 проходит через а, Процесс 2 — через е. Вначале Процесс 1 более активен, поскольку значение f вдоль выбранного им пути меньше, чем вдоль второго пути. Когда Процесс 1 достигает города с, а Процесс 2 все еще находится в е, ситуация меняется:

f(c) = g(c) + h(c) = 6 + 4 = 10

f(e) = g(e) + h(e) = 2 + 7 = 9

Поскольку f(e) < f(c), Процесс 2 переходит к f, а Процесс 1 ждет. Однако

f(f) = 7 + 4 = 11

f(c) = 10

f(c) < f(f)

Поэтому Процесс 2 останавливается, а Процессу 1 дается разрешение продолжать движение, но только до d, так как f(d) = 12 > 11. Происходит активация процесса 2, после чего он, уже не прерываясь, доходит до цели t.

Рисунок 6. Поиск кратчайшего маршрута из s в t

(а) Карта со связями между городами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t.

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

1.4.3. А-алгоритм и А*-алгоритм

Опр. 1. Информированный поиск с оценочной функцией f(u)=g(u)+h(u), где h(u) — эвристика вершины u, называется А-алгорит­мом.

Опр. 2. А-алгоритм с эвристической функцией h(u)≤h*(u) для любой u называется A*-алгоритмом.

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

Концевая вершина каждого пути оценивается согласно функции f, и для продолжения выбирается путь, оканчивающийся вершиной с минимальной f-оценкой.

Покажем, что поиск в ширину есть частный случай A-алгоритма. Поиск в ширину — это неинформированный поиск, следовательно, h(u)≡0 для любой u. Смысл g(u) — расстояние, пройденное от s до u. Следовательно, g(u) — это уровень или количество ребер от вершины s до вершины u. Как известно, поиск в ширину всегда находит минимальный путь, так как просматривает большое количество вершин пространства состояний. Это наводит на мысль, что использование «малых» эвристик будет давать минимальные решения с просмотром большого количества вершин, в то время как использование «больших» эвристик будет очень сильно фокусировать поиск без всяких гарантий, что поиск «не пройдет мимо» целевой вершины.

Дадим точные определения.

Опр. 3. Пусть A₁ и A₂ — два варианта A*-алгоритма, использование эвристические функции h₁ и h₂. Назовем A₂ более информированным, чем A₁, если для всех нецелевых вершин h₂(u)≥h₁(u) и для всех целевых h₁(u)=h₂(u)≡0.

Теорема 1.

Если A₁ и A₂ — варианты A* — алгоритма, и A₂ более информирован, чем A₁, то A₂ просмотрит вершин не больше чем A₁.

Теорема 2.

Если A1 является A* — алгоритмом с h(u)≤h*(u) для всех вершин, то A1 находит минимальное решение.

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

Пусть у нас имеется A-алгоритм с эвристикой h(u)>>g(u). Пусть на каком-то шаге имеются два пути-кандидата, оканчивающимися вершинами u₁ и u₂, причем вершина u₁ более «продвинута» в направлении целевой вершины (рис. 7):

Рисунок 7. Фокусировка дерева поиска с помощью «большой эвристики»

Так как u₁ лежит дальше от начала поиска, то g(u₁)>g(u₂). Соответственно, оценка расстояния от вершины u₁ до t меньше соответствующей оценки для u₂: h(u₁)<h(u₂).

Так как h — «большая» эвристика, то она сильно убывает в направлении целевой вершины, т.е.:

h(u₂)-h(u₁)>>g(u₁)-g(u₂)

Таким образом получаем, что

g(u₂)+h(u₂)>>g(u₁)+h(u₁),

то есть более «продвинутые» пути всегда будут иметь меньшие f-оценки, и А-алгоритм никогда не вернется к пути, оканчивающемуся вершиной, близкой к началу поиска.