Citat:
djoka_l:
Da vidim da li sam razumeo.
Treba da rešiš problem distribucije paketa u 50 čvorova (polazni čvor je nulti i još 50 čvorova).
Svaki čvor je povezan sa svakim drugim čvorom, a rastojanja su data u tabeli.
Ako čvor zahteva n paketa, moraš da mu isporučiš ili n ili 0 (ovo je jako bitno - da li mora porudžbina da se u potpunosti zadovolji ili može i parcijalno).
Ako su ove postavke tačne. Ovako bih ja rešio zadatak:
Prostor stanja su sve permutacije 50 elemenata.
Na primer, ako je permutacija (23 47 3 ... ) to bi značilo da se iz polaznog čvora dođe u čvor 23 pa 47 sve dok ima robe, pa onda nazad u 0 kada se kamion isprazni.
Da bih smanjio prostor, na početku bih naređao prvo sve čvorove kojima treba 0 paketa, jer u njih ne treba da se ide, pa je dužina puta do njih 0. Neka je tih čvorova k. Od preostalih 50-k se napravi permutacija pa se onda vidi koliki je ukupan put.
Nova tačka se traži tako što se od onih 50-k nenultih čvorova zamene, pa se ponovo izračuna put.
Za računanje puteva bi se koristi Dijkstrin algoritam za računanje najkraćeg puta u grafu.
Polazni cvor je definisan koordinatama [10,20], ali mogu i da se postave drugacije. To je kao magacin iz koga se krece i u koji treba da se vraca kada isporuci do 10 paketa koliki je maksimalni kapacitet.
Rastojanaj mogu iz tabele ili eventualno an osnovu zadatih koordinata koje isto tako mogu da se menjaju.
Treba porudzbina da se zadovolji u potpunosti, ali i mene ovo malo buni posto je pitanje da li prioritet treba zaista dati potpunoj isporuci ako se trazi najkraca ruta.
Ipak bih radio sa potpunom isporukom koja ce se uraditi najkracom mogucom rutom.
poptuno se slazem sa tobom oko permutacije 50 elemenata.
Za racunanje puteva mislim da nije bas neophodan ovaj algoritam.
Imas li nesto slicno vec uradjeno i kakva je sansa da mi kazes ako vec postoje gotove biblioteke pa da probam da ih upakujem.
ja evo uspeo nesto sa gotovim softverom VRPH, ali bih voleo da dam ulazni fajl kroz command prompt, a bas mi i ne ide.