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 x1x2..... xnkur kaina cijžymi kelionės iš miesto x kainąiprie xj. Keliaujančio pardavėjo problema yra rasti maršrutą, prasidedantį ir baigiant x1kad 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:
kainaij=
Ekskursija prasideda nuo H zonos1tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H1.
Pažymėkite sritį H6nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H1tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H6.
Pažymėkite sritį H7nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H6tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H7.
Pažymėkite sritį H8nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H8.
Pažymėkite sritį H5nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H5.
Pažymėkite sritį H2nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H2.
Pažymėkite sritį H3nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H3.
Pažymėkite sritį H4tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H4tai H1.Taigi, naudodamiesi gobšumo strategija, gauname štai ką.
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>.
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:
- S yra baigtinė aibė.
- 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.
- 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) = ∑<sub>x∈A</sub> w(x)
bet kokiam A ∈ S.