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

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

Резюме

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

• Списки:

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

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

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

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

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

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

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

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

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

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

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

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

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

• Графы:

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

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

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

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

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

Aho А. V., Hopcroft J. E. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.]

Aho А. V., Hopcroft J. E. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Baase S. (1978). Computer Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.

Глава 10

Усовершенствованные методы представления множеств деревьями

В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том, чтобы поддерживать сбалансированности или приближенную сбалансированность дерева, с тем чтобы избежать вырождения его в список. Механизмы балансировки деревьев гарантируют, даже в худшем случае, относительно быстрый доступ к элементам данных, хранящихся в дереве, при логарифмическом порядке времени доступа. В этой главе изложено два таких механизма: двоично-троичные (кратко, 2-3) деревья и AVL-деревья. (Для изучения остальных глав понимание данной главы не обязательно.)

10.1. Двоично-троичные справочники

Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log n, где n — число вершин дерева. Время, необходимое для вычислений, производимых отношениями внутри, добавить и удалить над двоичными справочниками, пропорционально глубине дерева. Таким образом, в случае двоичных справочников это время имеет порядок log n. Логарифмический рост сложности алгоритма, проверяющего принадлежность элемента множеству, — это определенное достижение по сравнению со списковым представлением, поскольку в последнем случае мы имеем линейный рост сложности с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производительности алгоритмов, работающие со справочником. В крайнем случае, двоичный справочник вырождается в список, как показано на рис. 10.1. Форма справочника зависит от той последовательности, а которой в всего записываются элементы данных. В лучшей случае мы получаем хорошую балансировку и производительность порядка log n, а в худшем — производительность будет порядка n. Анализ показывает, что в среднем сложность алгоритмов внутри, добавить и удалить сохраняет порядок log n в допущении, что все возможные входные последовательности равновероятны. Таким образом, средняя производительность, к счастью, оказывается ближе к лучшему случаю, чек к худшему. Существует, однако, несколько довольно простых механизмов, которые поддерживают хорошую сбалансированность дерева, вне зависимости от входной последовательности, формирующей дерево. Эти механизмы гарантируют производительность алгоритмов внутри, добавить и удалить порядка log n даже в худшем случае. Один из этих механизмов - двоично-троичные деревья (кратко, 2-3 деревья), а другой — AVL-деревья.

Рис. 10.1. Полностью разбалансированный двоичный справочник. Производительность его та же, что и у списка.