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




Поиск пути в графе - часть 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),



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