Prolog

стоимостях дуг. Иногда более естественным окажется приписывать стоимость не дугам, а вершинам, или же и тем, и другим одновременно.

Подведем итоги:

И / ИЛИ-представление основано на философии сведения задач к подзадачам.

Вершины И / ИЛИ-графа соответствуют задачам; связи между вершинами - отношениям между задачами.

Вершина, из которой выходят ИЛИ-связи, называется ИЛИ-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить одну из ее задач-преемников.

Вершина, из которой выходят И-связи, называ ется И-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить все ее задачи-преемники.

При заданном И / ИЛИ-графе конкретная задача специфицируется заданием

        стартовой вершины и

        целевого условия для распознавания

        целевых вершин.

Целевые вершины (или 'терминальные вершины') соответствуют тривиальным (или 'примитивным') задачам.

Решение представляется в виде решающего графа - подграфа всего И / ИЛИ-графа.

Представление задач в форме пространства состояний можно рассматривать как специальный частный случай И / ИЛИ-представления, когда все вершины И / ИЛИ-графа являются ИЛИ-вершинами.

И / ИЛИ-представление имеет преимущество в том случае, когда вершинами, находящимися в отношении И, представлены подзадачи, которые можно решать независимо друг от друга. Критерий независимости можно несколько ослабить, а именно потребовать, чтобы существовал такой порядок решения И-задач, при котором решение более 'ранних' подзадач не разрушалось бы при решении более 'поздних' под задач.

Дугам или вершинам, или и тем, и другим можно приписать стоимости с целью получить возможность сформулировать критерий оптимальности решения.

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

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

13. 2.    Примеры И/ИЛИ-представления задач

13. 2. 1.    И / ИЛИ-представление задачи поиска маршрута

Для задачи отыскания кратчайшего маршрута (рис. 13.1) И / ИЛИ-граф вместе с функцией стоимости можно определить следующим образом:

ИЛИ-вершины представляются в форме X-Z, что означает: найти кратчайший путь из  X  в  Z.

И-вершины имеют вид

        X-Z  через  Y

что означает: найти кратчайший путь из  X  в   Z,  проходящий через  Y.

Вершина X-Z является целевой вершиной (примитивной задачей), если на карте существует непосредственная связь между  X  и  Z.

Стоимость каждой целевой вершины X-Z равна расстоянию, которое необходимо  преодолеть по дороге, соединяющей X с Z.

Стоимость всех остальных (нетерминальных) вершин равна 0.

Стоимость решающего графа равна сумме стоимостей всех его вершин (в нашем случае это просто сумма стоимостей всех терминальных вершин). В задаче рис. 13.1 стартовая вершина - это   а-z.  На рис.

Рис. 13. 5.  Решающее дерево минимальной стоимости для задачи

поиска маршрута рис. 13.1, сформулированной в терминах И / ИЛИ-