La recherche du plus court chemin on s'en sert tous les jours. Va y avoir des mises-à-jour
"Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" est le titre du papier
Les chercheurs : Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
dispo à https://arxiv.org/pdf/2504.17033
source : https://x.com/dorsa_rohani/status/1954573594853244964
# A*
Posté par oliverpool (site web personnel) . Évalué à 5 (+4/-0).
Vraiment ? Est-ce que A* n'est pas plus utilisé ?
[^] # Re: A*
Posté par finss (site web personnel) . Évalué à 4 (+2/-0).
Dans l'article de Wikipédia, c'est dit "Si l'évaluation renvoie simplement toujours zéro, qui n'est jamais une surestimation, alors, A* exécutera une implémentation possible de l'algorithme de Dijkstra et trouvera toujours la solution optimale"
Le gain en complexité temporelle de ce nouvel algo fait qu'on passe de O(m+n log n) à O(m log{2/3} n) avec m le nombre de sommets et n le nombres de nœuds, devrait impacter A* amha.
\_o<
[^] # Re: A*
Posté par thoasm . Évalué à 7 (+4/-0).
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.
[^] # Re: A*
Posté par rewind (Mastodon) . Évalué à 5 (+2/-0).
Normalement, on ne trie pas, on utilise un tas, qui donne toujours l'élément max sans devoir tout trier à chaque fois.
[^] # Re: A*
Posté par thoasm . Évalué à 5 (+2/-0).
Même complexité non ? C'est l'insertion qui est en log(n) et tu fais ça n fois. C'est un tri version algorithme incrémental quoi.
# Prononçable
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 10 (+16/-0).
L'avantage principal de ce BMSSP par rapport à l'algorithme de Dijsktra, c'est que son nom est prononçable et moins sujet aux fautes de frappes.
(Sérieusement, cela fait moins d'un an que je sais que Dijsktra se prononce déistra.)
[^] # Re: Prononçable
Posté par Sylvain Berfini (site web personnel) . Évalué à 10 (+15/-0).
Et ben moi ça fait maintenant 1 minute que je le sais 😅, merci !
[^] # Re: Prononçable
Posté par Big Pete . Évalué à 10 (+8/-0).
Hum, l'algorithme du plus court chemin pour trouver la bonne prononciation de son nom n'est pas encore au point visiblement.
Faut pas gonfler Gérard Lambert quand il répare sa mobylette.
[^] # Re: Prononçable
Posté par devnewton 🍺 (site web personnel) . Évalué à 2 (+2/-3).
Béhème SS Pet => imagine toi dans un labyrinthe poursuivi par un nazi pétomane en BMW. Ca donne envie de trouver l'algo le plus performant pour en sortir !
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Prononçable
Posté par thoasm . Évalué à 3 (+0/-0).
Non le chemin le plus court est juste très très long et le graphe immense ! Il n'y a pas de bonne heuristique manifestement donc A* n'aide pas.
[^] # Re: Prononçable
Posté par Big Pete . Évalué à 5 (+3/-0).
Pour la blague, je cherchais des infos sur les algos de ce type qui utilise un principe tiré des colonies de fourmis, et je suis tombé sur cet article dont le titre est juste génial. on croirait du Douglas Adams :
Optimisation par colonies de fourmis pour le problème du sac à dos multidimensionnel
Pour des gens qui savent de quoi ça parle, ça doit être assez limpide, mais pour un esprit profane et légèrement enclin a l'imaginaire, ça laisse rêveur …
Le problème du sac à dos
les algos de colonie de fourmis
D'ailleurs, ma recherche de base, c'était d'essayer de savoir si ces algos d'optmisations de colonies de fourmis étaient utilisés en pratique ? J'avais cru comprendre que certaine applis comme Waze utilisait ça, mais j'ai jamais vraiment su si ça tenait de la légende urbaine ou pas.
Faut pas gonfler Gérard Lambert quand il répare sa mobylette.
[^] # Re: Prononçable
Posté par sobriquet . Évalué à 10 (+11/-1).
C'est pourtant simple : un sac à dos multidimensionnel est un sac à dos qui est plus grand à l'intérieur qu'à l'extérieur. Le problème de ces sacs à dos, c'est qu'ils sont tellement grands à l'intérieur qu'il devient difficile d'y retrouver ses affaires, surtout si on ne veut pas y mettre plus que le bras.
Le sujet de l'organisation des fourmis est un domaine actif de l'entomologie. En particulier, on comprend mal comment les fourmis font pour toujours retrouver leurs affaires malgré un désordre apparent et le rejet de la propriété privée. De plus les colonies de fourmi sont connues pour très bien occuper l'espace dont elles disposent.
L'optimisation proposée consiste ainsi à installer une colonie de fourmis dans le sac à dos pour les laisser traiter le rangement des affaires qu'on y met. L'originalité de leur approche a consisté en un protocole d'échange humain-fourmi qui garantit d'une part la récupération des affaires qu'on confie aux fourmis, et d'autre part la viabilité de la colonie (théoriquement).
C'est une étude intéressante avec des débouchés prometteurs, mais j'ai des réserves sur l'applicabilité d'une telle solution pour stocker de la nourriture.
[^] # Re: Prononçable
Posté par Julien Jorge (site web personnel) . Évalué à 7 (+5/-0).
J'avais travaillé sur un algo de colonies de fourmis sur le problème de set packing, qui, si je me souviens bien, est un cas particulier du sac a dos multidimensionnel où les poids, les coûts, et les capacités sont tous à 1. C'était utilisé il me semble dans une application de planning de transport ferroviaire.
Ça reste une métaheuristique qui ne converge même pas vers un optimum global, donc on se demande toujours si on n'aurait pas eu mieux en cherchant plus. Alors qu'un recuit simulé sur un temps infini ça converge au moins vers un optimum global !
[^] # Re: Prononçable
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 6 (+3/-0).
Sauf qu'en fait non, je me suis trompé. C'est Déikstra en fait. :'(
[^] # Re: Prononçable
Posté par Le Pnume . Évalué à 7 (+5/-0).
dɛɪkstra pour être précis
->[]
# Exemple
Posté par ff9097 . Évalué à 8 (+6/-0).
On a un exemple permettant aux gens normaux de comparer les 2 algos ?
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.