Calc_Work / CW_Pzis

6

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ

Кафедра інформаційних систем

Розрахункова робота

з дисципліни

ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ

Тема

Пошук оптимального шляху на графі станів

Виконав:

студент групи АКС4-5

Теслович І.Ю.

Перевірила:

Гаркуша І.Д.

Київ 2012

Розрахункова робота

з дисципліні

ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ

Тема :	Пошук на шляху найменшої ваги на зваженому графі станів
Мета :	Практичне ознайомлення з методом пошуку оптимального шляху на графі станів
План роботи :
Побудувати, відпрацювати та ознайомитись з роботою методів і відповідних програм пошуку на графах стану. Створити схему зваженого графа у складі 25-30 дуг з 4-6 кільцевими контурами. Дати схему графа. Створити відповідну базу даних. Побудувати схему послідовності розв'язку задачі. Створити програму пошуку оптимального шляху на графі станів На графі п.1 з використанням програми у режимі тестування цілі відпрацювати задачу пошуку шляхів між стартовою та цільовою вершинами.

До звіту включити:

• Завдання

• Зображення графів з нанесеними на них рішеннями;

• Схему послідовності розв'язку задачі.

• Тексти програм;

• Висновки

Схема зваженого графу

Схема графу

C

А B D E

G H F

M

K L N

O

База даних зваженого графа.

vet_("a","b",2). vet_("a","g",2).vet_("g","k",1).vet_("g","l",4).vet_("k","l",3).

vet_("g","b",6).vet_("b","d",3).vet_("c","d",3). vet_("d","f",2). vet_("c","e",4).

vet_("e","f",1).vet_("h","l",2).vet_("h","f",3).vet_("h","m",5).vet_("m","n",3).

vet_("m","o",4). vet_("n","o",2).

Послідовність розв'язку задачі

Текст програми

/*****************************************************************************

Purpose: Пошук на графі стану шляху з найменшою вагою

******************************************************************************/

% Пошук у глибину з начисленням ваги i min.

DOMAINS

UZ=STRING

LISTS=STRING*

RLIST=REAL*

DAT=dat(INTEGER Nmb,REAL Vaga)

DATL=DAT*

DATABASE-graf

vet_(UZ,UZ,REAL G)

start(UZ)

finish(UZ)

DATABASE-cur

determ cl(INTEGER)

DATABASE-res

path(INTEGER Nmb,LISTS Path,REAL Vaga)

PREDICATES

nondeterm solS(STRING,STRING,LISTS,REAL G)

nondeterm glS(LISTS,STRING,STRING,LISTS,REAL Gc,REAL G)

nondeterm member(STRING,LISTS).

nondeterm mgS(STRING,STRING,REAL DG)

nondeterm oneSol(DAT)

doSol

%-------

quicksort(DATL,DATL)

CLAUSES

member(X,[X|_]).

member(X,[_|_L]):-member(X,_L).

%------------------------------------

mgS(X,Y,D):-

vet_(X,Y,D).

mgS(X,Y,D):-

vet_(Y,X,D).

%....................................

solS(X,Y,L,G):-

glS([],X,Y,L,0.0,G).%,

%------------------------------------------------

glS(S1,Xt,Xt,[Xt|S1],G,G):-!.

glS(S1,Xt,Y,S,Gcur,G):-

mgS(Xt,Z,DG),

Gcur1=Gcur+DG,

not(member(Z,S1)),

glS([Xt|S1],Z,Y,S,Gcur1,G).

%-------------------------------------------------

oneSol(DAT):-

start(ST),

finish(FIN),

solS(ST,FIN,L,G),

cl(C),

C1=C+1,

assert(path(C1,L,G),res),

write("Номер=",C1," Шлях=",L," Вага=",G),nl,

DAT=dat(C1,G),

retractall(cl(_),cur),

assert(cl(C1),cur).

%-------------------------------------------------

% Сортування списків

PREDICATES

nondeterm partishion(DATL,DAT,DATL,DATL).

append(RLIST,RLIST,RLIST)

append(DATL,DATL,DATL)

CLAUSES

quicksort([X|Xs],Ys):-

partishion(Xs,X,Littles,Bigs),

quicksort(Littles,Ls),

quicksort(Bigs,Bs),

append(Ls,[X|Bs],Ys),!.

quicksort([],[]).

partishion([X|Xs],Y,[X|Ls],Bs):- %X<=Y,partishion(Xs,Y,Ls,Bs),

X=dat(_Nx,Gx),

Y=dat(_Ny,Gy),

Gx<=Gy,

partishion(Xs,Y,Ls,Bs).

partishion([X|Xs],Y,Ls,[X|Bs]):- %X>Y ,partishion(Xs,Y,Ls,Bs),

X=dat(_Nx,Gx),

Y=dat(_Ny,Gy),

Gx>Gy,

partishion(Xs,Y,Ls,Bs).

partishion([],_,[],[]).

append([],Ys,Ys).

append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).

%#############################################

%-------------------------------------------------

doSol:-

assert(cl(0),cur),

findall(D,oneSol(D),LD), %Пошук і зважування всіх шляхів

nl,write("LD =",LD),nl,

quicksort(LD,LDOrd), %Упорядкування шляхів за вагою

nl,write("LDOrd=",LDOrd),nl,

LDOrd=[MIN|_LDOrd1], %Визначення даних найлегшого шляху

MIN=dat(NMin,_), %Визначення номеру найлегшого шляху

path(NMin,L,G),!,

nl,nl,

write("_______________________________________"),nl,

write("Параметри кращого шляху"),nl,

write("_______________________________________"),nl,

write("Номер=",NMin),nl,

write("Шлях =",L),nl,

write("Вага =",G),nl.

%-------------------------------- ГРАФ ---------------------------------------

vet_("a","b",2). vet_("a","g",2).vet_("g","k",1).vet_("g","l",4).vet_("k","l",3).

vet_("g","b",6).vet_("b","d",3).vet_("c","d",3). vet_("d","f",2). vet_("c","e",4).

vet_("e","f",1).vet_("h","l",2).vet_("h","f",3).vet_("h","m",5).vet_("m","n",3).

vet_("m","o",4). vet_("n","o",2).

start("o").

finish("a").

%####################################

GOAL doSol.