Nous introduisons dans ce cours la notion d’algorithme approché. Un algorithme approché propose une solution non exacte, mais possiblement proche de la solution exacte. L’avantage d’un bon algorithme approché est qu’il s’exécute bien plus rapidement.
Une catégorie d’algorithmes approchés efficaces pour le problème du voyageur de commerce sont les algorithmes gloutons. Nous verrons dans ce cours plusieurs exemples d’algorithmes gloutons. Nous verrons aussi comment comparer ces algorithmes, en tenant compte à la fois de leur qualité d’approximation et de leur complexité.
Pour la prochaine fois
Nous vous demanderons de présenter votre solution pour ramasser plusieurs morceaux de fromage dans le labyrinthe. Pensez à comparer vos algorithmes en termes de qualité de la réponse fournie (comparaison avec un algorithme exhaustif, dans la mesure du possible) et temps de calcul.
Comme pour l’évaluation orale du cours 3, n’oubliez pas que vous devrez présenter et justifier vos choix. Vous pouvez/devez vous appuyer sur des courbes illustrant vos propos.