Программа поиска
13. 4. 2. Программа поиска
Программа, в которой реализованы идеи предыдущего раздела, показана на Рисунок 13.12. Прежде, чем мы перейдем к объяснению отдельных деталей этой программы, давайте рассмотрим тот способ представления дерева поиска, который в ней используется.
Существует несколько случаев, как показано на Рисунок 13.11. Различные формы представления поискового дерева возникают как комбинации следующих возможных вариантов, относящихся к размеру дерева и к его "решающему статусу".
- Размер:
(1) дерево состоит из одной вершины (листа)
или
(2) оно имеет корень и (непустые) поддеревья.
- Решающий статус:
(1) обнаружено, что дерево соответствует
решению задачи( т. е. является решающим
деревом) или
(2) оно все еще решающее дерево-кандидат.
Основной функтор, используемый для представления дерева, указывает, какая из комбинаций этих воз-
line();
