[Maths] Aide pour un projet d'études
Salut les chouals, je suis actuellement en classe prépa et je dois réaliser un projet d'étude sur l'optimisation. Quelqu'un s'y connaîtrait-il en recherche dans des graphes pondérés et des idées sympas pour rendre la théorie plus concrète ?
Merci
Commentaire supprimé.
Tu peux te servir d'un graphe pour modéliser une carte, chaque carrefour/intersection est représenté par un sommet et chaque route est une arrête du graph. Le coût de l’arrête est représenté par la longueur de la route.
Là le cadre est posé. Ensuite dans ton projet tu vas prendre un point de départ et un point d'arriver et utiliser un algorithme de plus court chemin pour trouver le parcours le plus rapide. Le truc c'est qu'il en existe plusieurs, tous performant mais dans des situations différentes.
Je te laisse te renseigner notamment sur:
- Dijktra
- L'algorithme A*
- Bellman-Ford
- Prism
- Floyd-Warshall
Tu les test tous, tu expliques pourquoi lui est mieux que lui dans tel cas etc...
"En quoi l'algorithme de xxxxxx est le plus optimisé dans tel cas de figure"
En gros ça fera plaisir à tes prof car c'est ce qu'ils vont t'enseigner dans l'année. Après pour rendre ça un peu plus intéressent, plutôt qu'une carte, utilise une grille comme ils le font dans les jeux vidéos (voir à 2:41 https://youtu.be/DlgnB4UKU74?t=2m41s pour comprendre)
Bonne chance !
@GeekRider: *Dijkstra
Ceci dit il est ultra pété cet algo, et accessoirement il a l'avantage d'être complet ET rapide.
Quand tu dis optimiser, entends-tu, par exemple, trouver le plus court chemin pour aller d'un point A à un point B, comme pour le GPS ?
@Calvinator: C'est l'idée, de faire un trajet le plus "court" en termes de coûts énergétiques et de matériaux. La problématique est d'optimiser le tracé d'un réseau d'eau sur un terrain vallonné, le graphe pondéré représentant les reliefs du terrain. On appliquerait ensuite des contraintes physiques pour économiser l'énergie qu'il faudrait pour distribuer l'eau à toute la population (des noeuds du graphe choisis).
@PtitPapier: Oui les arrêtes pondérées c'était ce qu'on comptait faire en créant des triplets ((coordonnées du pt a) ; (coordonnées du pt b) ; (poids pour a -> b)) en mettant des contraintes du genre : si (poids a -> b) > x on ne peut pas inclure le passage de a à b dans le trajet (comme on comptait simuler des conduites d'eau aériennes)
Tu ne dois accéder à ce site que si tu as au moins 18 ans ou si tu as l'âge légal pour visionner ce type de matériel dans ta juridiction locale, l’âge le plus élevé étant retenu. En outre, tu déclares et garantis que tu ne permettras aucun mineur à d'accéder à ce site ou à ces services.
En accédant à ce site, tu acceptes nos conditions d'utilisation.