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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ст2 is Ст1 + СтXY,

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

Рис. 9.21. Поиск пути в графе: Путь — путь между А и Z в графе Графстоимостью Ст.

Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами Верш1, Верш2графа Граф, задав цели

путь( Bepш1, Верш2, Граф, МинПуть, МинСт),

not( путь( Верш1, Верш2, Граф, _, Ст), Ст<���МинСт )

Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели

путь( _, _, Граф, МаксПуть, МаксСт),

not( путь( _, _, Граф, _, Ст), Ст > МаксСт)

Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.

Граф называется связным , если между любыми двумя его вершинами существует путь. Пусть G = (V, E) — связный граф с множеством вершин V и множеством ребep E. Остовное дерево графа G — это связный граф T = ( V, E'), где E' — подмножество E такое, что

(1) T — связный граф,

(2) в T нет циклов.

Выполнение этих двух условий гарантирует то, что T — дерево. Для графа, изображенного в левой части рис. 9.18, существует три остовных дерева, соответствующих следующим трем спискам ребер:

Дер1 = [а-b, b-c, c-d]

Дер2 = [а-b, b-d, d-с]

Дер3 = [а-b, b-d, b-c]

Здесь каждый терм вида X-Y обозначает ребро, соединяющее вершины X и Y. В качестве корня можно взять любую из вершин, указанных в списке. Остовные деревья представляют интерес, например в задачах проектирования сетей связи, поскольку они позволяют, имея минимальное число линий, установить связь между любыми двумя узлами, соответствующими вершинам графа.

Определим процедуру

остдерево( G, T)

где T — остовное дерево графа G. Будем предполагать, что G — связный граф. Можно представить себе алгоритмический процесс построения остовного дерева следующим образом. Начать с пустого множества ребер и постепенно добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы. Продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Полученное множество ребер будет остовным деревом. Отсутствие циклов можно обеспечить, если придерживаться следующего простого правила: ребро присоединяется к дереву только в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него. Программа, реализующая эту идею, показана на рис. 9.22. Основное отношение, используемое в этой программе, — это

расширить( Дер1, Дер, G)

Здесь все три аргумента — множества ребер. G— связный граф; Дер1и Дер — два подмножества G, являющиеся деревьями. Дер — остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из Gк Дер1. Можно сказать, что " Дер1расширено до Дер".

% Построение остовного дерева графа

%

% Деревья и графы представлены списками

% своих ребер, например:

% Граф = [а-b, b-с, b-d, c-d]

остдерево( Граф, Дер) :- % Дер - остовное дерево Граф'а

принадлежит( Ребро, Граф),

расширить( [Ребро], Дер, Граф).

расширить( Дер1, Дер, Граф) :-

добребро( Дер1, Дер2, Граф),

расширить( Дер2, Дер, Граф).

расширить( Дер, Дер, Граф) :-

not добребро( Дер, _, Граф).

% Добавление любого ребра приводит к циклу

добребро( Дер, [А-В | Дер], Граф) :-

смеж( А, В, Граф), % А и В - смежные вершины

вершина( А, Дер). % А содержится в Дер

not вершина( В, Дер). % А-В не порождает цикла

смеж( А, В, Граф) :-

принадлежит ( А-В, Граф);

принадлежит ( В-А, Граф).

вершина( А, Граф) :- % А содержится в графе, если

смеж( А, _, Граф). % А смежна какой-нибудь вершине

Pис. 9.22. Построение остовного дерева: алгоритмический подход. Предполагается, что Граф — связный граф.

Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения. Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе рис. 9.22. Нам понадобятся следующие определения:

(1) T является остовным деревом графа G, если

• T — это подмножество графа G и

• T — дерево и

• T "накрывает" G, т.е. каждая вершина из G содержится также в T.

(2) Множество ребер T есть дерево, если

• T — связный граф и

• T не содержит циклов.

Эти определения можно сформулировать на Прологе (с использованием нашей программы путьиз предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.

% Построение остовного дерева

% Графы и деревья представлены списками ребер.

остдерево( Граф, Дер) :-

подмнож( Граф, Дер),

дерево( Дер),

накрывает( Дер, Граф).

дерево( Дер) :-