hrvatski

Izračun hamiltonovih ruta zračnog prometa na nakupini računala

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.

Ashay Dharwadkerov algoritam; Hamiltonov problem; Hamiltonove rute; nakupina računala; zrakoplovne rute

nije evidentirano