И-или дерево
Дерево «и-или» — это графическое представление сведения проблем (или целей) к соединениям и дизъюнкциям подзадач (или подцелей).
Пример
[ редактировать ]И/или дерево:
представляет собой пространство поиска решения задачи P с использованием методов редукции цели:
- P, если Q и R
- P, если S
- Q, если Т
- Вопрос, если ты
Определения
[ редактировать ]Дана исходная задача P 0 и набор методов ее решения вида:
- P, если P 1 и … и P n
связанное дерево «и-или» представляет собой набор помеченных узлов, таких что:
- Корнем дерева является узел, помеченный P 0 .
- Для каждого узла N, помеченного проблемой или подзадачой P, и для каждого метода формы P, если P 1 и ... и P n , существует набор дочерних узлов N , ..., N n 1 узел N, такой, что каждый узел N i помечен P i . Узлы соединены дугой, чтобы отличить их от дочерних элементов N, которые могут быть связаны с другими методами.
Узел N, помеченный проблемой P, является узлом успеха, если существует метод формы P, если ничего (т. е. P является «фактом»). Узел является узлом отказа, если не существует метода решения P.
Если все дочерние элементы узла N, соединенные одной дугой, являются успешными узлами, то узел N также является успешным узлом. В противном случае узел является узлом отказа.
Стратегии поиска
[ редактировать ]Дерево «и-или» задает только пространство поиска решения задачи. различные стратегии поиска Возможны в пространстве. К ним относятся поиск по дереву в глубину, в ширину или по наилучшему результату с использованием некоторой меры желательности решений. Стратегия поиска может быть последовательной, осуществляющей поиск или генерацию одного узла за раз, или параллельной, осуществляющей поиск или генерацию нескольких узлов параллельно.
Связь с логическим программированием
[ редактировать ]Методы, используемые для генерации и/или деревьев, представляют собой программы пропозициональной логики (без переменных). В случае логических программ, содержащих переменные, решения совместных подзадач должны быть совместимыми. С учетом этой сложности стратегии последовательного и параллельного поиска по деревьям и/или предоставляют вычислительную модель для выполнения логических программ.
Отношения с играми для двух игроков
[ редактировать ]И/или деревья также можно использовать для представления пространств поиска в играх для двух человек. Корневой узел такого дерева представляет собой задачу победы одного из игроков в игре, начиная с начального состояния игры. Учитывая узел N, помеченный проблемой P, когда игрок выигрывает игру из определенного состояния игры, существует единственный набор совместных дочерних узлов, соответствующий всем ответным ходам оппонентов. Для каждого из этих дочерних узлов существует набор несовместных дочерних узлов, соответствующих всем защитным ходам игрока.
Для решения игровых деревьев с помощью семейства алгоритмов поиска по числу доказательств деревья игр должны быть сопоставлены с и/или деревьями. MAX-узлы (т.е. максимизация перемещения игрока) представлены как узлы OR, MIN-узлы отображаются в узлы AND. Сопоставление возможно, когда поиск выполняется только с бинарной целью, которая обычно состоит в том, что «игрок, который должен двигаться, выигрывает игру».
Библиография
[ редактировать ]- Люгер, Джордж Ф.; Стабблфилд, Уильям А. (1993). Искусственный интеллект: структуры и стратегии решения сложных задач (2-е изд.). Бенджамин/Каммингс. ISBN 978-0-8053-4785-2 . Проверено 28 февраля 2013 г.
- Нильссон, Нильс Дж. (1998). Искусственный интеллект: новый синтез . Морган Кауфманн. ISBN 978-1-55860-467-4 . Проверено 28 февраля 2013 г.
- Рассел С. и Норвиг П., 2021. Искусственный интеллект: современный подход, 4-е изд. США. Калифорнийский университет, Беркли, стр. 141.