Problema del venedor ambulant
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 1 x 2 ..... x n on cost c ij indica el cost de viatjar des de la ciutat x i a x j . El problema del venedor ambulant és trobar una ruta que comenci i acabi a x 1 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.
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 1 i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H 1 .
Marca l'àrea H 6 perquè és l'àrea de cost mínim a què s'arriba des de H 1 i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H 6 .
Marca l'àrea H 7 perquè és l'àrea de cost mínima que es pot arribar des de H 6 i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H 7 .
Marca l'àrea H 8 perquè és l'àrea de cost mínima que es pot arribar des de H 8 .
Marca l'àrea H 5 perquè és l'àrea de cost mínima que es pot arribar des de H 5 .
Marca l'àrea H 2 perquè és l'àrea de cost mínima que es pot arribar des de H 2 .
Marca l'àrea H 3 perquè és l'àrea de cost mínim a què s'arriba des de H 3 .
Marca l'àrea H 4 i, a continuació, seleccioneu l'àrea de cost mínim accessible des de H 4 és H 1 .Per tant, utilitzant l'estratègia cobdiciosa, obtenim el següent.
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>.
Així, el cost mínim del viatge = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroides:
Un matroide és un parell ordenat M(S, I) que compleix les condicions següents:
- S és un conjunt finit.
- 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.
- 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) = ∑<sub>x∈A</sub> w(x)
per a qualsevol A ∈ S.
