Problème de vendeur itinérant
Les problèmes du voyageur de commerce dépendent d'un vendeur et d'un ensemble de villes. Le vendeur doit visiter chacune des villes en commençant par une certaine (par exemple, la ville natale) et revenir dans la même ville. Le défi du problème est que le voyageur de commerce doit minimiser la durée totale du voyage.
Supposons que les villes soient x 1 X 2 ..... X n où coûte c je désigne le coût du voyage depuis la ville x je à x j . Le problème du voyageur de commerce est de trouver un itinéraire commençant et se terminant à x 1 cela prendra dans toutes les villes avec le coût minimum.
Exemple: Un agent de presse dépose quotidiennement le journal dans la zone assignée de telle manière qu'il doit couvrir toutes les maisons de la zone concernée avec un coût de déplacement minimum. Calculez le coût minimum du voyage.
La zone attribuée à l'agent où il doit déposer le journal est représentée sur la fig :
Solution : La matrice coût-adjacence du graphique G est la suivante :
coût je =
La visite commence à partir de la zone H 1 puis sélectionnez la zone de coût minimum accessible depuis H 1 .
Marquer la zone H 6 car c'est la zone de coût minimum accessible depuis H 1 puis sélectionnez la zone de coût minimum accessible depuis H 6 .
Marquer la zone H 7 car c'est la zone de coût minimum accessible depuis H 6 puis sélectionnez la zone de coût minimum accessible depuis H 7 .
Marquer la zone H 8 car c'est la zone de coût minimum accessible depuis H 8 .
Marquer la zone H 5 car c'est la zone de coût minimum accessible depuis H 5 .
Marquer la zone H 2 car c'est la zone de coût minimum accessible depuis H 2 .
Marquer la zone H 3 car c'est la zone de coût minimum accessible depuis H 3 .
Marquer la zone H 4 puis sélectionnez la zone de coût minimum accessible depuis H 4 c'est H 1 .Donc, en utilisant la stratégie gourmande, nous obtenons ce qui suit.
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>.
Ainsi le coût minimum du voyage = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroïdes :
Un matroïde est une paire ordonnée M(S, I) satisfaisant les conditions suivantes :
- S est un ensemble fini.
- I est une famille non vide de sous-ensembles de S, appelés sous-ensembles indépendants de S, tels que si B ∈ I et A ∈ I. On dit que I est héréditaire s'il satisfait cette propriété. Notez que l'ensemble vide ∅ est nécessairement membre de I.
- Si A ∈ I, B ∈ I et |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
On dit qu'un matroïde M (S, I) est pondéré s'il existe une fonction de poids w associée qui attribue un poids w (x) strictement positif à chaque élément x ∈ S. La fonction de poids w s'étend à un sous-ensemble de S par sommation :
w (A) = ∑<sub>x∈A</sub> w(x)
pour tout A ∈ S.
