Поиск на графах И/ИЛИ

При рассмотрении разложимых систем продукции было введено понятие графов И/ИЛИ. В таком графе вершины — это состояния БД или их части, которые получаются двумя способами: применением правила либо разложением БД на составляющие. Это именно граф, а необязательно только дерево поиска. Одна и та же вершина d может появиться и в результате разложения d_x, и применением правила к d₂. Графы И/ИЛИ находят широкое применении в ИИ. Алгоритмы поиска, подобные А*, специализируются и уточняются для применения в случае графов И/ИЛИ. Кроме того, для отдельных частных случаев гиперграфов известны еще более эффективные алгоритмы. Здесь изложены общие сведения, а конкретные примеры применения приведены в п. 2.3.3, 3.5.1 и параграфе 4.3.

Граф И/ИЛИ

Уточним определения.

Граф И/ИЛИ — это гиперграф, т. е. пара, состоящая из множества узлов {d} и множества ?-дуг, причем ?-дуга — это пара d —" (d_v …, d_k), где d — начальный узел /г-дуги, a {d_{, …, d_k} — множество концевых узлов^[1].

С точки зрения этого определения обычный ориентированный граф — это гиперграф, в котором каждая дуга — это 1-дуга. Так же, как и в обычном орграфе, в гиперграфе можно определить понятие пути (гиперпути).

Гиперпуть в гиперграфе — это последовательность множеств узлов, {, …, S_n>, причем для каждого узла d е S_i9 1 < i < п — 1, существует ровно одна &-дуга d —> (d_{,…, d_k) такая, что V 1 5_/+1).

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

Среди всевозможных гиперпутей нам интересны те, которые начинаются в исходном состоянии БД и заканчиваются в терминальных состояниях.

Граф решения G (d₀, T) — это гиперпуть из б/₀ во множество терминальных узлов Т.

Можно дать эквивалентное рекурсивное определение графа решения G (d_0y Т).

• 1. Если <7₀ € Г, то G —
• 2. Если с7₀ g 7'и из <7₀ исходит Л'-дуi a с/₀ —> (й^,<7_/;), причем существуют графы решения G_x, G₂,…, G_k для узлов d_{, d₂,…, d_k, то G = d₀-^(d_l,…, d_k) u cj cj G₂ cj ••• су G_k.

Стоимость (вес) графа решения (т.е. длина пути в гиперграфе) определяется с помощью рекурсивного определения:

Таким образом, одна и та же /г-дуга при подсчете длины может учитываться много раз.

Рассмотрим пример (рис. 3.11). Положим, что узлы 5 и 6 терминальные, а узел 0 начальный. Можем утверждать, что здесь имеются два графа решения (на рисунке они обведены).

Рис. 3.11. Гиперграфы решения и &-дуги:

—I + (2 + (2) + (2″ = 7:—с (*-дуга) = к——-2 + (2 + (1 + 2″ = 7.

Если считать, что длина &-дуги равна k, то данный граф имеет только два гиперпути решения.

Первый граф решения обведен сплошной линией, его длина составляет 1 + (2 + (2) + (2)) = 7 как сумма дуг: 0 —> 1 + 1 —> (2, 4) + 2 —" (5, 6) + 4 —> ->(5,6).

Второй граф решения обведен пунктирной линией, его длина составляет 2 + (2 + (1 + 2)) = 7 как сумма дуг: 1 —> (2, 3) + 2 —> (5, 6) + 3 —" 2 + + 2 -> (5, 6):

• • длина первого графа решения = 1 + (2 + (2) + (2)) = 7,
• • длина второго графа решения = 2 + (2 + (1+ 2)) = 7,

так как согласно рекурсивному определению некоторые /г-дуги могут учитываться несколько раз.

• [1] Вообще говоря, в ориентированном гиперграфе начальные узлы также могут образовывать множество.