Программирование на языке Пролог для искусственного интеллекта
в дереве поиска, причем стоимость
Пусть В1 - вершина-предшественник вершины В в дереве поиска, причем стоимость дуги, ведущей из В1 в В, равна с( В1, В), тогда положим
F( B) = с( В1, В) + H( В)
Пусть В1 - родительская вершина вершины В, а В1, В2, ... - ее дочерние вершины, тогда, в соответствии с определениями F и H, имеем
F( B) = c( B1, B) + minF( Bi),
если В - ИЛИ-вершина
i
если В - И-вершина
Хотя стартовая вершина А и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить h равным 0 для всех вершин И / ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна F( A).
На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И / ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины - стартовой вершины а, далее дерево постепенно "растет" до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд "мгновенных снимков", сделанных в процессе роста дерева поиска.
