est question des algorithmes de tri, en particulier, pour trouver le plus court chemin
entre deux noeuds en choisisant un point de départ et en connaissant le point d'arrivée.
Nous voilà donc dans une sous-discipline importante de l'informatique (Analyse), car
l'Internet doit constamment avancer de l'information selon ces algorihtmes, le GPS nous
localise, Google Maps nous trouve des restaurants...etc
L'université de Bordeaux - et son école d'informatique - aurait même changé sa devise
pour le plus court chemin pour aller loin...😉
L'exemple proposé se sert de l'algorithme de Dijkstra, un algorithme qui propose
du 'label-setting', c'est -à dire, qui met les noeuds à jour après chaque tour..
On peut s'amuser à créer ses propres problèmes sur le site ci-bas:
https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_en.html
Le problème de fond revient à ne pas épuiser l'ordi avec des calculs pas nécessaires; car
le nombre de calculs - et donc le temps de travail de l'ordi - monte très vite si on n'optimise pas: O(n!) opérations à voir si on traite toutes les possibilités; pour 6 noeuds, cela revient à 720 .
On aime bien l'ordre topologique pour traiter un problème:
L'algorithme de D crée un tel ordre à mesure de son exécution.
https://www.math.u-bordeaux.fr/~gstauffe/cours/MSE3211A/MSE3211A_3.pdf
Aucun commentaire:
Enregistrer un commentaire