Алгоритм поиска на графе И/ИЛИ

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

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

Алгоритм эвристического поиска на графе И/ИЛИ заключается в следующем.

Пусть граф ациклический, имеется оценочная функция Fи h удовлетворяет условию монотонности (монотонному ограничению):

и условию состоятельности (т.е. является нижней оценкой точного решения):

Процедуры поиска на графах И/ИЛИ определяются следующим образом.

Алгоритм 3.4. Основная процедура поиска на графе И/ИЛИ

proc GS и/или (dO, R, Т).

G := dO {частичный граф решения}.

s (dO) := dO е Т {отметка узла}.

F (dO):= h (dO).

while —is (dO) do d := Select (G).

if d = nil then return (fail) end if Open (d, G) end while end proc.

Здесь s (d): bool — отметка узла, обозначающая, найден ли для этого узла гиперпуть, ведущий в терминальные вершины. Если s (d)=true, гиперпуть найден, то узел называется разрешенным (от английского слова solved).

Процедура Select на основе построенного графа поиска рассматривает частичный граф решения и выбирает для раскрытия на этом графе нераскрытый узел минимальной стоимости.

Алгоритм 3.5. Процедура выбора узла для раскрытия

proc Select (G).

О := {dO} for de О do for q = (d-Kil, dk) e Q (d) do.

if x (d—>dl, dk) then {дуга отмечена}.

• 0:=0 — {d} {удаляем начальный}
• 0:=0 + ({dl, dk}T) {добавляем концевые}

end if end for end for m: = cc d' := nil for d e 0 do if F (d).

end if end for return (d') end proc.

Здесь 0 — концевые вершины частичного графа решения, Q (d) — множество дуг узла d, х (q) — отметка дуги q.

В этой процедуре фактически каждый раз заново прогоняется фронт решения от d₀ к концевым вершинам по отмеченным &-дугам.

Процедура Open значительно сложнее. Она раскрывает выбранную вершину, пересчитывает оценки вершин, отмечает k-дут и отмечает разрешенные вершины, т. е. вершины, для которых найден гиперпуть в терминальные вершины. Эти изменения могут затронуть весь граф.

Алгоритм 3.6. Процедура Open

proc Open (d, G){раскрытие вершины} for r e R do if r. p (d) then.

G i⁼ G + (d—> dl, dk) for i from 1 to k do.

if di {S G then F (di):=h (di) end if s (di) := di e T end for.

end if end for.

{Пересчет оценок и отметок}.

С := {d} while С 0 do.

{выбор вершин для пересчета} for d' е С do.

if P (d') n С = 0 then d:=d' end if end for С := C — {d} m: = oc.

for g=(d-> dl,…, dk) e Q (d) do w' :=w (q) + S F (di).

if w' < m then.

x (g (d)) := false.

x (g) := true s (d):=&s (di) m: = w'.

end if end for.

if s (d) v F (d)*m then F (d): =m C := C + U (d).

end if end while end proc.

Здесь используются следующие обозначения: Q (d) — множество исходящих из d дуг (в G); Р (d) — множество потомков d в G; q (d) — отмеченная дуга из d; х (q) — отметка дуги; U (d) — множество предков d в G вдоль отмеченных дуг; s (d) — отметка узла, означающая что из него построен гиперпуть до цели.

Повторим еще раз основные выводы по этим трем процедурам. Процедура GS и/или попеременно вызывает процедуры Select и Open пока не окажется так, что никакой узел не найден для раскрытия (результат fail), либо исходный узел d₀ не окажется разрешенным. Процедура Select строит фронт текущего частичного графа решения по отмеченным дугам и выбирает узел с наименьшей оценкой в этом фронте. Процедура Open сначала раскрывает выбранную вершину, а затем пересчитывает оценки узлов, отмечает дуги и вершины. При этом данная процедура может переоценить весь граф. В этих процедурах мы считаем, что понятие правила обобщает как применение правила, так и расщепление БД с помощью k-jxyvw.