Монотонный поиск в ширину

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

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

Вернемся к задаче поиска пути из Иванова в Москву. На рис. 4.2,б схематически показана карта участка дорог, ведущих из Иванова в Москву. Каждая из дорог, ведущих из одного пункта в другой, снабжена числовой оценкой действия. На рис. 4.2, а показана последовательность монотонного поиска в ширину. Каждая из вершин помечена ценой пути, ведущего в эту вершину.

Рис. 4. 2. Задача нахождения маршрута из Иванова в Москву:

а – порядок монотонного поиска в ширину. Каждая вершина помечена ценой пути, ведущим в нее из начальной вершины (снаружи вершины) и номером ее получения в процессе поиска (внутри вершины). На последнем шаге монотонного поиска в ширину найдена целевая вершина с ценой пути, равным 10;

б – пространство состояний, иллюстрирующее цену действий, соответствующую участкам пути между городами.

Дата добавления: 2014-12-27