13.1 Введение

Деревом И/ИЛИ является дерево, которое имеет два типа узлов (И-узел и ИЛИ-узел). Впервые понятие И/ИЛИ дерева поя-вилось в работе Слайгла . ИЛИ-узел означает, что задача может быть решена, если решать задачу 1, или задачу 2,или задачу 3 (рис.12.1)

И-узел означает, что задачу можно разложить на подзадачи и, решив все задачи из этого списка, получить решение исходной задачи (рис.12.2).

Вариантом дерева И /ИЛИ назовем поддерево, которое получается из за- данного путем отсечения выходных дуг кроме одной, у всех ИЛИ-узлов. Вариант в терминах решения задачи задает вариант решения задачи.

Деревья И/ИЛИ получили распространение в исследованиях по искусствен- ному интеллекту . Ниже предлагаются эффективные алгоритмы для перечисления вариантов в дереве И/ИЛИ .