Matkustavien myyntihenkilöiden ongelma
Matkamyyjän ongelmat liittyvät myyjään ja joukkoon kaupunkeja. Myyjän on vierailtava jokaisessa kaupungissa tietystä kaupungista alkaen (esim. kotikaupungista) ja palattava samaan kaupunkiin. Ongelman haasteena on se, että matkustavan myyjän tulee minimoida matkan kokonaispituus.
Oletetaan, että kaupungit ovat x 1 x 2 ..... x n missä hinta c ij tarkoittaa matkakustannuksia kaupungista x i x:lle j . Matkamyyjän ongelmana on löytää reitti, joka alkaa ja päättyy x:ään 1 joka ottaa vastaan kaikki kaupungit pienin kustannuksin.
Esimerkki: Sanomalehtien agentti pudottaa sanomalehden päivittäin sille osoitetulle alueelle siten, että hänen on katettava kaikki kyseisen alueen talot minimimatkakuluilla. Laske vähimmäismatkakulut.
Agentille osoitettu alue, jolle hänen on pudotettava sanomalehti, on esitetty kuvassa:
Ratkaisu: Graafin G kustannus-naapurimatriisi on seuraava:
kustannus ij =
Kierros alkaa alueelta H 1 ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H 1 .
Merkitse alue H 6 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 1 ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue 6 .
Merkitse alue H 7 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 6 ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue 7 .
Merkitse alue H 8 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 8 .
Merkitse alue H 5 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 5 .
Merkitse alue H 2 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 2 .
Merkitse alue H 3 koska se on pienin kustannusalue, joka on tavoitettavissa H:sta 3 .
Merkitse alue H 4 ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H 4 se on H 1 .Joten, käyttämällä ahnetta strategiaa, saamme seuraavan.
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>.
Näin ollen vähimmäismatkakulut = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidit:
Matroidi on järjestetty pari M(S, I), joka täyttää seuraavat ehdot:
- S on äärellinen joukko.
- I on ei-tyhjä S:n osajoukkojen perhe, jota kutsutaan S:n itsenäisiksi osajouksiksi siten, että jos B ∈ I ja A ∈ I. Sanomme, että I on perinnöllinen, jos se täyttää tämän ominaisuuden. Huomaa, että tyhjä joukko ∅ on välttämättä I:n jäsen.
- Jos A ∈ I, B ∈ I ja |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Sanomme, että matroidi M (S, I) on painotettu, jos siihen liittyy painofunktio w, joka antaa tiukasti positiivisen painon w (x) jokaiselle elementille x ∈ S. Painofunktio w ulottuu summauksen avulla S:n osajoukkoon :
w (A) = ∑<sub>x∈A</sub> w(x)
mille tahansa A ∈ S:lle.
