Информационен Интернет сайт Moderno.info

Графа може да се опише чрез отношението ”nasl”. Съседството между два възела X и Y може да се изрази чрез предиката:

nasl(X,Y).
който е в сила,ако Y е непосредствен наследник на възела X.
Описанието на графа чрез отношението ”nasl” изглежда така:

• nasl(1,2,12).
• nasl(1,3,5).
• nasl(3,6,5).
• nasl(3,7,4).
• nasl(3,5,1).
• nasl(7,16,3).
• nasl(7,17,2).
• nasl(6,11,4).
• nasl(11,12,1).
• nasl(12,10,3).
• nasl(10,23,7).
• nasl(11,13,1).
• nasl(13,19,5).
• nasl(5,15,7).
• nasl(5,14,9).
• nasl(14,18,6).
• nasl(18,19,3).
• nasl(18,20,2).
• nasl(2,4,9).
• nasl(2,40,16).
• nasl(4,9,18).
• nasl(4,8,7).
• nasl(9,22,13).
• nasl(9,23,5).
• nasl(8,21,2).
• nasl(8,10,1).

При реализацията на търсене в ширина с програма на ПРОЛОГ се дефинира предикат,създаващ списък от всички терми: all(терм,списък),където списък ще съдържа всички терми. Предиката all поставя в базата от данни всеки терм като rec(терм). След това съответните записи се извличат от базата от данни и формират резултатния списък.

all([P|S],_):-nasl(P,T,_),assert(rec([T,P|S])),fail.
all(_,Sp):-assert(rec(0)),form([],Sp).
form(Sp1,Sp):-izvl(T),!,form([T|Sp1],Sp).
form(Sp,Sp).
izvl(T):-rec(T),retract(rec(T)),!,not(T=0).

Предиката all се използва в програмата реализираща търсене в ширина за определяне на всички непосредствени наследници на текущия възел. В процеса на търсене се извършва пораждане на пътищата в графа въз основа на табличното му представяне чрез съвкупността на факти nasl(X,Y). Пътищата за решение на задачата са представени чрез списък, всеки елемент на който също е списък,представлящ един от пътищата. Всеки път представлява последователност от възли на граф, подредени в обратен ред-глава на списъка е последният пореден възел. Процедурата за търсене в ширина се основава на следния алгоритъм:
ако първият път в списъка съдържа (като глава) целево състояние,той е решение на задачата
в противен случай първият път се отстранява в началото на списъка и се разширява.Решението се състои в пораждане на непосредствените наследници на последния разглеждан възел (съдържа се в главата на подсписъка). Разширеният подсписък се записва в края на списъка на кандидатите.

t_shir(Nach,Resh):-razsh([[Nach]],Resh).
razsh([[P|S]|_],[P|S]):-zel(P).
razsh([[P|S]|K],R):-all([P|S],Sas),append(K,Sas,K1),
razsh(K1,R);razsh(K,R).

append([],M,M).
append([X|Y],M,[X|F]):-append(Y,M,F).

Търсенето в дълбочина се базира на следната идея:за да се намери път R от дадено състояние S до някое състояние целево състояние Sn,то:
ако S е целево състояние,то R се състои от S
в противен случай,ако S1 е наследник на S,за което е известно,че от него съществува път R1 до някое целево състояние,то решението R се получава,като S се добави към пътя R1.
R-Път,R1-Път1,S-Състояние,S1-Състояние1.
Ако графът, обхождан от процедурата за търсене в дълбочина ,съдържа цикъл,то програмата ще навлезе в безкраен цикъл. Поради това естественото развитие на програмата изисква наличие на средства за откриване и отсраняване на цикли. За избягване на цикъл изоплзвам следното просто съображение:даден възел не се разглежда, ако той вече се съдържа в пътя от началния до текущия възел. Това съображение се реализира от предиката:
find(път,състояние,решение)
където път е списък от възли на графа от началното до текущото състояние (представено от променливата състояние); решение ще се свърже с получения в крайна сметка списък от възли (включващ и текущите значения на път и състояние) .

deep(H,P):-find([],H,P).
find(V,H,[H|V]):-zel(H).
find(V,H,P1):-nasl(H,H1,_),not(member(H1,V)),
find([H|V],H1,P1).
member(X,[X|_]).
member(X,[_|Y]):-member(X,Y).

Оптималния път за търсене в граф е зададен чрез съвкупност от отношения nasl(възел,възел1,разстояние).Идеята на процедурата се състои в избор на най-добър кандидат за разширяване на високо ниво.Най-добър е кандидатът с минимално тегло на дъгата,свързваща го с непосредствения му предшественик.Списъкът от съседи  се представя в програмата като списък от структури  path(X,Z),където  X е разглежданият кандидат,а Z-разстоянието до текущия възел.Този списък се получава в процеса на работа на optimalen чрез предиката all.

optimalen(P,[P],0):-zel(P).
optimalen(P,[P|T],W):-nasl(P,S,W1),
optimalen(S,T,W2),W is W1 + W2.
all1([P|S],_):-optimalen(P,T,W),
assert(path(T,W)),fail.
all1(_,Sp):-assert(path(0,0)),form1([],Sp).
form1(Sp1,Sp):-izvl1(T,W),!,form1([path(T,W)|Sp1],Sp).
form1(Sp,Sp).
izvl1(T,W):-path(T,W),retract(path(T,W)),
not(W = 0).

min намира пътя с минимална дължина.
min([],path(P,D)):-write(P),write(“-”),write(D).
min([path(P,D)|O],path(P1,M)):-
M > D,min(O,path(P,D)).
min([path(P,D)|O],path(P1,M)):-min(O,path(P1,M)).

pr отпечатва намерения път.
pr([]).
pr([path(P,D)|O]):-write(P),nl,pr(O).

menu дава възможност за избор на дадено действие.
menu:-nl,write(“————-MENU————–”),nl,
write(“Vyvedete 1 za tyrsene v shirina.”),nl,
write(“Vyvedete 2 za tyrsene v dylbo4ina.”),nl,
write(“Vyvedete 3 za optimalno tyrsene.”),nl,
write(“Vyvedete 4 za vsi4ki pytishta.”),nl,
write(“Vyvedete 5 za nova cel.”),nl,
write(“Vyvedete 0 za izhod.”),nl,
write(“——————————-”),nl,
read(I,”Izbor”),go(I).

go-в зависимост от въвъедения избор извиква съответната функция.
go(1):-t_shir(1,W),write(W),menu.
go(2):-deep(1,W),write(W),menu.
go(3):-all1([1],W),min(W,path(P,1000)),menu.
go(4):-all1([1],W),pr(W),menu.
go(5):-read(D,”Vyvedete cel”),zelta(D),menu.
go(0):-!.

Извод:

Търсенето в ширина започва от корена към листата,а при търсенето в дълбочина-от върха.Избира един от наследниците и така вътви надолу до края на пътя.Ако това не е целта се връща назад и търси други пътища.При търсенето на минимален път намира всички пътища по метода на търсенето в дълбична,запомня ги заедно с дължините им и търси пътя,който е с най-малка дължина.

Като цяло езика ПРОЛОГ е подходящо средство за играждане на интелигентни програмни системи.Поради следните негови качества:

• Средствата на езика позволяват да се използвуват термините на съответната проблемна област. Програмирането се приближава до логиката на програмиста в резултат на по-естествените изразни средства за описание на задачите.
• В ПРОЛОГ са вградени средства за автоматичен логически извод на твърдения.
• Лесно се изграждат релационни бази от данни удобно се представят качествени характеристики и отношения.
• Лесно се формират сложни въпроси от логически свързани подвъпроси за отстраняване на общи черти,реализация,противоречия и други,между разглежданите обекти.
• Има възможност за решаване на задачи,предполагащи по-нататъшно прецизиране и доопределяне.

Сходни статии:

1. Двоично търсене, блочно търсене и индексиране Двоичното търсене се основава на разделянето на дадено множество от записи на две равни части, сравняване на търсения идентификатор с последния запис от горната половина или с първия запис от...
2. Свързване на съобщения и методи в C++. Механизъм на «ранното» свързване Стартирането на метод като реакция на определено съобщение трябва да се извършва в съответствие с природата на обекта-получател на съобщението, независимо от това, че този метод може многократно да е...
3. Основни термини на компютърната система Определение за компютърна система-Съвременните компютри са електронни автоматични устройства, работещи на принципа на програмното управление. Те преобразуват данни (цифрови факти) в информация (организирана използваема форма). При това изпълняват функциите управление,...
4. Защитни стени (FireWall). Филтриране на пакети. Система iptables. Методи за предпазване от атаки Известни са няколко основни подхода за защита на достъпа до компютърните мрежи: Без защита. Защита чрез неизвестност (security through obscurity). Защита на ниво хост (host...
5. SEO оптимизация за търсене по изображение SEO оптимизацията за търсачки по изображение е процес на организиране на съдържанието на уеб страница, така че да повиши връзката между специфичните ключови думи на търсачките, които използват изображения. Също,...