Назад | Содержание| Вперёд 13. 2. Примеры И/ИЛИ-представления задач ...

Назад | Содержание| Вперёд

13. 2. Примеры И/ИЛИ-представления задач

13. 2. 1. И / ИЛИ-представлениезадачи поиска маршрута

Для задачи отыскания кратчайшего маршрута (рис.13.1) И / ИЛИ-граф вместе с функцией стоимости можноопределить следующим образом:

ИЛИ-вершины представляются в форме X-Z, что означает: найти кратчайший путь из X в Z.

И-вершины имеют вид

X-Z через Y

что означает: найти кратчайший путь из X в Z, проходящий через Y.

Вершина X-Z является целевой вершиной (примитивной задачей), если на карте существует непосредственная связь между X и Z.

Стоимость каждой целевой вершины X-Z равна расстоянию, которое необходимо преодолеть по дороге, соединяющей X с Z.

Стоимость всех остальных (нетерминальных) вершин равна 0.

Стоимость решающего графа равна сумместоимостей всех его вершин (в нашем случае этопросто сумма стоимостей всех терминальныхвершин). В задаче рис. 13.1 стартовая вершина - это а-z. На рис.

Рис. 13. 7. Формулировкаигровой задачи для игры двух лиц в

форме И / ИЛИ-дерева; участники игры: "игрок"и "противник".

та хода противника. Другими словами, игроквыигрывает в Q_i, если онвыигрывает во всех позициях R_i1 и R_i2 и ... . Таким образом, всепозиции противника - это И-вершины. Целевыевершины - это позиции, выигранные согласноправилам игры, например позиции, в которых корольпротивника получает мат. Позициям проиграннымсоответствуют задачи, не имеющие решения. Длятого, чтобы решить игровую задачу, мы должныпостроить решающее дерево, гарантирующее победуигрока независимо от ответов противника. Такоедерево задает полную стратегию достижениявыигрыша: для каждого возможного продолжения,выбранного противником, в дереве стратегии естьответный ход, приводящий к победе.

Назад | Содержание| Вперёд

Оглавление