Логические модели. Блок-схемы алгоритмов

Описание станций линий метро

 линия(линия_1,[a,s,d,f,g]).

 линия(линия_2,[l,k,d,j,h]).

 линия(линия_3,[z,x,d,c,v]).

 линия(линия_4,[b,n,d,m,q]).

 линия(линия_5,[c,j,f,m,x,k,s,n,c]).

 

Далее определяеться принадлежность станции к линии. Т.е. станция принадлежит списку (линии), если она являеться головой этого списка; станция принадлежит списку, если она находиться в хвосте.

 принадлежит(Станция,[Станция|_]).

 принадлежит(Станция,[_|Хвост]):- принадлежит(Станция,Хвост).

 

Аналогично производиться проверка двух станций на соседство в списке.

 соседние(Станция1,Станция2,[Станция1,Станция2|_]).

 соседние(Станция1,Станция2,[_|Хвост]):-

 соседние(Станция1,Станция2,Хвост).

 

Ненаправленность графа обеспечивается в поиске смежных станций, т.е. находим ветвь Станция1, Станция2 или Станция2, Станция1.

смежные_станции(Станция1,Станция2,Линия):- линия(Линия,Список),принадлежит(Станция1,Список),

принадлежит(Станция2,Список), соседние(Станция1,Станция2,Список);

линия(Линия,Список), принадлежит(Станция1,Список),

принадлежит(Станция2,Список), соседние(Станция2,Станция1,Список).

Пересадка с линии1 на линию 2 возможна, когда станция принадлежит обеим линиям.

пересадка(Станция,Линия1,Линия2):- линия(Линия1,Список1), линия (Линия2, Список2),

принадлежит(Станция,Список1),принадлежит(Станция,Список2), Линия1<>Линия2.

 

Осуществляем поиск возможного пути от начальной станции к конечной.

маршрут(Станция,Станция,[Станция],1,Линия,_) :- линия(Линия,Список),принадлежит(Станция,Список).

% путь с пересадкой

маршрут(Начало,Конец,[Начало,Начало2|Хвост],Остановки1,Линия,История) :-

линия(Линия,Список),линия(Новая_Линия,Новый_Список),

принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список),

пересадка(Начало,Линия,Новая_Линия),Линия<>Новая_Линия,

смежные_станции(Начало,Начало2,_),

not(принадлежит(Начало2,История)),

маршрут(Начало2,Конец,[Начало2|Хвост],Остановки2,Новая_Линия, [Начало2|История]),

Остановки1=Остановки2+1.

% путь без пересадки

маршрут(Начало,Конец,[Начало,Начало2|Хвост] ,Остановки1, Линия, История) :-

линия(Линия,Список),линия(Новая_Линия,Новый_Список),

принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список),

Линия=Новая_Линия,смежные_станции(Начало,Начало2,_),

not(принадлежит(Начало2,История)),

маршрут(Начало2, Конец, [Начало2|Хвост], Остановки2, Линия, [Начало2|История]),

Остановки1 = Остановки2 + 1.

/* осуществляется поиск пути через заданную остановку*/

через_станцию(Начало,Конец,Пром,Ost,List):-маршрут(Начало,Конец,List,Ost,_,[Начало]),принадлежит(Пром,List).

 

Тестовый пример

 

Из схемы метро(см.приложение А) выбираем начальную и конечную станции, а так же вводим промежуточные через которые нам надо проехать.Запускаем программу. Вводим соответствующие названия станций Например: нач-a,кон-g, пром-с,j.

После обработки данных программа выводит на экран маршрут проезда, в виде списка станций, через которые следует ехать, и количество остановок в пути.

 

Список использованных источников

 

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

 Мир - Москва ,1990.

2. Малпас Дж. Реляционный язык Prolog и его применение – Наука - Москва, 1990.

3. Математические модели информационных процессов и управления

 Сост.: С.И. Беляева и др. - Нижний Новгород, 1991.

Приложение

 

Код программы

/*ПРОЕЗД В МЕТРО ЧЕРЕЗ ЗАДАННЫЕ ОСТАНОВКИ*/

 

DOMAINS

список=symbol*

список1=integer*

 

PREDICATES

nondeterm линия(symbol,список)

nondeterm мин_1(integer,список1)

nondeterm минимальное(integer,список1)

nondeterm принадлежит(symbol,список)

nondeterm соседние(symbol,symbol,список)

nondeterm смежные_станции(symbol,symbol,symbol)

nondeterm пересадка(symbol,symbol,symbol)

nondeterm маршрут(symbol,symbol,список,integer,symbol,список)

nondeterm через_станцию(symbol,symbol,symbol,integer,список)

nondeterm поиск

nondeterm stations(symbol,symbol,список,integer,список)

nondeterm includ(список,список)

nondeterm vvod(integer,список,список)

nondeterm vvod1(integer,список)

nondeterm vvod2(integer)

nondeterm digit(string,integer)

 

CLAUSES

/* ОПИИСАНИЕ ЛИНИЙ */

линия(линия_1,[a,s,d,f,g]).

линия(линия_2,[l,k,d,j,h]).

линия(линия_3,[z,x,d,c,v]).

линия(линия_4,[b,n,d,m,q]).

линия(линия_5,[c,j,f,m,x,k,s,n,c]).

 

/* ПОИСК МИНИМАЛЬНОГО ЭЛЕМЕНТА В СПИСКЕ ЦЕЛЫХ ЧИСЕЛ */

мин_1(_,[]).

мин_1(Мин,[X|Хвост]):- Мин<=X, мин_1(Мин,Хвост).

минимальное(Мин,[X|Хвост]):- Мин=X,мин_1(Мин,Хвост); минимальное(Мин,Хвост).

 

/* ПРОВЕРКА НА ПРИНАДЛЕЖНОСТЬ СТАНЦИИ СПИСКУ */

принадлежит(Станция,[Станция|_]).

принадлежит(Станция,[_|Хвост]):- принадлежит(Станция,Хвост).

 

/*ПРОВЕРКА ДВУХ СТАНЦИЙ НА СОСЕДСТВО В СПИСКЕ */

соседние(Станция1,Станция2,[Станция1,Станция2|_]).

соседние(Станция1,Станция2,[_|Хвост]):- соседние(Станция1,Станция2,Хвост).

 

/* СМЕЖНЫЕ СТАНЦИИ */

смежные_станции(Станция1,Станция2,Линия):- линия(Линия,Список),принадлежит(Станция1,Список),

принадлежит(Станция2,Список), соседние(Станция1,Станция2,Список);

линия(Линия,Список), принадлежит(Станция1,Список),

принадлежит(Станция2,Список), соседние(Станция2,Станция1,Список).

 

/* ВОЗМОЖНОСТЬ ПЕРЕСАДКИ */

пересадка(Станция,Линия1,Линия2):- линия(Линия1,Список1), линия(Линия2,Список2),

принадлежит(Станция,Список1),принадлежит(Станция,Список2),Линия1<>Линия2.

 

/* ОСУЩЕСТВЛЯЕТСЯ ПОИСК ПУТИ */

маршрут(Станция,Станция,[Станция],1,Линия,_) :- линия(Линия,Список),принадлежит(Станция,Список).

% путь с пересадкой

маршрут(Начало,Конец,[Начало,Начало2|Хвост],Остановки1,Линия,История) :-

линия(Линия,Список),линия(Новая_Линия,Новый_Список),

принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список),

пересадка(Начало,Линия,Новая_Линия),Линия<>Новая_Линия,

смежные_станции(Начало,Начало2,_),

not(принадлежит(Начало2,История)),

маршрут(Начало2,Конец,[Начало2|Хвост],Остановки2,Новая_Линия,[Начало2|История]),

 

Остановки1=Остановки2+1.

% путь без пересадки

маршрут(Начало,Конец,[Начало,Начало2|Хвост],Остановки1,Линия,История) :-

линия(Линия,Список),линия(Новая_Линия,Новый_Список),

принадлежит(Начало,Список),принадлежит(Начало2,Новый_Список),

Линия=Новая_Линия,смежные_станции(Начало,Начало2,_),

not(принадлежит(Начало2,История)),

маршрут(Начало2,Конец,[Начало2|Хвост],Остановки2,Линия,[Начало2|История]),

Остановки1 = Остановки2 + 1.

/* осуществляется поиск пути через заданную остановку*/

через_станцию(Начало,Конец,Пром,Ost,List):-маршрут(Начало,Конец,List,Ost,_,[Начало]),принадлежит(Пром,List).     

поиск:-write("Выбор маршрута в метро c проездом через заданные остановки"),nl,

write("Схему метро смотрите в Приложении А пояснительной записки"),nl,nl,

write("Введите начальнаую станцию = "),readln(Начало),

write("Введите конечную станцию = "),readln(Конец),

vvod1(_,Prom),

findall(Остановки,stations(Начало,Конец,Prom,Остановки,List),Ost_Список),

минимальное(Остановки,Ost_Список),

stations(Начало,Конец,Prom,Остановки,List),

%через_станцию(Начало,Конец,Пром,Остановки,List),

write("\nПуть: ",List,"\nЧисло остановок: ",

 

Остановки),nl.

stations(Начало,Конец,Пром,Ost,List):-маршрут(Начало,Конец,List,Ost,_,[Начало]),

includ(Пром,List).

%проверка, чтобы элемента из списка1 входили в список2

includ([X],List):-принадлежит(X,List).

includ([X|List1],List):-принадлежит(X,List),includ(List1,List).

vvod(1,List,List1):-write("Введите последнюю промежуточную станцию: "),

readln(Str),not(принадлежит(Str,List1)),List=[Str],!.

vvod(N,List,List1):-N>1,write("Введите промежуточную станцию: "),

readln(Nomer),

not(принадлежит(Nomer,List1)),N1=N-1,

vvod(N1,List2,[Nomer|List1]),List=[Nomer|List2],!;

write("Станция с таким названием уже была введена"),nl,vvod(N,List,List1).

digit(Str,Digit):- str_int(Str,Digit).

vvod2(N):-write("Сколько вы хотите ввести промежуточных станций: "),nl,

readln(Str),digit(Str,N),!;

write("Была введена не цифра. Повторите ввод"),nl,vvod2(N).

vvod1(N,List):-vvod2(N),vvod(N,List,[]).

GOAL

поиск.