Naslov
Izračun hamiltonovih ruta zračnog prometa na nakupini računala
(Claculation of Hamilton Airplane Routes on Computational Cluster)

Autori
Birovljević, Damir

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Elektrotehnički fakultet Osijek

Mjesto
Osijek

Datum
11.02

Godina
2008

Stranica
54

Mentor
Martinović, Goran

Neposredni voditelj
Martinović, Goran

Ključne riječi
Ashay Dharwadkerov algoritam; Hamiltonov problem; Hamiltonove rute; nakupina računala; zrakoplovne rute
(Airplane routes; Ashay Dharwadker's algorithm; Cluster; Hamiltonian problem; Hamiltonian routes)

Sažetak
Ukoliko netko zrakoplovom želi posjetiti određeni skup gradova uz uvjet da isti grad ne posjeti više od jednom, potrebno je izračunati Hamiltonovu rutu za taj skup gradova. Zbog velike računalne zahtjevnosti problema, korištena je nakupina računala. Razvijen je automatizirani sustav zasnovan na web sučelju preko kojeg korisnik vrši podešavanje načina rada, te dobiva rješenja u obliku popisa i u grafičkom obliku karte s ucrtanom rutom. Osim skupa gradova i početnog grada, korisnik definira broj procesora i algoritam za izračun ruta. Tri algoritma su implementirana u sustav. Prvi algoritam, nazvan NP algoritam, zasnovan je na pronalasku svih varijacija skupa odabranih gradova, te pronalasku mogućih ruta u tim varijacijama. Drugi algoritam je nazvan BC (engl. Branch and Cut), jer razvija stablo svih varijacija i čim pronađe nepovezane čvorove, eliminira cijelu granu i sve varijacije koje se vežu na nju. Treći algoritam, NEW, kojeg je razvio Dharwadker, za sve moguće susjede trenutnog čvora, pronalazi daljnje susjede, te prati koji su čvorovi već posjećeni. Na taj način ne pronalazi sve moguće rute, ali ukoliko barem jedna ruta postoji, bit će pronađena. Rezultati ispitivanja su pokazali da BC algoritam uvijek daje potpuno rješenje u znatno kraćem vremenu nego NP algoritam, koji također daje potpuno rješenje, te time ne postoji razlog za korištenje NP algoritma. Algoritam NEW preporučuje se ukoliko je bitno dobiti barem jednu rutu u što kraćem vremenu, a ukoliko je bitno imati sve moguće rute preporučuje se koristiti BC algoritam.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA