Problemele vânzătorului ambulant se supun unui vânzător și un set de orașe. Vânzătorul trebuie să viziteze fiecare dintre orașele începând de la unul anume (de exemplu, orașul natal) și să se întoarcă în același oraș. Provocarea problemei este că vânzătorul ambulant trebuie să minimizeze durata totală a călătoriei.

Să presupunem că orașele sunt x ₁ X ₂ ..... X _n unde costă c _ij denotă costul călătoriei din orașul x _i la x _j . Problema agentului de vânzări ambulant este de a găsi o rută care începe și se termină la x ₁ care va lua în toate orașele cu costul minim.

Exemplu: Un agent de ziar aruncă zilnic ziarul în zona alocată în așa fel încât trebuie să acopere toate casele din zona respectivă cu cost minim de călătorie. Calculați costul minim de călătorie.

Zona alocată agentului în care trebuie să arunce ziarul este prezentată în fig:

Rezolvare: Matricea cost-adiacență a graficului G este următoarea:

cost _ij =

Turul începe din zona H ₁ și apoi selectați zona de cost minim accesibilă din H ₁ .

Marcați zona H ₆ deoarece este zona de cost minim accesibilă de la H ₁ și apoi selectați zona de cost minim accesibilă din H ₆ .

Marcați zona H ₇ deoarece este zona de cost minim accesibilă de la H ₆ și apoi selectați zona de cost minim accesibilă din H ₇ .

Marcați zona H ₈ deoarece este zona de cost minim accesibilă de la H ₈ .

Marcați zona H ₅ deoarece este zona de cost minim accesibilă de la H ₅ .

Marcați zona H ₂ deoarece este zona de cost minim accesibilă de la H ₂ .

Marcați zona H ₃ deoarece este zona de cost minim accesibilă de la H ₃ .

Marcați zona H ₄ și apoi selectați zona de cost minim accesibilă din H ₄ este H ₁ .Deci, folosind strategia lacomă, obținem următoarele.

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

Astfel costul minim de călătorie = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

Matroizi:

Un matroid este o pereche ordonată M(S, I) care îndeplinește următoarele condiții:

1. S este o mulțime finită.
2. I este o familie nevidă de submulțimi ale lui S, numite submulțimi independente ale lui S, astfel încât dacă B ∈ I și A ∈ I. Spunem că I este ereditar dacă îndeplinește această proprietate. Rețineți că mulțimea goală ∅ este în mod necesar un membru al lui I.
3. Dacă A ∈ I, B ∈ I și |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>

Spunem că o matroida M (S, I) este ponderată dacă există o funcție de greutate asociată w care atribuie o pondere strict pozitivă w (x) fiecărui element x ∈ S. Funcția de greutate w se extinde la o submulțime a lui S prin însumare. :

 w (A) = &#x2211;<sub>x&#x2208;A</sub> w(x)  

pentru orice A ∈ S.