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.

expertné systémy

Predpokladajme, že mestá sú x₁X₂..... X_nkde cena c_ijoznačuje náklady na cestu z mesta x_ido x_j. Problémom cestujúceho predajcu je nájsť trasu začínajúcu a končiacu na x₁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=

príklad podreťazca java

Prehliadka začína z oblasti H₁a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H₁.

Označte oblasť H₆pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₁a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H₆.

Označte oblasť H₇pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₆a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H₇.

čo je rom

Označte oblasť H₈pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₈.

Označte oblasť H₅pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₅.

Označte oblasť H₂pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₂.

Označte oblasť H₃pretože ide o minimálnu nákladovú oblasť dosiahnuteľnú z H₃.

gzip pre linux

Označte oblasť H₄a potom vyberte minimálnu nákladovú oblasť dosiahnuteľnú z H₄je to H₁.Takže pomocou chamtivej stratégie dostaneme nasledovné.

 4 3 2 4 3 2 1 6 H<sub>1</sub> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <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:

1. S je konečná množina.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

pre akékoľvek A ∈ S.