Keliaujančio pardavėjo problema
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ę.
Tarkime, kad miestai yra x 1 x 2 ..... x n kur kaina c ij žymi kelionės iš miesto x kainą i prie x j . Keliaujančio pardavėjo problema yra rasti maršrutą, prasidedantį ir baigiant x 1 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 1 tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H 1 .
Pažymėkite sritį H 6 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 1 tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H 6 .
Pažymėkite sritį H 7 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 6 tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H 7 .
Pažymėkite sritį H 8 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 8 .
Pažymėkite sritį H 5 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 5 .
Pažymėkite sritį H 2 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 2 .
Pažymėkite sritį H 3 nes tai yra minimalių sąnaudų plotas, pasiekiamas iš H 3 .
Pažymėkite sritį H 4 tada pasirinkite minimalių sąnaudų sritį, pasiekiamą iš H 4 tai H 1 .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.
