Problém s cestujúcim predajcom
Problémy cestujúceho obchodníka dodržiava obchodník a súbor miest. Predajca musí navštíviť každé z miest počnúc určitým (napr. rodným mestom) a vrátiť sa do toho istého mesta. Problémom tohto problému je, že cestujúci predávajúci musí minimalizovať celkovú dĺžku cesty.
Predpokladajme, že mestá sú x 1 X 2 ..... X n kde cena c ij označuje náklady na cestu z mesta x i do x j . Problémom cestujúceho predajcu je nájsť trasu začínajúcu a končiacu na x 1 ktoré zaberú všetky mestá s minimálnymi nákladmi.
Príklad: Novinový agent denne hodí noviny do pridelenej oblasti tak, že musí pokryť všetky domy v príslušnej oblasti s minimálnymi cestovnými nákladmi. Vypočítajte minimálne cestovné náklady.
Oblasť pridelená agentovi, kde má hodiť noviny, je znázornená na obr.
Riešenie: Matica nákladovej susednosti grafu G je nasledovná:
náklady ij =
Prehliadka začína z oblasti H 1 a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H 1 .
Označte oblasť H 6 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 1 a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H 6 .
Označte oblasť H 7 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 6 a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H 7 .
Označte oblasť H 8 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 8 .
Označte oblasť H 5 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 5 .
Označte oblasť H 2 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 2 .
Označte oblasť H 3 pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H 3 .
Označte oblasť H 4 a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H 4 je to H 1 .Takže pomocou chamtivej stratégie dostaneme nasledovné.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Teda minimálne cestovné náklady = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidy:
Matroid je usporiadaný pár M(S, I) spĺňajúci nasledujúce podmienky:
- S je konečná množina.
- I je neprázdna rodina podmnožín S, nazývaných nezávislé podmnožiny S, takže ak B ∈ I a A ∈ I. Hovoríme, že I je dedičné, ak spĺňa túto vlastnosť. Všimnite si, že prázdna množina ∅ je nevyhnutne členom I.
- Ak A ∈ I, B ∈ I a |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Hovoríme, že matroid M (S, I) je vážený, ak existuje asociovaná váhová funkcia w, ktorá priraďuje striktne kladnú váhu w (x) každému prvku x ∈ S. Váhová funkcia w sa rozširuje na podmnožinu S súčtom :
w (A) = ∑<sub>x∈A</sub> w(x)
pre akékoľvek A ∈ S.
