вершинам на рис. 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. Представление дерева поиска.
