3.5. Нахождение пути на графе

19. Поиск пути на графе – классическая задача. На Прологе она записывается очень компактно. После несложного расширения эта программа сможет отвечать на следующие вопросы:

- как добраться из одной вершины в другую, не посещая дважды одной и той же вершины;

- как пройти по маршруту, посетив заданную вершину;

- как добраться до нужной вершины, избежав некоторых вершин.

Центральной частью программы будет база данных, содержащая данные о сети дуг между вершинами. Эта информация представлена в виде двухаргументного отношения road, например:

road(v1,v3).

road(v4,v1).

road(v3,v5).

Необходимо иметь информацию об обратных направлениях. Чтобы не дублировать базу данных, воспользуемся вспомогательным предикатом road1:

road1(T1,T2):–road(T1,T2);

road(T2,T1).

Для решения этой задачи удобнее всего собирать в список все пройденные вершины пути, исходя из следующих соображений: если существует дуга из вершины X в вершину Y, то путь найден (базовое правило), иначе чтобы найти путь из X в Y, надо найти дугу из X в Z и затем путь из Z в Y (рекурсивное правило):

way(X,Y,[ ]):–road1(X,Y).

way(X,Y,[Z|W]):–road1(X,Z), way(Z,Y,W).

Очевиден недостаток такой записи: система не смущаясь будет находить маршруты, многократно проходящие через одну и ту же вершину. Чтобы избежать этого, следует добавить проверку непринадлежности очередной вершины найденному списку вершин:

way(X,Y,[Z|W]]);- road1(X,Z), way(Z,Y,W), not(membr(Z,W)).

Здесь member– знакомый предикат проверки принадлежности элемента списку.

Рекурсия неизбежно становится нехвостовой, поскольку для предиката memberнеобходимо иметь конкретизированную величину списка W (а список этот конкретизируется только при обратном прохождении рекурсии). Но в такой рекурсии есть опасность зацикливания: можно без конца совершать переходы из одной вершины в другую и обратно, т.к. до проверки непринадлежности вершины маршруту вычисления просто не доходят. Очевидна необходимость хвостовой рекурсии. Можно перейти к такой рекурсии, если начать вычисления от конкретизированного списка (например, пустого) и иметь уже тем больший список, чем больше вложенность рекурсии, т.е. накапливать список в правой части правила. Но в таком случае накопленный список надо зафиксировать в базовом правиле введением дополнительного аргумента:

way(X,Y,W,W):–road1(X,Y).

way(X,Y,W,L):– road1(X,Z), not(member(Z,W)),

way(Z,Y,[Z|W],L).

Для запуска этой программы можно воспользоваться интерфейсным предикатом go, аргументы которого содержат начальный и конечный пункты:

go(Here,There):– way(Here,There,[Here],W),

add(There,W,W1), reverse(W1,W2), write(W2).

Здесь исходный список маршрута конкретизируется начальной вершиной. К списку найденного маршрута добавляется конечный пункт (предикат add). Предикатreverseвыполняет инверсию этого списка. Клозы этих последних предикатов было записано ранее.

3.6. Использование структур

Структуры данных являются мощным средством программирования в Прологе. Они позволяют организовать различные фрагменты информации в единые логические единицы, что дает возможность использовать информацию, не думая о деталях ее действительного представления. Широкое применение структур – это также средство представления структурных объектов (баз данных) и управления ими. Использование структур делает Пролог и естественным языком запросов к базе данных.

Структура данных в Прологе задается на составной области определения (третий способ указания Domains).

Рассмотрим ряд примеров с использованием структур.

20. База данных "Семья". Каждая семья состоит, с точки зрения логики, из трех объектов: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе – это либо "не работает", либо указания кода работы и оклада.

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

Domains

data=dat(integer,string,integer)

work=worker(string,integer);notwork

Тогда основная структура, соответствующая описанию каждого члена семьи, может выглядеть таким образом:

memfam=mem(string,string,data,work)

Информацию о семьях можно занести в базу данных с помощью следующих предложений:

family(mem(jon,kelly,dat(17,may,1950),worker(bbz,15000)),

mem(bony,kelly,dat(29,may,1951),notwork)),

[mem(pat,kelly,dat(5,april,1983),notwork),

mem(liz,kelly,dat(10,april,1960),notwork)).

family(mem(bob,rob,dat(14,may,1930),worker(pla,12000)),

mem(sally,rob,dat(5,october,1931),worker(plt,11000)),[ ]). % нет детей

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

goal family(mem(_,kelly,_,_),_,_).

Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не интересуют.

Можно найти все семьи с тремя детьми при помощи выражения:

goal family(X,_, [_,_,_]).

Чтобы найти имена и фамилии всех женщин, имеющий по крайней мере трех детей, можно задать вопрос:

goal family(_, mem(Name,Fam,_,_),[_,_,_|_]).

Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре, т.е. иметь результат в виде целой структуры или в виде отдельных элементов структур.

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

husband(X):–family(X,_,_). % X – ìóæ