ЛЕКЦИЯ 29

10.4. Поиск на графах «И-ИЛИ»

В разделе 10.1 при определении графа пространства состояний былоотмечено, что его вершины должны отличаться друг от друга, поскольку каждый узел представляет некоторое состояние процесса решения. В качестве формального языка для описания этих различий и отображения узлов графа в пространство состояний можно использовать исчисление преди­катов. Более того, для создания дуг и описания связей между состояниями можно использо­вать правила вывода. Тогда методами поиска могут быть решены некоторые проблемы ис­числения предикатов. Например, таким образом можно определить, является ли некоторое конкретное выражение логическим следствием данного набора утверждений.

Корректность и полнота правил вывода исчисления предикатов обеспечивает кор­ректность подобных заключений. Возможность получить формальное доказательство целостности решения задачи с помощью алгоритма решения самой задачи является уни­кальным преимуществом многих методов искусственного интеллекта.

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

В качестве первого примера рассмотрим задачу построения графа на основе набора

логических отношений из исчисления высказываний. Пусть р, q, r,v,t,s,u- высказывания. Рассмотрим следующие истинные утверждения.

q→p, r→p, v→q, s→r, t→r, s→u, s, t.

Из этого набора утверждений на основе правила вывода может быть выведена истинность следующих высказываний: p, r, и u. Истинность других высказываний, в частности, v и q, не могут быть выведены таким способом. Действительно, они логически не следуют из этих утверждений. Отношения между начальными утверждениями и выведенными из них описаны на рис. 10.13. с помощью ориентированного графа.

	v

Рис. 10.13. Граф пространства состояний набора импликаций в исчислении высказываний

Дуги на рис.10.13.соответствуют логическим импликациям (→). Утверждения, кото­рые считаются истинными (s и t),соответствуют исходным данным задачи. Логические следствия из данного набора утверждений соответствуют достижимым узлам. Путь на

графе отражает последовательность применения правила вывода. Например, путь

[ s, r, p ] соответствует такому ряду логических выводов.

Из s и s → r следует r. Из r г и r → p следует p.

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

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

В выражениях вида q ٨ r → p для обеспечения истинности p должны быть истинны как q, так и r. В выражениях вида q ٧ r → p истинность q или r достаточна для доказательства того, что p - истина. Поскольку импликации (→), содержащие дизъюнктивные (٧) предпосылки, могут быть записаны как пары отдельных импликаций, это выражение часто записывается в виде q → p, r → p. Чтобы представить различные отношения графи­чески, на графах И/ИЛИ различают узлы И (aпd) и ИЛИ (оr). Если предпосылки имплика­ций связаны оператором ٨, они называются И -узлами графа, а дуги, ведущие от этих узлов, соединяются кривой. На рис. 10.14. в виде графа И/ИЛИ представлено выражение q ٨ r → p.

		r

Рис. 10.14. Граф И/ИЛИ для выражения q ٨ r → p.

Кривая, соединяющая дуги на рис. 10.14, означает, что для доказательства p должны быть истинными обе предпосылки: q и r. Если предпосылки соединены оператором ИЛИ, на графе они представляются узлами ИЛИ (оr). Дуги, ведущие от узлов ИЛИ к следую­щей вершине, не соединяются кривой (рис. 10.15). Это указывает на то, что истина любой из предпосылок является достаточным условием для истинности заключения.

	q			r

Рис. 10.15. Граф И/ИЛИ для выражения q ٧ r → p.

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

a

b

c

a ٨ b→d

a ٨ c→e

b ٨ d→f

f→g

a ٨ e→h

Этот набор утверждений определяет граф И/ИЛИ, показанный на рис. 10.16.

Рисунок 10.16. Граф И/ИЛИ для набора выражений a, b, c, a ٨ b→d, a ٨ c→e, b ٨ d→f,

f→g, a ٨ e→h

С помощью поиска на этом графе можно получить (вывести) ответы на следую­щие вопросы.

1. Истинно ли h?

2. Является ли h истиной, если b больше не истина?

3. Каков кратчайший путь, доказывающий, что некоторое высказывание Х истинно?

4. Показать, что высказывание р (не используемое в наборе исходных высказываний)

есть ложь. Что это значит? Что необходимо знать для получения этого заключения?

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

В примере, показанном на рис. 10.16, для определения истинности h с помощью стратегии поиска от цели (goal-directed strategy) сначала доказывается истинность а и е. Истинность а очевидна, а выражение е истинно, если истинны и с и а, что да­но по условию задачи. Решающее устройство прослеживает все дуги, ведущие к ис­тинным предложениям. Затем истинные значения передаются и -узлу для доказа­тельства истинности h.

Стратегия определения истинности h на основе данных предполагает обработку ис­ходных данных ( с, а и b ) и добавление новых высказываний к набору известных фактов в соответствии со связями графа И/ИЛИ. Сначала к набору фактов добавляется высказы­вание е или d. Это дает возможность вывести новые факты. Процесс продолжается до тех пор, пока не будет проверена желаемая цель h.

Поиск на графе И/ИЛИ можно рассматривать следующим образом. Операторы ٨ (и ­ узлы графа) означают декомпозицию задачи. Иными словами, задача разбивается на подзадачи, которые должны быть решены для решения исходной проблемы. Оператор ٧

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

Рисунок 10.17. Фрагмент дорожной карты.

Эту задачу, безусловно, можно сформулировать как поиск кратчайшего пути в пространстве состояний. Соответствующее пространство состояний может выглядеть полностью аналогично этой карте: узлы в пространстве состояний соответствуют городам, дуги­ - прямым соединениям между городами, а стоимости дуг – расстояниям между городами. Но может рассматриваться и другое представление этой задачи, основанное на её естественной декомпозиции при её решении.

На карте, приведенной на рис. 10.17, имеется также река. Предположим, что эту реку можно пересечь только с помощью двух мостов, один из которых находится в городе f, а другой - в городе g. Очевидно, что необходимо включить в разрабатываемый маршрут один из мостов, поэтому маршрут должен пройти или через f, или через g. Таким образом, имеются два описанных ниже ocновных варианта.

Чтобы найти путь от а до z необходимо выполнить одно из следующих действий:

· Найти путь от а до z через f.

· Найти путь от а до z через g.

Теперь каждый из этих двух вариантов можно разложить на следующие подзадачи:

1. Чтобы найти путь от а до z через f необходимо выполнить следующее:

1.1. Найти путь от а до f.

1.2. Найти путь от f до z.

2. Чтобы найти путь от а до z через g необходимо выполнить следующее:

2.1. Найти путь от а до g.

2.2. Найти путь от g до z.

В конечном итоге имеются два основных варианта решения первоначальной задачи: проложить маршрут через f или проложить его через g. Кроме того, каждый из этих вариантов задачи можно разделить на две подзадачи (соответственно, 1.1 и 1.2. или 2.1. и 2.2.)Здесь важно то, что (в обоих вариантах) каждая из подзадач может быть решена независимо от другой. Такую декомпозицию можно представить в виде графа И/ИЛИ, представленного на рис. 10.18.

Рис. 10.18. Декомпозиция задачи поиска маршрута представленная в виде графа И/ИЛИ, полностью определённая для подзадачи поиска пути от а до z через f.

В представлении в виде пространства состояний решение задачи поиска пути от а до z через f сводилось к поиску пути в пространстве состояний. Каково же решение в представлении в виде графа И/ИЛИ? Безусловно, что любое решение должно включить все подзадачи любого узла И. Поэтому теперь решение является не путем, а деревом. Такое дерево решения, Т, определяется следующим образом.

. Первоначальная проблема, Р, является корневым узлом дерева Т.

. Если Р - узел ИЛИ, то в дереве Т находится один и только один из его преем­ников (по графу И/ИЛИ ) вместе с его собственным деревом решения.

. Если Р - узел И, то в дереве Т находятся все его преемники (по графу И/ИЛИ ) наряду с их деревьями решения.

На основании сказанного выше можно сделать следующие выводы:

· Представление задачи в виде графа И/ИЛИ основано на принципе декомпозиции задачи на подзадачи.

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

· Вершина из которой исходят связи ИЛИ, представляет собой вершину ИЛИ. Для решения задачи, обозначенной вершиной ИЛИ, достаточно решить одну из задач её преемников.

· Вершина из которой исходят связи И, представляет собой вершину И. Для решения задачи, обозначенной вершиной И, необходимо решить все задачи её преемников.

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

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

. Любое решение представлено в виде графа решения, который является подграфом графа И/ИЛИ.

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

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

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

На рис. 10.19. представлено одно из возможных решений в виде дерева Т, т.к. решается задача определения кратчайшего пути, то необходимо определить стоимость этого решения, она вычисляется путём суммирования стоимостей дуг, входящих в это решение и равно 11.

рис. 10.19. Возможное решение задачи рисунка 10.17 в виде графа И/ИЛИ.

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

. Вершины ИЛИ имеют форму: «путь от X до Z», а это означает, что нужно кратчайший маршрут от Х до Z.

. Вершины И имеют такую форму: «путь от X до Z через У», а это означает - найти кратчайший маршрут от Х до Z, при условии, что этот маршрут должен пройти через У.

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

. Стоимость каждой целевой вершины «путь от X до Z» представляет собой указанное дорожное расстояние между X и Z.

. Стоимости всех других (нетерминальных) вершин равны О.

Стоимость графа решения представляет собой сумму стоимостей всех дуг, входящих в терминальную вершину. Для задачи, показанной на рис. 10.17, начальной вершиной является «путь от А до Z». На рис. 10.19 показано дерево решения со стоимостью 11. Это дерево соответствует маршруту (a,b,d,f,h,z), который можно реконструировать из дерева решения, посетив все листья в этом дереве в последовательности слева направо.

Можно найти более короткий маршрут от А до Z, что предлагается сделать самостоятельно.