Из Википедии, бесплатной энциклопедии
  (Перенаправлено из И-или дерева )
Перейти к навигации Перейти к поиску

И-или дерево представляет собой графическое представление редукции проблем (или целей) к конъюнкции и дизъюнкции из подзадач (или подцелей).

Пример [ править ]

И / или дерево:

Andortree.png

представляет собой пространство поиска для решения задачи P с использованием методов приведения к цели:

P, если Q и R
P, если S
Q, если T
Q, если U

Определения [ править ]

Для исходной задачи P 0 и набора методов решения проблемы вида:

P, если P 1 и… и P n

связанное и / или дерево представляет собой набор помеченных узлов, таких что:

  1. Корень дерева - это узел, помеченный P 0 .
  2. Для каждого узла N, помеченного проблемой или подзадачей P, и для каждого метода формы P, если P 1 и… и P n , существует набор дочерних узлов N 1 ,…, N n узла N, такой как что каждый узел N i помечен P i . Узлы соединены дугой, чтобы отличить их от потомков N, которые могут быть связаны с другими методами.

Узел N, помеченный проблемой P, является успешным узлом, если существует метод формы P, если ничего нет (т. Е. P является «фактом»). Узел является узлом отказа, если нет метода решения P.

Если все дочерние узлы узла N, соединенные одной и той же дугой, являются узлами успеха, то узел N также является узлом успеха. В противном случае узел является отказавшим узлом.

Стратегии поиска [ править ]

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

Связь с логическим программированием [ править ]

Методы, используемые для генерации и / или деревьев, представляют собой программы логики высказываний (без переменных). В случае логических программ, содержащих переменные, решения совместных подзадач должны быть совместимыми. С учетом этого усложнения стратегии последовательного и параллельного поиска и / или деревьев обеспечивают вычислительную модель для выполнения логических программ.

Отношения с играми для двух игроков [ править ]

И – или деревья могут также использоваться для представления пространств поиска для игр для двух человек. Корневой узел такого дерева представляет проблему победы одного из игроков в игре, начиная с начального состояния игры. Для данного узла N, обозначенного проблемой P игрока, выигрывающего игру в конкретном состоянии игры, существует единственный набор соединенных дочерних узлов, соответствующий всем ответным ходам оппонентов. Для каждого из этих дочерних узлов существует набор несвязанных дочерних узлов, соответствующих всем защитным ходам игрока.

Для решения деревьев игр с помощью семейства алгоритмов поиска числа доказательств , деревья игр должны быть отображены в и / или деревья. МАКС-узлы (т.е. максимальное движение игрока) представлены как узлы ИЛИ, МИН-узлы сопоставляются узлам И. Отображение возможно, когда поиск выполняется только с бинарной целью, обычно это «игрок, который переместится, побеждает в игре».

Библиография [ править ]