Dans Dijkstra tu repars systématiquement du chemin le plus court à jour pour l'étape suivante, ça implique de trier pour savoir quels sont les sommets "non clos" triés par leur chemin le plus court d'accès connu. Ils s'en débarrassent en se servant d
un algo sur le papier plus cher mais qui ne nécessite pas de tri, en adoptant une approche "diviser pour régner" pour ne l'appliquer que de manière bornée et pas sur tout le graphe pour contrôler soigneusement la complexité.
A* ne se débarrasse pas de ce tri, il est juste changé un peu, au lieu de prendre le chemin le plus court à jour on prend le chemin le plus court plus une estimation du reste du chemin à parcourir, c'est pareil à l'estimation du chemin restant près. D'ou la borne au pire qui se réduit Dijkstra si on a pas de bonne estimation du chemin à parcourir.
Donc effectivement, ça fait mieux que A*, et je ne sais pas si utiliser une heuristique comme ça dans le nouvel algo améliorerait les choses vu qu'ils n'ont pas besoin du tri pour choisir un nœud prometteur.
[^] # Re: A*
Posté par thoasm . En réponse au journal Des chercheurs ont trouvé mieux que l'algo de Dijkstra pour la recherche de chemins. Évalué à 7.
Ce qui permet de supprimer le "n log(n)", cf. cet article de quanta magazine qui vulgarise le truc si on veut pas se taper l'article : https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ c'est de se débarrasser du tri des sommets.
Dans Dijkstra tu repars systématiquement du chemin le plus court à jour pour l'étape suivante, ça implique de trier pour savoir quels sont les sommets "non clos" triés par leur chemin le plus court d'accès connu. Ils s'en débarrassent en se servant d
un algo sur le papier plus cher mais qui ne nécessite pas de tri, en adoptant une approche "diviser pour régner" pour ne l'appliquer que de manière bornée et pas sur tout le graphe pour contrôler soigneusement la complexité.
A* ne se débarrasse pas de ce tri, il est juste changé un peu, au lieu de prendre le chemin le plus court à jour on prend le chemin le plus court plus une estimation du reste du chemin à parcourir, c'est pareil à l'estimation du chemin restant près. D'ou la borne au pire qui se réduit Dijkstra si on a pas de bonne estimation du chemin à parcourir.
Donc effectivement, ça fait mieux que A*, et je ne sais pas si utiliser une heuristique comme ça dans le nouvel algo améliorerait les choses vu qu'ils n'ont pas besoin du tri pour choisir un nœud prometteur.