Progresser-en-maths

Maths + Toi = 1

Optimisation de trajectoires
Informatique Maths Facts

Optimisation de trajectoires dans un environnement simple

Aujourd’hui, nous vous présentons un sujet de TIPE d’informatique ! Ce sujet d’optimisation de trajectoirs est proposé par Colin Coërchon que nous remercions ! Ce TIPE a été présenté au tétraconcours. Colin a eu un beau 17,6/20 avec ce TIPE.

Présentation succincte du sujet

On souhaite aller d’un point A à un point B avec des contraintes : passage inaccessible, vitesse de déplacement plus ou moins ralentie – on va par se déplacer moins vite dans des endroits avec de la foule, dans la boue ou encore s’il faut nager ou escalader. Quels algorithmes nous permettent de trouver le meilleur trajet ?

Ce TIPE présente alors divers algorithmes : triangulation, parcours en largeur (GBFS), dijkstra et A* à travers des exemples très concrets (contraintes dans un jeu de chasse au trésor, se déplacer dans la ville de Paris) dans divers espaces :

  • Espace polygonal simple : on définit un plan à partir de polygones
  • Quadrillage de l’espace : on découpe le plan en x*y pixels pour mettre des contraintes différentes à chaque pixel

Ce TIPE est très détaillé, voici 3 supports :

  • Le TIPE (87 slides)
  • L’annexe, qui présente en LaTeX des démonstrations
  • Le code sur GitHub

Voici le sujet

Avec une annexe en tapée en LaTeX pour avoir toutes les démonstrations !

Laisser un commentaire