Inteligenta artificiala

Extras din referat Cum descarc?

1. Cautarea de tip breadth-first. Prezentare generala si implementare in Prolog
Prezentare generala:
Strategia de cautare de tip BF extinde mai intai nodul radacina, apoi se extind toate nodurile generate de nodul radacina, apoi succesorii lor, si asa mai departe. Nodurile aflate la adancimea d in arbore sunt extinse inaintea nodurilor aflate la adancimea d+1. Spunem ca aceasta cautare este o cautare in latime.
Cautarea BF este un tip de cautare neinformata, adica nu se cunosc pasii sau costul drumului de la starea curenta la starea scop. Cautarea BF este completa si optima cu conditia ca costul drumului sa fie o functie descrescatoare de adancime a nodului.
Aceasta cautare este sistematica fiindca ia in consideratie toate drumurile de lungime 1, de lungime 2, samd. Daca exista o solutie, este sigur ca va fi gasita, iar daca exista mai multe, se va gasi intotdeauna solutia cea mai putin adanca.
Complexitate timp si spatiu: O(bd), unde b=nr de stari noi, iar d=lungimea drumului solutiei
Implementare in Prolog:
Pentru a programa in Prolog aceasta strategie este nevoie de o multime de noduri candidate, care vor forma o multime de drumuri candidate. Aceasta multime va fi reprezentata ca o lista de drmuri, iar in fiecare drum va fi o lista de noduri in ordine inversa. Capul listei fiind nodul cel mai recent generat, iar ultimul element este nodul de unde s-a inceput cautarea.
Cautarea este inceputa cu o multime de candidati avand un singur element: [[NodStart]].
Strategia BF este:
- daca primul drum contine un nod-scop pe post de cap, atunci aceasta este o solutie a problemei.
- altfel, inlatura primul drum din multimea de candidati, si genereaza toate extensiile de un pas ale acestui drum, care se adauga la sfarsitul multimii pe care se va face cautarea BF.
Cod:
%concat(+Lista1,+Lista2,-Listarez)
concat([],L,L).
concat([H|T],L,[H|T1]):-concat(T,L,T1).
%membru(+Element,+Lista)
membru(H,[H|_]).
membru(X,[_|T]):-membru(X,T).
%rezolva_b(+Start,- Sol)
rezolva_b(Start, Sol):-breadthfirst([[Start]],Sol).
%breadthfirst(+Listadrumuri,-DrumSolutie)
breadthfirst([[Nod|Drum]|_], [Nod|Drum]):- scop(Nod).
breadthfirst([Drum|Drumuri], Sol) :- 
extinde(Drum, DrumuriNoi),
concat(Drumuri, DrumuriNoi, Drumuri1),
breadthfirst(Drumuri1, Sol).
%extinde(+StareDrum,-ListaDrumuriDerivate)
extinde([Nod|Drum],DrumuriNoi):-
bagof([NodNou,Nod|Drum], (s(Nod,NodNou), +(membru(NodNou,[Nod|Drum]))),
DrumuriNoi),
!.
extinde(_,[]).
rezolva_b(+Start,- Sol):- este adevarat daca Sol este un drum (in ordine inversa) de la nodul Start la un nod scop.
breadthfirst(+Listadrumuri,-DrumSolutie):- este adevarat daca un drum din multimea de noduri candidate Drumuri1 poate fi extins la o stare scop, rezultand Sol.
concat(+Lista1,+Lista2,-Listarez):- este adevarat daca, atunci cand concatenam Drumuri cu DrumuriNoi rezulta Drumuri1.
membru(+Element,+Lista):- este adevarat daca NodNou apartine listei [Nod|Drum].
scop(Nod):- este adevarata daca Nod este scop al cautarii.
s(Nod,NodNou):- este functia de succesiune si desemneaza faptul ca NodNou este succesor al Nod.
2. Cautarea de tip depth-first. Prezentare generala si implementare in Prolog
Prezentare generala:
Cautarea de tip depth-first este o caurate de tip neinformata. Ea extinde intotdeauna unul dintre nodurile alfate la nivelul cel mai adanc din arbore. Cautarea se intoarce inapoi si sunt extinse noduri de la adancimi mai mici doar daca a fost atins un nod care nu e scop si nu mai poate fi extins. Spunem ca aceasta este o cautare in adancime.
Necesitatile de memorie sunt foarte mici deoarece se memoreaza un singur drum de la radacina la nod-frunza, impreuna cu nodurile frate neextinse. 
Dpdv al complexitatii spatiu, pentru un spatiu al starilor cu factor de ramificare b si m adancime maxima, vom memora doar bm noduri. Complexitatea timp este O(bm) inclusiv in cazul cel mai nefavorabil. 
Dezavantaje:
- poate intra in ciclu infinit (rezolvabil prin adaugarea unui test de apartenta)
- poate gasi ca solutie un drum de lungime mai mare decat cel optim
- nu e nici complet nici optim
Avantaje:
- consum redus de memorie
- posibilitatea gasirii unei solutii fara a se explora o mare parte din spatiul de cautare 
Implementare in Prolog:
Strategia depth-first este cea care se potriveste cel mai bine cu stilul de programare recursiv din Prolog. Strategia gasirii unui drum solutie de la un nod dat,N, pana la un nod scop este:
- daca N este un nod scop, atunci Sol=[N]
- altfel, daca exista un nod N1, succesor al lui N, astfel incat sa existe un drum , Sol1, de la N1 la un nod-scop , atunci Sol=[N|Sol1].
Cod fara mecanism de detectare a ciclurilor:
%rezolva_d(+Nod,-DrumSolutie)
rezolva_d(N,[N]):-scop(N).
rezolva_d(N,[N|Sol1]):-s(N,N1), rezolva_d(N1,Sol1).
rezolva_d(+Nod,-DrumSolutie):- este adevarat daca Sol este un drum de la Nod la un nod scop, insa poate rula la infinit in cazul ciclurilor
Cod cu mecanism de detectare a ciclurilor:
%membru(+Element,+Lista)
membru(H,[H|_]).
membru(X,[_|T]):-membru(X,T).
%rezolva_d(+Nod,-DrumSolutie)
rezolva_d(N,Sol):-depthfirst([],N,Sol).
%depthfirst(+Drum,+Nod, -Solutie)
depthfirst(Drum, Nod, [Nod|Drum]):-scop(Nod).
depthfirst(Drum, Nod, Sol):-
s(Nod,Nod1),
+ (membru(Nod1,Drum)), 
depthfirst([Nod|Drum],Nod1, Sol).
%rezolva_d(+Nod,-DrumSolutie):- este adevarat daca DrumSolutie este un drum de la Nod la un nod scop; va intoarce in DrumSolutie, drumul gasit intre Nod si un nod scop in ordine inversa.
depthfirst(+Drum,+Nod, -Solutie):- este varianta imbunatatita a programului, avand un mecanism de detectare a ciclurilor; aici Nod este starea de la care trebuie sa pornim spre o stare scop, Drum este lista de noduri intre cel de start si Nod, iar Solutie este Drum extins via Nod spre un nod scop.
membru(+Element,+Lista):- este adevarat daca Element apartine listei [Lista].
3. Cautarea in adancime iterativa. Prezentare generala si implementare in Prolog
Prezentare generala:
Cautarea in adancime iterativa este o cautare de tip neinformata. Reprezinta este o strategie care evita chestiunea stabilirii unei adancimi optime la care trebuie cautata solutia, prin testarea tuturor limitelor de adancime posibile: mai intai adancimea 0, apoi 1, etc. Acesti tip de cautare imbina beneficiile DF si BF:
- este optima si completa (BF)
- consuma cantitate mica de memorie (DF) deoarece cerinta de memorie este liniara
Ordinea extinderii este aceeasi ca la cautarea BF, numai ca anumite ramuri sunt extinse de mai multe ori. Strategia garanteaza gasirea nodului scop de la adancime minima, daca acesta exista. In general, este preferata atunci cand exista un spatiu al cautarii foarte mare, iar adancimea solutiei nu e cunoscuta.


Fisiere in arhiva (1):

  • Inteligenta artificiala.docx

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!