Программирование на языке Пролог для искусственного интеллекта


         

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


Для задачи отыскания кратчайшего маршрута (рис. 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.  Решающее дерево минимальной стоимости для задачи

    поиска маршрута рис. 13.1, сформулированной в терминах И / ИЛИ-

    графа.

    13.5 показан решающий граф, имеющий стоимость 9. Это дерево соответствует пути [a, b, d, f, i, z], который можно построить, если пройти по всем листьям решающего дерева слева направо.



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