Трассировка процесса поиска с предпочтением в и / или-графе ( h = 0) при решении задачи рис. 13.4.

  Трассировка процесса поиска с предпочтением в
И / ИЛИ-графе ( h = 0) при решении задачи рис. 13.4.

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

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

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

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

• Размер:
  
  (1)    дерево состоит из одной вершины (листа)
          или
  (2)    оно имеет корень и (непустые) поддеревья.
  
• Решающий статус:
  
  (1)    обнаружено, что дерево соответствует
          решению задачи( т. е. является решающим
          деревом) или
  (2)    оно все еще решающее дерево-кандидат.

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

line();

Содержание раздела