Lors des précédents cours, nous avons vu que le problème du voyageur de commerce est très complexe à résoudre, et qu’espérer obtenir une solution pour des gros graphes est complètement irréaliste en un temps acceptable. La première alternative proposée était de s’appuyer sur des algorithmes approchés ne donnant pas nécessairement la bonne solution.
Toutefois, les algorithmes approchés peuvent aider à la résolution exacte du problème. Il est par exemple possible de tomber très vite sur un bon chemin, auquel cas de nombreuses explorations suivantes sont superflues. C’est l’objectif de ce cours. Nous présentons ici deux algorithmes basés sur des heuristiques permettant de résoudre le problème du voyageur de commerce plus efficacement que l’approche exhaustive, en s’appuyant sur des approximations données par des algorithmes approchés.
Pour la prochaine fois
C’est à présent le moment de vous lâcher, et de commencer à écrire vos IAs pour le tournoi. La septième et dernière séance avant le tournoi est un peu particulière. Nous vous demandons deux choses :
- Préparer un court document (1 à 2 pages) décrivant dans les grandes lignes l’IA que vous allez présenter au tournoi. Nous vous demandons un document un peu “marketing”, c’est à dire que n’importe qui doit pouvoir comprendre vos choix, et avoir confiance en votre équipe à sa lecture. N’hésitez pas à mettre des illustrations/courbes/etc., à la manière d’un poster de vulgarisation scientifique. Ces documents seront affichés en amphi le jour du tournoi.
- Préparer une présentation (avec slides/animations/etc.) de dix minutes, plus cinq minutes de questions, que vous présenterez à votre classe par binômes (avec temps de parole réparti). Cette présentation devra présenter vos choix d’IA, ainsi que leurs qualités/défauts/etc. Pour plus d’infos sur les critères d’évaluation, nous vous conseillons de regarder la grille d’évaluation. De même, pensez à explorer les quelques liens en bas de la page de présentation du cours !
Articles à étudier
- Complexité pire cas et complexité en moyenne
- Les heuristiques (encore !)
- L’algorithme de backtracking
- L’algorithme de branch-and-bound