Sortare si cautare

Sortare si cautare

Metoda de sortare prin generare si testare

Utilizand structura de control a limbajului Prolog, se poate realiza foarte simplu sortarea unei secvente de elemente, folosind metoda generare si testare. Aceasta metoda de rezolvare a problemelor, utilizata in inteligenta artificiala, dar putin potrivita pentru o sortare, are la baza urmatoarea idee: o componenta generatoare construieste solutii candidate si o a doua componenta, componenta de testare, verifica fiecare solutie candidata pentru a vedea daca este sau nu o solutie a problemei. In acest fel, se pot obtine fie toate solutiile problemei, fie una singura. Aceasta metoda poate fi exprimata succint in Prolog astfel:

gaseste(Solutie) :-

genereaza(Solutie),

testeaza(Solutie).

Metoda este in general ineficienta, chiar in cazul problemelor tipice de inteligenta artificiala care necesita un proces de cautare a solutiei. Metoda este extrem de ineficienta in cazul rezolvarii problemelor de sortare, pentru care exista algoritmi eficienti de rezolvare. Cu toate acestea, se prezinta in continuare solutia de sortare in ordine crescatoare a unei liste de intregi prin metoda generare si testare ca exercitiu Prolog.

% sortare(+Lista, -ListaSortata) - sortare prin metoda generare si testare

sortare(Lista, ListaSortata) :-

permut(Lista, ListaSortata), ordonata(ListaSortata).

% permut(+Lista, -PermutareLista)

permut([], []).

permut(Lista, [Prim | Rest]) :- elim(Prim, Lista, L), permut(L, Rest).

% elim(+Element, +Lista, -ListaMinusElement)

elim(Elem, [Elem | Rest], Rest).

elim(Elem, [Prim | Rest], [Prim | L]) :- elim(Elem, Rest, L).

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine rel

rel(X, Y) :- X =< Y.

% ordonata(+Lista) - verifica daca Lista este sortata dupa relatia rel(X, Y)

ordonata([ _ ]).

ordonata([Prim, Secund | Rest]) :-

rel(Prim, Secund), ordonata([Secund | Rest]).

Se observa ca sortarea se face prin generarea permutarilor elementelor din lista si verificarea daca o permutare generata este o secventa sortata. Componenta generatoare este predicatul permut(Lista, ListaSortata) si componenta de testare este predicatul ordonata(Lista).   Desi implementarea este simpla, exploatand facilitatile nedeterministe ale limbajului Prolog, ea este foarte ineficienta

Metoda de sortare prin insertie

Sortarea prin insertie a unei liste de elemente L = [H | T] se poate exprima recursiv astfel: se sorteaza mai intai lista T in TS si apoi se insereaza elementul H in lista TS, acolo unde ii este locul conform relatiei de ordine rel(X, Y).

% isort1(+Lista, -ListaSortata) - sortare prin insertie, varianta 1

isort1([], []) :- !.

isort1([H | T], LS) :- isort1(T, TS), insereaza(H, TS, LS).

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine

rel(X, Y) :- X =< Y.

% insereaza(+Element, +Lista, -ListaPlusElement) -

% insereaza Element in Lista sortata astfel incat

% ListaPlusElement sa ramana sortata

insereaza(Elem, [], [Elem]).

insereaza(Elem, [Prim | Rest], [Elem, Prim | Rest]) :- rel(Elem, Prim), !.

insereaza(Elem, [Prim | Rest], [Prim | L]) :-

not(rel(Elem, Prim)), insereaza(Elem, Rest, L).

Predicatul cut folosit in definirea predicatului insereaza este un cut verde. Se poate rescrie predicatul insereaza folosind un cut rosu astfel:

insereaza(Elem, [], [Elem]).

insereaza(Elem, [Prim | Rest], [Elem, Prim | Rest]) :- rel(Elem, Prim), !.

insereaza(Elem, [Prim | Rest], [Prim | L]) :- insereaza(Elem, Rest, L).

A doua varianta de sortare prin insertie este urmatoarea: Lista poate fi privita la un moment dat ca L' = PS::PN, unde PS este partea sortata si PN = [X | T] este partea nesortata. Se ia primul element X din PN si se insereaza in PS. Algoritmul porneste cu PS = [] si PN = L, si se opreste cand PN = [], in acel moment PS fiind chiar lista sortata. Se observa ca PS are rol de acumulator, rezultatul final fiind intors in al treilea parametru (constructia rezultatului se face pe apelul recursiv).

% isort2(+Lista, -ListaSortata) - sortare prin insertie, varianta 2

isort2(L, LS) :- isort2( [], L, LS).

isort2(PS, [], PS).

isort2(PS, [X | T], LS) :- insereaza(X, PS, PS1), isort2(PS1, T, LS).

Metoda de sortare rapida

Sortarea rapida (quicksort) a unei liste de elemente L se defineste recursiv astfel:

Elimina un element Pivot din lista L si obtine Rest = L - Pivot.

Imparte lista Rest in doua liste: ListaInf, cu toate elementele din Rest inferioare elementului Pivot si ListaSup cu toate lementele din Rest superioare elementului Pivot.

Sorteaza ListaInf si obtine ListaInfSort.

Sorteaza ListaSup si obtine ListaSupSort.

Concateneaza listele ListaInfSort, lista formata din Pivot, ListaSupSort si obtine ListaSortata

Predicatul quicksort(Lista, ListaSortata , definit mai jos, implementeaza acest algoritm. Elementul Pivot este considerat, in implementarea urmatoare, primul element al listei Lista, iar impartirea listei in ListaInf si ListaSup, in functie de elementul pivot se face cu ajutorul predicatului scindeaza(Element, Lista, ListaInf, ListaSup)

% quicksort(+Lista, -ListaSortata) - sortare prin metoda sortarii rapide

quicksort([], []).

quicksort([Pivot | Rest], ListaSortata) :-

scindeaza(Pivot, Rest, L1, L2),

quicksort(L1, L1Sortata), quicksort(L2, L2Sortata),

conc(L1Sortata, [Pivot | L2Sortata], ListaSortata).

% conc(+L1, +L2, -L) - concateneaza listele L1 si L2 in lista L

conc([], L, L).

conc([Prim | Rest], L, [Prim | Rest1]) :- conc(Rest, L, Rest1).

% scindeaza(+Element, +Lista, -ListaInf, -ListaSup) -

% imparte Lista in ListaInf (cu elemente inferioare lui Element)

% si ListaSup (cu elemente superioare lui Element)

% in functie de relatia rel(X, Y)

scindeaza(Elem, [], [], []).

scindeaza(Elem, [Prim | Rest], [Prim | L1], L2) :-

not(rel(Elem, Prim)), !, scindeaza(Elem, Rest, L1, L2).

scindeaza(Elem, [Prim | Rest], L1, [Prim | L2]) :-

rel(Elem, Prim), scindeaza(Elem, Rest, L1, L2).

Sa testam acum implementarile metodelor de sortare prezentate si sa comparam rezultatele lor cu rezultatul produs de predicatul sort, care este predefinit in SWI-Prolog:

% testarea metodelor de sortare

test(F) :-

L = [2, 2, 4, 6, 9, 8, 1, 3, 5, 7, 0], P =.. [F, L, S], call(P), write(P), nl.

test :- test(isort1), test(isort2), test(quicksort), test(sort).

Testarea va decurge astfel:

test.

isort

isort

quicksort

sort

Arbori binari

Consideram urmatoarea reprezentare in Prolog a arborilor binari:

arborele vid este codificat cu nil;

un arbore nevid este codificat cu arb(Cheie, SubarboreStang, SubarboreDrept).

Traversarea unui arbore binar, cu afisarea cheilor din noduri, se implementeaza in Prolog foarte usor folosind facilitatile recursive ale limbajului. Predicatul rsd(Arbore) realizeaza afisarea cheilor din Arbore in ordinea radacina‑stanga‑dreapta.

% rsd(+Arbore) - parcurge arborele binar Arbore

% in ordinea radacina stanga dreapta, afisand cheile arborelui

rsd(nil).

rsd(arb(Radacina, SubarboreStang, SubarboreDrept)) :-

write(Radacina), write(' '),

rsd(SubarboreStang),

rsd(SubarboreDrept).

Daca se considera cazul arborilor binari de cautare (cu chei intregi), se pot defini trei predicate: caut(Cheie, Arbore), de cautare a unei chei in arbore, care reuseste daca cheia este in arbore si esueaza in caz contrar; inser(Cheie, Arbore, ArboreRez), de inserare a unei chei in arbore, cu argumentele Cheie si Arbore instantiate si argumentul ArboreRez sintetizat de program; si elim(Cheie, Arbore, ArboreRez), care sterge o cheie dintr‑un arbore.

% caut(+Cheie, +Arbore) - reuseste daca Cheie este in

% arborele binar de cautare Arbore, esueaza in caz contrar

caut(Cheie, arb(Cheie, _ , _ )) :- !.

caut(Cheie, arb(Radacina, ArbStg, _)) :-

Cheie < Radacina, caut(Cheie, ArbStg).

caut(Cheie, arb(Radacina, _ , ArbDr)) :-

Cheie > Radacina, caut(Cheie, ArbDr).

Prima clauza a predicatului caut reuseste daca cheia este in arbore. Pentru a impiedica o posibila resatisfacere, deci gasirea unei alte aparitii a cheii de cautare in arbore, s‑a introdus in acest caz predicatul cut. Daca se doreste, de exemplu, afisarea tuturor aparitiilor cheii de cautare in arbore, se va elimina acest cut si predicatul caut va avea atatea solutii cate aparitii ale cheii de cautare exista in arbore.

% inser(+Cheie, +Arbore, -ArboreRez) - insereaza Cheie in

% arborele binar de cautare Arbore si produce ArboreRez

inser(Cheie, nil, arb(Cheie, nil, nil)).

inser(Cheie, arb(Cheie, ArbStg, ArbDr), arb(Cheie, ArbStg, ArbDr)):-!.

inser(Cheie, arb(Radacina, ArbStg, ArbDr),

arb(Radacina, ArbStg1, ArbDr)) :-

Cheie < Radacina, !, inser(Cheie, ArbStg, ArbStg1).

inser(Cheie, arb(Radacina, ArbStg, ArbDr),

arb(Radacina, ArbStg, ArbDr1)) :-

Cheie > Radacina, inser(Cheie, ArbDr, ArbDr1).

Predicatul de inserare a unei chei intr‑un arbore de cautare, inser, utilizeaza in definitie un cut verde pentru cresterea eficientei. Se poate elimina conditia Cheie > Radacina, din cea de a treia regula a predicatului inser, caz in care predicatul cut se transforma intr‑un cut rosu. Programul Prolog urmator foloseste definitiile predicatelor caut si inser pentru a implementa mai multe operatii de prelucrare a arborilor binari de cautare.

Eliminarea unei chei dintr-un arbore binar de cautare se face dupa algoritmul standard:

% elim(+Cheie,+Arb,-ArbNou) elimina Cheie din Arb

% cu rezultat in ArbNou

elim(Cheie, nil, nil).

elim(Cheie, arb(Cheie, nil, nil), nil).

elim(Cheie, arb(Cheie, ArbStg, nil), ArbStg).

elim(Cheie, arb(Cheie, nil, ArbDr), ArbDr).

elim(Cheie, arb(Cheie, ArbStg, ArbDr), arb(Cheie1, Stg1, ArbDr)) :-

drept(ArbStg, Cheie1, Stg1),!.

elim(Cheie, arb(Cheie1, ArbStg, ArbDr),

arb(Cheie1, ArbStg1, ArbDr1)) :-

(Cheie < Cheie1, !, elim(Cheie, ArbStg, ArbStg1), ArbDr1=ArbDr) ;

elim(Cheie, ArbDr, ArbDr1), ArbStg1=ArbStg.

% drept(+Arb,-Cheie,-SuccDr) - intoarce cel mai din dreapta nod

% din arborele Arb.

drept(arb(Cheie, ArbStg, nil), Cheie, ArbStg).

drept(arb(Cheie, ArbStg, ArbDr), Cheie1, arb(Cheie, ArbStg, ArbDr1)) :-

drept(ArbDr, Cheie1, ArbDr1).

Se poate defini un meniu de prelucrare arborilor binari de cautare care sa permita executia operatiilor definite anterior, la cerere.

meniu(Arb):- nl,

write('1. Sfarsit'), nl,

write('2. Creeaza arbore'), nl,

write('3. Insereaza o cheie'), nl,

write('4. Cauta o cheie'), nl,

write(' Sterge o cheie'), nl,

write('6. Afiseaza arbore'), nl,

read(Opt), Opt = 1, !, actiune(Opt, Arb, ArbNou), meniu(ArbNou).

meniu( _ ) :- write('Sfarsit'), nl.

actiune(2, Arb, ArbNou) :- creare(Arb, ArbNou).

actiune(3, Arb, ArbNou) :-

write('Introduceti cheia: '), read(Cheie), inser(Cheie, Arb, ArbNou).

actiune(4, Arb, Arb) :-

write('Introduceti cheia: '), read(Cheie),

(caut(Cheie, Arb), write('Cheia a fost gasita');

write('Cheia nu este in arbore')), nl.

actiune(5, Arb, ArbNou) :-

write('Introduceti cheia: '), read(Cheie), elim(Cheie, Arb, ArbNou).

actiune(6, Arb, Arb) :-

write(' In ce ordine? '), read(Ordine), afisare(Arb, Ordine).

creare(Arb, ArbNou) :-

write('Introduceti o cheie, 0 pentru terminare: '), read(Cheie),

Cheie = 0, !, inser(Cheie, Arb, A), creare(A, ArbNou).

creare(Arb, Arb).

% afisare(Arbore, Ordine) - afiseaza cheile arborelui binar Arbore,

% parcurgand arborele in ordinea specificata de Ordine: rsd, srd, sdr

afisare(nil, _ ).

afisare(arb(Radacina, SubarboreStang, SubarboreDrept), Ordine) :-

(Ordine = rsd, write(Radacina), write(' '); true),

afisare( SubarboreStang, Ordine),

(Ordine = srd, write(Radacina), write(' '); true),

afisare( SubarboreDrept, Ordine),

(Ordine = sdr, write(Radacina), write(' '); true).

Afisarea arborilor cu ajutorul predicatului afisare(Arbore, Ordine) se poate face in trei moduri diferite, in functie de valoarea argumentului Ordine: rsd (radacina‑stanga‑dreapta), srd (stanga‑radacina‑dreapta) si sdr (stanga‑dreapta‑radacina). Se observa utilizarea operatorului de disjunctie a scopurilor, cu ajutorul caruia se exprima cele trei modalitati de parcurgere a arborelui. Afisarea repetata a meniului de actiuni este facuta de predicatul meniu(Arb) prin apelul recursiv al acestuia, cat timp nu s-a selectat actiunea Sfarsit. Predicatul are argumentul Arb instantiat. Acesta poate fi initial arborele vid si este actualizat de apelul recursiv la noua valoare ArbNou, care depinde de actiunea selectata In functie de actiunea selectata in NrActiune si de arborele dat Arb, predicatul actiune(NrActiune, Arb, ArbNou) decide care prelucrari sunt necesare pentru a obtine arborele rezultat ArbNou.

Sa vedem acum un predicat de sortare a listelor, care utilizeaza arbori binari de cautare. Predicatul binsort(Lista, ListaSortata) sorteaza lista Lista in lista ListaSortata. El construieste un arbore binar de cautare prin inserarea succesiva a elementelor din Lista cu ajutorul predicatului inser prezentat anterior. ListaSortata   se obtine prin parcurgerea in ordine a arborelui obtinut.

% binsort(+Lista, -ListaSortata)

binsort(L, LSort) :-

constr_arb(L, Tree, nil), write('Arborele este: '), nl,

write(Tree), nl, parc_ord(Tree, LSort, []).

% constr_arb - construieste un arbore binar de cautare

constr_arb([], Acc, Acc) :- !.

constr_arb([K | Rest], Sol, Acc) :-

inser(K, Acc, NoulAcc), constr_arb(Rest, Sol, NoulAcc).

% parc_ord - parcurge in ordine un arbore binar,

% construind lista cheilor sale

parc_ord(nil, Acc, Acc) :- !.

parc_ord(arb(Cheie, Stang, Drept), L, Acc) :-

parc_ord(Drept, L1, Acc), parc_ord(Stang, L, [Cheie | L1]).

Exercitii propuse

EP1. Care este complexitatea timp a algoritmului de sortare prin metoda generare si testare, prezentat in Sectiunea 1 ?

EP2. Comentati asupra complexitatii timp a unei implementari Prolog a algoritmului de cautare binara a unei chei intr‑o lista sortata crescator.

EP3. Scrieti predicatul ssort(-L,+LS) care sorteaza lista L in lista LS conform metodei de sortare prin selectie. La un moment dat lista este L' = PS::PN, unde PS este partea sortata si PN partea nesortata. Se extrage in mod repetat din PN elementul X de valoare minima si se adauga la sfarsitul listei PS. Algoritmul incepe cu PS = [] si PN = L, si se termina cand PN = [], in acel moment PS fiind chiar lista sortata LS. Pentru eliminarea unui element dintr‑o lista si concatenarea a doua liste trebuie sa mai scrieti doua predicate: elim si append. Pentru a evita folosirea lui append se poate extrage maximul din PN la fiecare pas si insera inaintea lui SP.

EP4. Sa se scrie un program Prolog care realizeaza sortarea prin interclasare.

EP O concordanta este o lista de cuvinte care apar intr‑un text, lista sortata in ordine alfabetica impreuna cu numarul de aparitii ale fiecarui cuvant in text. Sa se scrie un program care genereaza o concordanta pornind de la un text dat. Sa se propuna o reprezentare pentru text si o reprezentare pentru concordanta

EP6. Sa se scrie un predicat care elimina o cheie dintr‑un arbore binar de cautare.

EP7. Sa se rescrie predicatul meniu(Arb), inlocuind definitia recursiva a acestuia cu o definitie care utilizeaza predicatul repeat.

EP8. Sa se scrie un predicat Prolog care verifica egalitatea a doi arbori binari, adica daca au aceleasi chei.

EP9. Sa se scrie un predicat Prolog care verifica egalitatea structurala a doi arbori binari, adica daca au aceleasi numar de chei si arata la fel.

EP10. Sa se defineasca o structura Prolog care sa reprezinte un arbore multicai. Sa se scrie un predicat Prolog pentru afisarea unui astfel de arbore.

EP11. Sa se scrie un predicat Prolog care verifica egalitatea a doi arbori multicai.