Problème du voyageur de commerce — circuit hamiltonien optimal

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

5 villes ${A, ..., E}$ , distances données. 1. Circuits distincts depuis $A$ . 2. Coût de $A$ - $B$ - $C$ - $D$ - $E$ - $A$ et $A$ - $B$ - $D$ - $C$ - $E$ - $A$ . 3. Heuristique du voisin le plus proche. 4. Meilleur circuit, optimalité ?

Indices

— clique pour révéler

1 Indice 1

Pour compter les circuits distincts depuis $A$, pense au nombre de facons d'ordonner les 4 villes restantes, en tenant compte du fait qu'un circuit et son sens inverse donnent le meme trajet.

2 Indice 2

Pour calculer le cout d'un circuit donne, additionne simplement les distances des aretes parcourues dans l'ordre indique par le circuit.

3 Indice 3

Pour l'heuristique du plus proche voisin, pars de $A$ et choisis a chaque etape la ville non visitee la plus proche de la ville courante, jusqu'a revenir a $A$.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Problème du pont de Königsberg — généralisation Retour au chapitre Puissance de matrice et chemins de longueur 3

Problème du voyageur de commerce — circuit hamiltonien optimal

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Problème du voyageur de commerce — circuit hamiltonien optimal

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯