Aujourd’hui, nous vous présentons un sujet de TIPE d’informatique ! Ce sujet d’optimisation de trajectoires 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 !
