Назад | Содержание| Вперёд Глава 13 СВЕДЕНИЕ ЗАДАЧ ...

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

Глава 13

СВЕДЕНИЕ ЗАДАЧ К ПОДЗАДАЧАМ.

И / ИЛИ-ГРАФЫ

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

13. 1. Представление задач в виде И /ИЛИ-графов

В главах 11 и 12, говоря о решении задач, мысконцентрировали свое внимание на пространствесостояний как средстве представления этих задач.В соответствии с таким подходом решение задачсводилось к поиску пути в графе пространствасостояний. Однако для некоторых категорий задачпредставление в форме И / ИЛИ-графаявляется более естественным. Такоепредставление основано на разбиениизадач на подзадачи. Разбиение на подзадачидает преимущества в том случае, когда подзадачивзаимно независимы, а, следовательно, и решать ихможно независимо друг от друга.

Проиллюстрируем это на примере. Рассмотримзадачу отыскания на карте дорог маршрута междудвумя заданными городами, как показано на рис. 13.1.Не будем пока учитывать длину путей. Разумеется,эту задачу можно сформулировать как поиск пути впро-

Рис. 13. 4. (а) Пример И / ИЛИ-графа: d, g и h - целевые вершины;

a - исходная задача. (b) и (с) Два решающих дерева, стоимости

которых равны 9 и 8 соответственно.Здесь стоимость решающего

дерева определена как сумма стоимостей всехвходящих в него дуг.

Иллюстрацией к этому определению может служитьрис. 13.4. Используя стоимости, мы можемформулировать критерии оптимальности решения.Например, можно определить стоимость решающегографа как сумму стоимостей всех входящих в негодуг. Тогда, поскольку обычно мы заинтересованы вминимизации стоимости, мы отдадим предпочтениерешающему графу, изображенному на рис. 13.4(с).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оглавление