Prolog

        F( B) = c( B1, B) + minF( B_i),             если  В   -  ИЛИ-вершина

                                          ⁱ

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

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

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

После распространения поиска из первоначального дерева (снимок  А)   получается дерево  В.  Вершина  а   - это ИЛИ-вершина, поэтому мы имеем два решающих дерева-кандидата:  b  и  с.   Поскольку  F( b) = 1 < 3 = F( c), для продолжения поиска выбирается альтернатива  b.   Насколько далеко может зайти процесс роста поддерева  b? Этот процесс может продолжаться до тех пор, пока не произойдет одно из двух событий:

    (1)        F-оценка вершины  b  станет больше, чем  F-оценка ее конкурента  с,  или

    (2)        обнаружится, что найдено решающее дерево.

В связи с этим, начиная просмотр поддерева-кандидата  b,  мы устанавливаем верхнюю границу для  F( b):   F( b) <= 3 = F( c). Сначала порождаются преемники  d  и  е  вершины  b    (снимок  С), после чего  F-оценка   b  возрастает до 3. Так как это значение не превосходит верхнюю границу, рост дерева-кандидата с корнем в  b   продолжается. Вершина  d   оказывается целевой вершиной, а после распространения поиска из вершины  е   на один шаг получаем дерево, показанное на снимке  D.  В этот момент выясняется, что  F( b)  =  9   >  3,  и рост дерева  b

Рис. 13. 10.  Трассировка процесса поиска с предпочтением в

И / ИЛИ-графе ( h = 0) при решении задачи рис. 13.4.

прекращается. В результате процесс поиска не успевает "осознать", что  h  -   это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу  с.  Поскольку в этот момент F( b) = 9, устанавливается верхняя граница для  F( c),  равная 9. Дерево-кандидат с корнем  с   наращивается (с учетом установленного ограничения) до тех пор, пока не возникает ситуация, показанная на снимке  Е.  Теперь процесс поиска обнаруживает, что найдено решающее дерево (включающее в себя целевые вершины  h  и  g),  на чем поиск заканчивается. Заметьте, что в качестве результата процесс поиска выдает наиболее дешевое из двух возможных решающих деревьев, а именно решающее дерево рис. 13.4(с).

13. 4. 2.    Программа поиска

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

Существует несколько случаев, как показано на рис. 13.11. Различные формы представления поискового дерева возникают как комбинации следующих возможных вариантов, относящихся к размеру дерева и к его "решающему статусу".

Размер:

(1)    дерево состоит из одной вершины (листа)

        или

(2)    оно имеет корень и (непустые) поддеревья.

Решающий статус:

(1)    обнаружено, что дерево соответствует

        решению задачи( т. е. является решающим

        деревом) или

(2)    оно все еще решающее дерево-кандидат.

Основной функтор, используемый для представления дерева, указывает, какая из комбинаций этих воз-

Рис. 13. 11.  Представление дерева поиска.

можностей имеется в виду. Это может быть одна из следующих комбинаций:

        лист     решлист    дер    решдер

Далее, в представление дерева входят все или некоторые из следующих объектов:

корневая вершина дерева,

F-оценка дерева,

стоимость  С  дуги И / ИЛИ-графа, ведущей в корень дерева,

список поддеревьев,

отношение (И или ИЛИ) между поддеревьями.

Список поддеревьев всегда упорядочен по возрастанию  F-оценок. Поддеревья, являющиеся решающими деревьями, помещаются в конец списка.

Обратимся теперь к программе рис. 13.12. Отношение самого высокого уровня - это

        и_или( Верш, РешДер)