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

Основное отношение, используемое в этой программе, — это

расширить( Дер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. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.

% Построение остовного дерева
% Графы и деревья представлены списками ребер.
остдерево( Граф, Дер) :-
 подмнож( Граф, Дер),
 дерево( Дер),
 накрывает( Дер, Граф).
дерево( Дер) :-
 связи( Дер),
 not имеетцикл( Дер).
связи( Дер) :-
 not ( вершина( А, Дер), вершина( В, Дер),
 not путь( А, А, Дер, _ ) ).
имеетцикл( Дер) :-
 смеж( А, В, Дер),
 путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1
накрывает( Дер, Граф) :-
 not ( вершина( А, Граф), not вершина( А, Дер) ).
подмнож( [], []).
подмнож( [ X | L], S) :-
 подмнож( L, L1),
 ( S = L1; S = [ X | L1] ).

Рис. 9.23. Построение остовного дерева: 'декларативный подход'.

Отношения вершина и смеж см. на рис. 9. 22.

Упражнение

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

Резюме

В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе

• Списки:

  варианты представления списков

  сортировка списков:

    сортировка методом 'пузырька'