Одесский национальный университет им. И.И.Мечникова Министерство науки и образования Украины
Лабораторная работа №5
по курсу «Специализированные языки программирования»
выполнил студент III курса гр. МОКС
Свиридов Артём
Одесса 2012
Цель работы: изучить основные алгоритмы работы с деревьями и графами – обход, поиск кратчайших путей и др.
Постановка задачи.
Разработать программу, реализующую задание:
Граф представляет карту дорог. Найти все города, длина пути до которых от города А не меньше заданной.
Код программы на Visual Prolog 7.3:
implement main
open core, console, string
constants
className = "main". classVersion = "".
clauses
classInfo(className, classVersion).
domains
list = integer*. symbollist=symbol*. town=town(symbol,integer).
class facts
edge: (symbol,symbol,integer).
class predicates
path : (symbol,symbol,symbollist,integer) nondeterm(i,i,o,o).
path_aux : (symbol,symbollist,symbollist,integer,integer) nondeterm(i,i,o,i,o). connect : (symbol,symbol,integer) nondeterm(o,i,o).
belong_s : (symbol,symbollist) determ(i,i). roadlist : (symbol,list) procedure(i,o). findtown : (symbol,symbol) nondeterm(i,o).
add : (symbollist,symbollist,symbol) procedure(i,o,i). no_repeat : (symbollist, symbollist, symbollist) procedure(i,i,o). town_accept : (symbol,integer,integer) determ(i,o,i). town_accept2 : (list,integer,integer) determ(i,o,i).
findreqtowns : (symbollist,symbollist,list,integer) procedure(i,o,o,i). start : (integer) procedure(i).
clauses edge("A","B",1). edge("B","C",1). edge("C","D",2). edge("B","D",5).
roadlist(T,Q):-findall(R,path("A",T,_,R),Q).
path(Begin,End,Path,R):-path_aux(Begin,[End],Path,0,R).
path_aux(Begin,[Begin|Tail_Path],[Begin|Tail_Path],R,R):-!. path_aux(Begin,[Head_Path|Tail_Path],Path,X,R) :- connect(Tmp,Head_Path,L), not(belong_s(Tmp,
Tail_Path)), path_aux(Begin, [Tmp,Head_Path|Tail_Path], Path, X+L, R).
connect(Node1, Node2, L):-edge(Node1, Node2, L). connect(Node1, Node2, L):-edge(Node2, Node1, L).
belong_s(N,[N|_]):-!. belong_s(N,[_|T]):-belong_s(N,T).
start(A):-findall(N,findtown("A",N),Q),no_repeat(Q,[],L),findreqtowns(L,L1,L2,A),nl,write(L1),nl,write(L2),!.
findtown(T,N):-edge(_,N,_), N <> T. findtown(T,N):-edge(N,_,_), N <> T.
add([],[E],E) :- !. add([H|T],[H|T],E) :- H=E, !. add([H|T],[H|T1],E) :- add(T,T1,E).
no_repeat([],RES,RES):-!.
no_repeat([H|T],L,RES) :- add(L,L1,H), no_repeat(T,L1,RES).
findreqtowns([],[],[],_):-!. findreqtowns([H|T],[H|T1],[K|T2],A):-town_accept(H,K,A),findreqtowns(T,T1,T2,A), !. findreqtowns([_|T],T1,T2,A):-findreqtowns(T,T1,T2,A).
town_accept(H,K,A) :- roadlist(H,L), town_accept2(L,K,A).
town_accept2([H|_],H,A) :- H >= A,!. town_accept2([_|T],K,A) :- town_accept2(T,K,A).
clauses run():-
console::init(), K = read(), start(K),
console::clearInput(), _=readline().
end implement main
goal mainExe::run(main::run).
Граф представлен внутри программы, в виде отдельных предложений – фактов edge(<город_1>,<город_2>,<длина_пути>).
start(K) – функция, выводящая решение задачи на экран, где К – заданная пользователем длина пути.
Алгоритм:
Функция start ищет все города в графе, отличные от А (функция findtown), удаляет из списка этих городов повторяющие города (функция no_repeat), затем вызывается функция findreqtowns, выбирающая из списка лишь те города, что подходят (путь до них не меньше заданного).
Пути, содержащие циклы, не считаются, т.к. в таком случае в большинстве сложных графов решениями задачи были бы все существующие города.
На экран выводится список найденных городов, а также список соответствующих им длин путей (первых, что оказались не меньше заданного).
Функция findreqtowns с помощью вспомогательных функций перебирает каждый город из списка, находит все возможные пути из А в данный город (без циклов), и вычисляет, присутствует ли среди путей такой, что не меньше заданного. Если присутствует, данный город и путь добавляются в соответствующие списки.
Функции программы: |
|
path(Begin,End,Path,R), path_aux(Begin,[Head_Path|Tail_Path],Path,X,R) |
– |
находят все возможные пути Path из города Begin в город End, попутно вычисляя путь R; вспомогательные функции: connect(Node1, Node2, L) – находит все смежные с Node2 города Node1 и их пути L, belong_s(N,M) – проверяет, принадлежит ли город N списку городов M.
findtown(А,N) – ищет все города в графе, отличные от А (с повторами). no_repeat(Q,Т,L), его внутренняя функция add(S,S1,H) – исключает все
повторения из списка Q, создаёт результирующий список L.
roadlist(T,Q) – c помощью findall и path получает список всех длин путей Q из города А в город T.
town_accept(H,K,N) – вызывает roadlist для города H, проверят каждую длину пути из полученного списка; если данная длина не меньше N, то выводит К – данную длину; иначе – функция не выполняется.
findreqtowns(L,L1,L2,N) – отбирает из списка городов L лишь те, что удовлетворяют условию; L1 – результирующий список городов, L2 – результирующий список соответствующих им длин путей, N – заданная пользователем длина; программа выполняется рекурсивно, в процессе вызывается town_accept.
start(N) – с помощью findall и findtown создаёт список городов, с помощью no_repeat удаляет лишние города из списка, с помощью findreqtowns создаёт результирующие списки городов и длин путей, выводит их на экран; N – заданная пользователем длина пути.
Результат работы программы:
Вывод
Вданной лабораторной работе были получены необходимые навыки работы
сграфами в Visual Prolog 7.3.