10.1. Алгоритмы для нахождения минимального пути к единственной целевой точке

10.1.0. Общая часть

Мы изложим четыре основных алгоритма поиска на графе. В каждом из них прежде всего выделяется начальный узел находится множество его преемников а затем упорядочивается множество в соответствии с оценкой стоимости решающего пути для каждого . Нильсон использует следующий общий способ описания работы алгоритмов. Когда узлу впервые приписывается величина он помещается в упорядоченное множество, называемое ОТКРЫТ. Узлы удаляются из списка ОТКРЫТ в порядке возрастания После удаления из списка ОТКРЫТ узел помещается в множество, называемое ЗАКРЫТ (будем называть это закрытием узла Когда некоторый узел закрыт, величины связанные с каждым узлом в ОТКРЫТ, могут вычисляться заново. Поэтому несколько усложним наши обозначения, понимая как „величину , вычисленную при условии, что узел закрыт". Аналогично определим Предполагается, что для каждого узла из списков ОТКРЫТ или ЗАКРЫТ указывается узел, который был закрыт в тот момент, когда определялось его текущее значение

10.1.1. Алгоритм перебора в ширину

1. Поместить все узлы из в список ОТКРЫТ в произвольном порядке.

2. Если список ОТКРЫТ пуст, то неудача — решетя нет.

3. Закрыть первый узел из ОТКРЫТ. Пусть это будет узел Если то успех — решение дается последовательностью (в обратном порядке): узел узел, закрытый в тот момент, когда был помещгн в ОТКРЫТ; узел, закрытый в тот момент, когда предыдущий узел был помещен в ОТКРЫТ, и т. д. до тех пор, пот не будет достигнут некоторый узел Если перейти к шагу 4.

4. Найти . Поместить все узлы множества и в ОТКРЫТ в произвольном порядке, исключая те, которые следуют за любым узлом, уже находящимся в ОТКРЫТ. Зафиксировать, что узел использовался для записи каждого из новых узлов в ОТКРЫТ.

5. Перейти к шагу 2.

Пример. Рассмотрим задачу нахождения маршрута из Сиэтла в Рено (рис. 10.1). Получаем последовательность записей в списках ОТКРЫТ и ЗАКРЫТ.

Решение достигается на следующем шаге. Маршрут, в обратном порядке, таков: Рено — Спокан — Сиэтл.

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

10.1.2. Алгоритм равных цен

Эта модификация предыдущего алгоритма призвана минимизировать стоимость окончательного решения.

1. Поместить все узлы в список ОТКРЫТ в произвольном порядке. Пусть

2. Если список ОТКРЫТ пуст, на выход подается сигнал о невозможности решения.

3. Пусть — такой узел в списке ОТКРЫТ, что значение минимально. Если то решение дается обратным путем к некоторому узлу как и ранее. В противном случае поместить в список ЗАКРЫТ и перейти к шагу 4.

4. Для всех вычислить Это оценка минимального пути из некоторого узла в через вычисленная после записи в список ЗАКРЫТ. Если узелп не содержится в ОТКРЫТ, поместить его туда и положить Если содержится в ОТКРЫТ и то присвоить текущее значение,

равное и зафиксировать, что узел был помещен в ОТКРЫТ через . В противном случае не менять значения и содержимое списка ОТКРЫТ. Заметим, что эта процедура может изменять оценку по мере помещения новых узлов в список ЗАКРЫТ.

5. Перейти к шагу 2.

Пример. Этот алгоритм можно продемонстрировать, решая задачу нахождения пути от Сан-Франциско до Лос-Анджелеса и используя, как и раньше, карту на рис. 10.1 (опять напомним, что расстояния на карте выбраны произвольно, лишь для иллюстрации алгоритма). На этот раз списки ОТКРЫТ и ЗАКРЫТ снабжены также соответствующими оценками расстояний и связями с другими узлами.

(см. скан)

Решение достигается на следующем шаге и представляет собой маршрут Сан-Франциско — Сан-Бернардино — Лос-Анджелес.

Этот алгоритм лучше предыдущего, поскольку узлы помещаются в список ЗАКРЫТ в порядке убывания их расстояний от начального узла. Вследствие этого любой узел в списке ОТКРЫТ дальше от начального, чем любой узел из списка ЗАКРЫТ. Если можно допустить, что при закрытии узла становится известным истинное расстояние от него до ближайшего узла из то решение, которое дает метод равных цен, во всех случаях минимально. Это подтверждается следующей теоремой.

Теорема о равных ценах. Метод равных цен дает при закрытии узла кратчайший путь от , таким образом, для всех .

Доказательство. Докажем сначала две леммы.

Лемма 1. Если любой узел помещен в список OTKPЫT, когда узел закрыт, или уже находится в списке OTKPЫT, и если для любого узла закрытого до то

Доказательство леммы. Правая часть равенства в (6) есть не что иное, как определение корректировки Так как то лемма доказана.

Следствие. Пусть — преемник некоторого узла , когда узел закрыт, Кроме того, пусть Тогда

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

Неравенство (7) справедливо для всех потомков узла

Лемма 2. Если узел закрыт после то т. е. порядок, в котором закрываются узлы, соответствует возрастанию их оценок в момент закрытия узла.

Доказательство леммы. Пусть множество узлов в списке ОТКРЫТ в момент закрытия узла и пусть любой узел из Тогда должно быть

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

лемма доказана.

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

и, следовательно, значение не изменилось бы. Это значит, что при закрытии узла оценка его расстояния до какого-то узла из была минимальной. Таким образом, обратный путь от его предка из был кратчайшим, и потому

Теорема доказана.