Примеры и/или-представления задач
Примеры И/ИЛИ-представления задач
И / ИЛИ-представление задачи поиска маршрута
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. На рис.
