Лекция: СТРАТЕГИЯ ПОИСКА В ГЛУБИНУ

Логический вывод по существу сводится к достижению цели G на основе последовательного процесса доказательства истинности (или ложности) частичных целей через механизм унификации и возвратов.

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

Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче, а решение задачи сводится к поиску пути на графе. Вершины графа соответствуют проблемным ситуациям, дуги – разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией и некоторой указанной заранее конечной ситуацией, называемой целевой вершиной. В терминах пространства ситуаций основными стратегиями поиска являются стратегии поиска в глубину и в ширину. Рассмотрим сначала первую из них (рис. 1.1).

В терминах логического программирования вычисление цели j приводит к полному обходу в глубину конкретного дерева поиска цели j, в котором выбирается самая левая цель. По существу здесь декларирован некоторый порядок извлечения целей. Действительно, говоря о поиске в глубину, мы имеем в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. В соответствии с этим порядком запоминается одна альтернативная вершина и связанные с ней потомки. Сама система Prolog при выполнении цели проверяет цели по принципа поиска в глубину.

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

Рассмотрим программу поиска на графе в глубину на языке Prolog:

after – состояние дуг исходного графа

but – целевые вершины.