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



         

Поиск пути в графе - часть 3


Используя отношение путь, эту задачу можно решить так:

        гамильтон( Граф, Путь) :-

                путь( _, _, Граф, Путь),

                всевершины( Путь, Граф).

        всевершины( Путь, Граф) :-

                not (вершина( В, Граф),

                        not принадлежит( В, Путь) ).

Здесь вершина( В, Граф) означает: В

- вершина графа Граф.

Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.

Для того, чтобы наши отношения путь и путь1

могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:

        путь( А, Z, G, Р, С)

        путь1( A, P1, C1, G, Р, С)

Здесь С - стоимость пути Р, a C1 - стоимость пути Р1. В отношении смеж также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.

line();

        путь( А, Z, Граф, Путь, Ст) :-

                путь1( A, [Z], 0, Граф, Путь, Ст).

        путь1( А, [А | Путь1], Ст1, Граф, [А | Путь1], Ст).

        путь1( А, [Y | Путь1], Ст1, Граф, Путь, Ст) :-

                смеж( X, Y, СтXY, Граф),

                not принадлежит( X, Путь1),



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