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₁x₂..... x_nmissä hinta c_ijtarkoittaa matkakustannuksia kaupungista x_ix:lle_j. Matkamyyjän ongelmana on löytää reitti, joka alkaa ja päättyy x:ään₁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₁ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H₁.

Merkitse alue H₆koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₁ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue₆.

Merkitse alue H₇koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₆ja valitse sitten H:sta tavoitettavissa oleva vähimmäiskustannusalue₇.

painike keskittää css

Merkitse alue H₈koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₈.

Merkitse alue H₅koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₅.

Merkitse alue H₂koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₂.

Merkitse alue H₃koska se on pienin kustannusalue, joka on tavoitettavissa H:sta₃.

python tai

Merkitse alue H₄ja valitse sitten tavoitettavissa oleva vähimmäiskustannusalue H₄se on H₁.Joten, käyttämällä ahnetta strategiaa, saamme seuraavan.

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

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:

1. S on äärellinen joukko.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

mille tahansa A ∈ S:lle.