UCSearch je komponenta koja predstavlja implementaciju algoritma za pretragu grafa. Implementirani algoritam u ovoj komponenti je Uniform Cost Search algoritam. Ova komponenta bi trebalo da korisniku omogući pronalazak najjeftinijeg puta od starta do cilja. Malo opširniji opis algoritma sledi u tekstu.
Pretraga se
može pokrenuti na vše načina:
·
Odabirom
akcije UCSearch na toolbaru glavnog prozora aplikacije
·
Odabirom
akcije UCSearch na padajućem meniju glavnog prozora aplikacije
·
Pokretanjem
pretrage iz konzole programa sledećom sintaksom: ucs <startni_čvor>
<ciljni_čvor> ili ucs <startni_čvor> <ciljni_čvor>
-a <ime težinskog atributa>
Napomena:
Treći način pokretanja pretrage moguć je samo ukoliko program sadrži i Console
komponentu u aplikaciji.
Pre pokretanja same pretrage, korisnik je dužan da unese parametre za pretragu:
·
Polje: From node – Iz padajućeg menija korisnik treba da odabere
startni čvor za pretragu
· Polje: To node – Iz padajućeg manija korisnik treba da odabere ciljni čvor za pretragu
· Polje: Attribute – U polje korisnik treba da unese naziv težinskog atributa za pretragu
Napomena: Startni i ciljni čvor su obavezni parametri za pretragu dok naziv težinskog atributa nije.
Ukoliko korisnik ne unese naziv ili pak pogrešno unese naziv težinskog atributa (TA) za pretragu program će pokušati da sprovede pretragu koristeći pretpostavljeni naziv TA a to je Weight. Ukoliko u toku izvršavanja pretraga naiđe na vezu koja ne sadrži traženi TA uzeće pretpostavljenu (neutralnu) vrednost a to je 1.
Po potvrdi unetih parametara (klik na dugme OK) program će izvršiti pretragu nad trenutno aktuelnim grafom i ako ga pronađe, prijaviti korisniku rezultat pretrage.
Ukoliko pretraga ne vrati nikakav rezultat korisnik će i o tome biti obavešten.
Sintaksa za
pokretanje pretrage preko konzole je sledeća:
·
ucs <startni_čvor> <ciljni_čvor>
·
ucs <startni_čvor> <ciljni_čvor> -a <ime težinskog
atributa>
Prvi način pokretanja pretrage izvršiće pretragu nad trenutno aktivnim grafom u konzoli koristeći pretpostavljeni naziv TA.
Drugi način pokretanja pretrage izvšiće pretragu takođe nad aktivnim grafom u konzoli ali koristeći uneto ima TA kao atribut iz koga će pokušati da dodje do težinskog faktora. Ukoliko uneti TA ne postoji u čvorovima biće izvšena ista procedura kao što je opisano i u prethodnom odeljku.
Ovaj
algoritam pronalazi najjeftiniju putanju između startnog i ciljnog čvora. Kao
težinski faktor na osnovu kojeg će odlučiti koji čvor će sledeće da obiđe
algoritam koristi težinu (povoljnost, cenu) grane koja vodi do tog čvora.
Algoritam, počavši od startnog čvora razvija sve čvorove povezane sa trenutnim
čvorom i ređa ih po težinskom faktoru u listu, iz koje nakon svakog razvoja, za
trenutni čvor uzima čvor sa najjeftinijom putanjom u toj listi. Algoritam
razvija čvor po čvor sve dok ne dođe do ciljnog čvora. Nakon što je došao do
ciljnog čvora algoritam se vraća korak po korak unazad odnosno na čvorove sa
kojih je došao ne tekući čvor i tako formira pronadjenu putanju koju na kraju
prijavljuje kao rezultat pretrage.