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 x1x2..... xnmissä hinta cijtarkoittaa matkakustannuksia kaupungista xix:llej. Matkamyyjän ongelmana on löytää reitti, joka alkaa ja päättyy x:ään1joka 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:
kustannusij=
Kierros alkaa alueelta H1ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H1.
Merkitse alue H6koska se on pienin kustannusalue, joka on tavoitettavissa H:sta1ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue6.
Merkitse alue H7koska se on pienin kustannusalue, joka on tavoitettavissa H:sta6ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue7.
painike keskittää css
Merkitse alue H8koska se on pienin kustannusalue, joka on tavoitettavissa H:sta8.
Merkitse alue H5koska se on pienin kustannusalue, joka on tavoitettavissa H:sta5.
Merkitse alue H2koska se on pienin kustannusalue, joka on tavoitettavissa H:sta2.
Merkitse alue H3koska se on pienin kustannusalue, joka on tavoitettavissa H:sta3.
python tai
Merkitse alue H4ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H4se on H1.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.