Программирование на языке ПРОЛОГ для искуственного интеллекта




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


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

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

  • Размер:

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

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

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

line();

fig13_11.gif (7263 bytes)

line();

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

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

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

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

  • корневая вершина дерева,
  • F-оценка дерева,
  • стоимость  С  дуги И / ИЛИ-графа, ведущей в корень дерева,
  • список поддеревьев,
  • отношение (И или ИЛИ) между поддеревьями.

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

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

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

где Верш - стартовая вершина. Программа строит решающее дерево (если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции  h,  которую использует алгоритм.


Содержание  Назад  Вперед