[nastava:2003] - Re: pitanje iz ekspertskih by Nenad Rogulja <npress@galeb.etf.bg.ac.yu>

Zdravo,
mislim da su algoritmi obilazenja u globalu potpuno identicni onim iz 
struktura.
A evo sta tebe najverovatnije buni. (ili kako jos vise da te zbunim :))

Ovde (u ES) se vodi evidencija obilazenja iz dva razloga. U strukturama si 
imao evidentiranje putovanja kroz stablo/graf samo da bi znao gde da se 
vratis (ako zapadnes u corsokak, otprilike :)), a neku pseudo proceduru 
P(cvor) (Process)za obradjivanje cvora. U ekspertskim je to P(cvor) shvati 
kao Poseti(cvor), naime bitno je PRETRAZIVANJE (celog) grafa/stabla 
pretrage. I pri pretrazivanju nema ciklusa, ali...
Pri definiciji STABLA pretrazivanja se kaze da se cvorovi stabla dobijaju 
ekspandovanjem tekuceg i tako sirimo nase stablo (tacno kako, govori 
algoritam pretrazivanja). Tu mogu biti ISTOIMENI cvorovi /u stablu 
pretrage/ (u grafu ne mogu, ali tu imamo cikluse), ali bez ciklusa. Pa sad 
dodatno stvar komplikuje dinamicko programiranje u npr. A* pretrazivanju 
koje eliminise neoptimalne putanje do istoimenih cvorova.



> Kada se radi pretrazivanje u sirinu i dubinu, koliko sam shvatio iz 
> zbirke,
> ne pamti se koji su cvorovi vec nadjeni?
> To otprilike znaci da ako postoji neki ciklus u grafu tih cvorova (koji
> predstavljaju neka stanja) a ciljni cvor nije dostizan, da ce algoritam
> vecno da se vrti u petlji.
Nisi bas jasan. Razdvoj dva "pamcenja" ono sto je pretrazeno od reda/steka 
koji sluzi za povratak u sucaju corsokaka. 3. korak algoritma kaze: Ako je 
pronadjen ciljni cvor, pretraga je uspesno zavrsena, u suprotnom pretraga 
je neuspesna! A pri  koraku 2.2 "dodati njegove sledbenike iz stabla 
pretrage" se podrazumeva zdravorazumski da u skup sledbenika ne ide onaj 
cvor PREKO KOGA SI DOSAO do tekuceg, pa nema petlje. Sto vazi za SVE 
algoritme pretrage.
> Algoritam pretrage u sirinu i dubinu za grafove, koji smo radili npr. na
> strukturama podataka, pamti kada ce pronadje neki cvor i algoritam uvek
> zavrsava.
Da ali, ako graf nije povezan, ne obilazi obavezno sve corove grafa/stabla 
vec je potreban restart sa neposecenim ... (ali mislim da to nema veze sa 
onim sto tebe buni)
> Ovo nije bas najjasnije u zbirci, posto se u nekim zadacima radi ovako 
> kako
> sam prvo naveo (bez pracenja sta je vec nadjeno) a u nekim naprasno kaze 
> "da
> ne bi doslo do ciklusa ne razmatramo" neko tamo stanje.
To je to, ne razmatramo onaj preko koga si dosao...
> Meni je potpuno nelogicno i glupo da se ove pretrage rade bez pamcenja.
> Da li neko zna kako treba da se radi na ispitu iz ekspertskih sistema?
>
> Hvala,
> Milan

Naravno da se ne sme dozvoliti da bilo koji algoritam bilo kada zapadne u 
beskonacnu petlju (sem u rezoluciji sa netacnim tvrdjenjem :)).

Ako imas konkretno pitanje, sta te buni, pucaj!

--

Pozdrav,
Nenad Rogulja