UCSearch

Osnovni opis:

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.

Pokretanje pretrage:

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.

Pokretanje pretrage preko prozora:

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.

Pokretanje pretrage preko konzole:

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.

Kratak opis Uniform Cost Search algoritma:

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.