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

...

дуга( s, t, 3).

дуга( t, v, 1).

дуга( u, t, 2).

...

Другой способ — весь граф представлять как один объект. В этом случае графу соответствует пара множеств — множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро — парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра — функтор p. Тогда (ненаправленный) граф рис. 9.18 примет вид:

G1 = граф( [a, b, c, d],

 [p( а, b), p( b, d), p( b, с), p( c, d)] )

Рис. 9.18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.

Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим

G2 = диграф( [s, t, u, v],

 [д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),

  д( v, u, 2) ] )

Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.

Еще один способ представления графа — связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как

G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]

G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]

Здесь символы '->' и '/' — инфиксные операторы.

Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:

• найти путь между двумя заданными вершинами;

• найти подграф, обладающий некоторыми заданными свойствами.

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

<p>9.5.2. Поиск пути в графе</p>

Пусть G — граф, а А и Z — две его вершины. Определим отношение

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

где P — ациклический путь между А и Z в графе G. Если G — граф, показанный в левой части рис. 9.18, то верно:

путь( a, d, G, [a, b, d] )

путь( а, d, G, [a, b, c, d] )

Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:

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

Если А = Z , то положить P = [А], иначе найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из P1.

В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае P1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:

путь1( А, P1, G, P)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл:

• А — некоторая вершина,

• G — граф,

• P1 — путь в G,

• P — ациклический путь в G, идущий из А в начальную вершину пути P1, а затем — вдоль пути P1 вплоть до его конца.

Pис. 9.19. Отношение путь1Путь — это путь между А и Z, в своей заключительной части он перекрывается с Путь1.

Между путь и путь1 имеется следующее соотношение:

путь( А, Z, G, P) :- путь1( А, [Z], G, P).

На рис. 9.19 показана идея рекурсивного определения отношения путь1. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути P. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что

(1) Y — вершина, смежная с X,

(2) X не содержится в P1 и

(3) для P выполняется отношение путь1( А, [X | P1], G, P).

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

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

путь1( А, [А | Путь1, _, [А | Путь1] ).

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

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

 принадлежит( X, Путь1), % Условие отсутствия цикла

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

Рис. 9.20. Поиск в графе Граф ациклического пути Путь из А в Z.

Перейти на страницу:

Похожие книги

Adobe InDesign CS3
Adobe InDesign CS3

Книга посвящена верстке и макетированию в программе Adobe InDesign CS3. Помимо того что в ней описываются возможности программы, рассматриваются также принципы и традиции верстки, приводятся примеры решения типичных задач. Все это позволит читателю не только овладеть богатым инструментарием программы, но и грамотно применять его.Материал книги разделен на логические части: теоретические сведения, инструментарий программы, решение задач, – а также рассчитан на два уровня подготовки читателей – начинающих и опытных пользователей, что выгодно отличает книгу от других изданий. Это позволит применять ее как новичкам для знакомства с программой, так и пользователям со стажем для пополнения своих знаний.

Владимир Гавриилович Завгородний , Владимир Завгородний

Программирование, программы, базы данных / Программное обеспечение / Книги по IT
C++
C++

С++ – это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей С++ является надмножеством языка программирования C. Помимо возможностей, которые дает C, С++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы. Ключевым понятием С++ является класс. Класс – это тип, определяемый пользователем. Классы обеспечивают сокрытие данных, гарантированную инициализацию данных, неявное преобразование типов для типов, определенных пользователем, динамическое задание типа, контролируемое пользователем управление памятью и механизмы перегрузки операций. С++ предоставляет гораздо лучшие, чем в C, средства выражения модульности программы и проверки типов. В языке есть также усовершенствования, не связанные непосредственно с классами, включающие в себя символические константы, inline-подстановку функций, параметры функции по умолчанию, перегруженные имена функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены возможности языка C по работе с основными объектами аппаратного обеспечения (биты, байты, слова, адреса и т.п.). Это позволяет весьма эффективно реализовывать типы, определяемые пользователем. С++ и его стандартные библиотеки спроектированы так, чтобы обеспечивать переносимость. Имеющаяся на текущий момент реализация языка будет идти в большинстве систем, поддерживающих C. Из С++ программ можно использовать C библиотеки, и с С++ можно использовать большую часть инструментальных средств, поддерживающих программирование на C. Эта книга предназначена главным образом для того, чтобы помочь серьезным программистам изучить язык и применять его в нетривиальных проектах. В ней дано полное описание С++, много примеров и еще больше фрагментов программ.

Бьёрн Страуструп , Бьярн Страустрап , Мюррей Хилл

Программирование, программы, базы данных / Программирование / Книги по IT