Программирование на языке Пролог для искусственного интеллекта




Эвристические оценки и алгоритм поиска - часть 3


Пусть   В1  -  вершина-предшественник вершины  В  в дереве поиска, причем стоимость дуги, ведущей из  В1  в  В,   равна  с( В1, В),  тогда положим

        F( B) = с( В1, В) + H( В)

Пусть  В1  -  родительская вершина вершины  В,  а  В1,  В2,   ... - ее дочерние вершины, тогда, в соответствии с определениями  F  и  H, имеем

        F( B) = c( B1, B) + minF( Bi),

            если  В   -  ИЛИ-вершина

                                          i

       

fig13_9_2.gif (491 bytes)

               если  В    -  И-вершина

Хотя стартовая вершина  А  и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить  h  равным 0 для всех вершин И / ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна  F( A).

На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого  F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И / ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины - стартовой вершины  а, далее дерево постепенно "растет" до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд "мгновенных снимков", сделанных в процессе роста дерева поиска.


Содержание  Назад  Вперед