NSI (terminale) · Chapitre 8 · Exercice d'entraînement
Le voyageur et le plus proche voisin
Les algorithmes gloutons · Quand le glouton n'est qu'une heuristique · niveau 2
Énoncé
Le voyageur et le plus proche voisin.
Un livreur part de la ville A, doit passer une fois par chacune des autres villes, puis revenir en A, en parcourant la plus petite distance totale. Les villes sont situées le long d'une même route, aux kilomètres suivants :
villes = {"A": 0, "B": 1, "C": -2, "D": 5, "E": -6}- Heuristique du plus proche voisin : depuis la ville courante, aller toujours à la ville non visitée la plus proche. Appliquer cette heuristique depuis
Aet calculer la longueur de la tournée. - Trouver une tournée plus courte. Le plus proche voisin est-il optimal ?
- Écrire une fonction
plus_proche_voisin(villes, depart)et comparer avec l'essai de toutes les tournées. Pourquoi utilise-t-on malgré tout ce genre d'heuristique ?
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.