Лекция: ЛЕКЦИЯ 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. с помощью ориентированного графа.
| |||||||
Рис. 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.
| |||
Рис. 10.14. Граф И/ИЛИ для выражения q٨r→p.
Кривая, соединяющая дуги на рис. 10.14, означает, что для доказательства pдолжны быть истинными обе предпосылки: qи r. Если предпосылки соединены оператором ИЛИ, на графе они представляются узлами ИЛИ (оr). Дуги, ведущие от узлов ИЛИк следующей вершине, не соединяются кривой (рис. 10.15). Это указывает на то, что истина любой из предпосылок является достаточным условием для истинности заключения.
|
| |||||
Рис. 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,что предлагается сделать самостоятельно.