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

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

%

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

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

% Граф = [а-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. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер. Напишите программу построения для заданного графа его остовного дерева минимальной стоимости.

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

• Списки:

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

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

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

сортировка со вставками

быстрая сортировка

эффективность этих процедур

• Представление множеств двоичными деревьями и двоичными справочниками:

поиск элемента в дереве

добавление элемента

удаление элемента

добавление в качестве листа или корня

сбалансированность деревьев и его связь с эффективностью этих операций

отображение деревьев

• Графы:

представление графов

поиск пути в графе

построение остовного дерева

В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).

Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).