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₁X₂..... X_noù coûte c_jedé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₁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₁puis sélectionnez la zone de coût minimum accessible depuis H₁.

meilleure automobile du monde

Marquer la zone H₆car c'est la zone de coût minimum accessible depuis H₁puis sélectionnez la zone de coût minimum accessible depuis H₆.

Marquer la zone H₇car c'est la zone de coût minimum accessible depuis H₆puis sélectionnez la zone de coût minimum accessible depuis H₇.

Marquer la zone H₈car c'est la zone de coût minimum accessible depuis H₈.

Marquer la zone H₅car c'est la zone de coût minimum accessible depuis H₅.

Marquer la zone H₂car c'est la zone de coût minimum accessible depuis H₂.

Marquer la zone H₃car c'est la zone de coût minimum accessible depuis H₃.

Marquer la zone H₄puis sélectionnez la zone de coût minimum accessible depuis H₄c'est H₁.Donc, en utilisant la stratégie gourmande, nous obtenons ce qui suit.

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

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 :

générer un nombre aléatoire en Java

1. S est un ensemble fini.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

pour tout A ∈ S.