Keliaujančio pardavėjo problemos kyla dėl pardavėjo ir miestų rinkinio. Pardavėjas turi aplankyti kiekvieną miestą, pradedant nuo tam tikro (pvz., gimtojo miesto) ir grįžti į tą patį miestą. Problemos iššūkis yra tas, kad keliaujantis pardavėjas turi sumažinti bendrą kelionės trukmę.

do while ciklas java

Tarkime, kad miestai yra x₁x₂..... x_nkur kaina c_ijžymi kelionės iš miesto x kainą_iprie x_j. Keliaujančio pardavėjo problema yra rasti maršrutą, prasidedantį ir baigiant x₁kad užims visus miestus su minimaliomis išlaidomis.

Pavyzdys: Laikraščio agentas kasdien numeta laikraštį į paskirtą zoną taip, kad su minimaliomis kelionės išlaidomis jis turi padengti visus atitinkamo ploto namus. Apskaičiuokite minimalias kelionės išlaidas.

Agentui priskirta sritis, kurioje jis turi mesti laikraštį, parodyta pav.

Sprendimas: Grafo G sąnaudų gretimumo matrica yra tokia:

kaina_ij=

Ekskursija prasideda nuo H zonos₁tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H₁.

Pažymėkite sritį H₆nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₁tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H₆.

Pažymėkite sritį H₇nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₆tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H₇.

Pažymėkite sritį H₈nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₈.

Pažymėkite sritį H₅nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₅.

Pažymėkite sritį H₂nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₂.

Pažymėkite sritį H₃nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H₃.

Pažymėkite sritį H₄tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H₄tai H₁.Taigi, naudodamiesi gobšumo strategija, gauname štai ką.

 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>. 

Taigi minimali kelionės kaina = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

Matroidai:

Matroidas yra sutvarkyta pora M(S, I), atitinkanti šias sąlygas:

1. S yra baigtinė aibė.
2. I yra netuščia S poaibių šeima, vadinama nepriklausomais S poaibiais, kad jei B ∈ I ir A ∈ I. Sakome, kad aš yra paveldimas, jei jis atitinka šią savybę. Atkreipkite dėmesį, kad tuščia aibė ∅ būtinai yra I narys.
3. Jei A ∈ I, B ∈ I ir |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>

Sakome, kad matroid M (S, I) yra pasvertas, jei yra susijusi svorio funkcija w, kuri kiekvienam elementui x ∈ S priskiria griežtai teigiamą svorį w (x). Svorio funkcija w apima S poaibį sumuojant. :

 w (A) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

bet kokiam A ∈ S.