Els problemes del venedor ambulant s'acaben d'un venedor i d'un conjunt de ciutats. El venedor ha de visitar cada una de les ciutats començant per una determinada (per exemple, la ciutat natal) i tornar a la mateixa ciutat. El repte del problema és que el venedor ambulant ha de minimitzar la durada total del viatge.

Suposem que les ciutats són x₁x₂..... x_non cost c_ijindica el cost de viatjar des de la ciutat x_ia x_j. El problema del venedor ambulant és trobar una ruta que comenci i acabi a x₁que portarà a totes les ciutats amb el cost mínim.

Exemple: Un agent de premsa diàriament deixa el diari a la zona assignada de manera que ha de cobrir totes les cases de la zona respectiva amb un cost mínim de desplaçament. Calcula el cost mínim del viatge.

convertir int en cadena

L'àrea assignada a l'agent on ha de deixar el diari es mostra a la figura:

Solució: la matriu de cost-adjacència del gràfic G és la següent:

cost_ij=

El recorregut comença des de la zona H₁i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H₁.

Marca l'àrea H₆perquè és l'àrea de cost mínim a què s'arriba des de H₁i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H₆.

hora de sopar vs sopar

Marca l'àrea H₇perquè és l'àrea de cost mínima que es pot arribar des de H₆i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H₇.

java dormir

Marca l'àrea H₈perquè és l'àrea de cost mínima que es pot arribar des de H₈.

Marca l'àrea H₅perquè és l'àrea de cost mínima que es pot arribar des de H₅.

Marca l'àrea H₂perquè és l'àrea de cost mínima que es pot arribar des de H₂.

Marca l'àrea H₃perquè és l'àrea de cost mínim a què s'arriba des de H₃.

Marca l'àrea H₄i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H₄és H₁.Per tant, utilitzant l'estratègia cobdiciosa, obtenim el següent.

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

Així, el cost mínim del viatge = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

arp - una ordre

Matroides:

Un matroide és un parell ordenat M(S, I) que compleix les condicions següents:

1. S és un conjunt finit.
2. I és una família no buida de subconjunts de S, anomenats subconjunts independents de S, tal que si B ∈ I i A ∈ I. Diem que I és hereditari si compleix aquesta propietat. Tingueu en compte que el conjunt buit ∅ és necessàriament un membre de I.
3. Si 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>

Diem que un matroide M (S, I) es pondera si hi ha una funció de pes associada w que assigna un pes estrictament positiu w (x) a cada element x ∈ S. La funció de pes w s'estén a un subconjunt de S per suma. :

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

per a qualsevol A ∈ S.