Rešitev: Raznašalca (Algoritem)

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 22:07, 26 junij 2007
LucijanPlevnik (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
212.235.177.79 (Pogovor | prispevki)

Vrstica 1: Vrstica 1:
[[Naloga: Raznašalca]] [[Naloga: Raznašalca]]
- +{{V delu}}
-Algoritem bomo načrtovali s [[Požrešna metoda|požrešno metodo]]. Na vsakem koraku bomo izbrali najboljšo delno rešitev.+
- +
-Na začetku sta oba raznašalca v točki <math>w_0</math>. 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= =Primer=

Trenutna različica

Naloga: Raznašalca

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

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