Rešitev: Raznašalca (Algoritem)

Iz MaFiRaWiki

Naloga: Raznašalca

Algoritem bomo načrtovali s požrešno metodo. Na vsakem koraku bomo izbrali najboljšo delno rešitev.

Na začetku sta oba raznašalca v točki w0. Na vsakem koraku se moramo odločiti, katerega raznašalca bomo poslali v naslednjo točko. Na prvem koraku je vseeno katerega izberemo. Na vsakem naslednjem izberemo tistega, ki je tej točki bližje.

Primer

Katere točke mora obiskati kateri raznašalec, če so točke razporejene kot na spodnji sliki? Številke nad (pod) povezavami predstavljajo razdaljo med točkama. En raznašalec prehodi rdeče povezave, drug pa modre(o).

Imamo raznašalca R (rdeči) in M (modri). Na začetku sta oba v točki a. Najprej R pošljemo v točko b. R je od točke c oddaljen 3 enote, M pa 7. Zato gre R v točko c. Sedaj je R od točke d oddaljen 6 enot, M pa 2. Zato gre M v točko d in je od točke e oddaljen 8 enot, R pa 4. Torej gre R v točko e. Tako so obiskane vse točke.

Osebna orodja