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

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.5 показан решающий граф, имеющий стоимость 9. Это дерево соответствует пути [a, b, d, f, i, z], который можно построить, если пройти по всем листьям решающего дерева слева направо.

Рис. 13.5. Решающее дерево минимальной стоимости для задачи поиска маршрута рис. 13.1, сформулированной в терминах И/ИЛИ-графа.