Ajustement à un algorithme de chemin le plus court

Question

pour une structure de données & classe d'algorithmes au collège nous devons implémenter un algorithme présenté dans un document. Le papier peut être trouvé here. Donc j'ai complètement implémenté l'algorithme, avec encore quelques erreurs laissées (mais ce n'est pas vraiment pourquoi je pose cette question, si vous voulez voir comment je l'ai implémenté jusqu'ici, vous pouvez le trouver here)

Le réel raison pour laquelle je pose une question sur Stackoverflow est la deuxième partie de la tâche: nous devons essayer de rendre l'algorithme meilleur. J'ai eu quelques façons à l'esprit, mais tous sonnent bien en théorie, mais ils ne seront pas vraiment faire du bien dans la pratique:

• tracer une ligne entre la source et le noeud final, rechercher le noeud le plus proche du milieu de cette ligne et diviser le "chemin" en 2 récursivement. Le cas de base serait un graphique plus petit où un seul Dijkstra ferait le calcul. Ce n'est pas vraiment un ajustement à l'algorithme actuel, mais en pensant qu'il est clair que cela ne donnerait pas une solution optimale.
• Essayez de donner un sens à l'algorithme en donnant une priorité plus élevée aux arêtes qui pointent vers le noeud final. Cela ne sera pas non plus optimal ..

Alors maintenant, je suis à court d'idées et j'espère que quelqu'un ici pourrait me donner un petit indice pour un éventuel ajustement. Il ne faut pas vraiment améliorer l'algorithme, je pense que la première raison pour laquelle ils nous ont demandé de le faire est de ne pas simplement mettre en œuvre l'algorithme du papier sans savoir ce qui se cache derrière.

(Si Stackoverflow n'est pas le bon endroit pour poser cette question, mes excuses :))

Une brève description de l'algorithme: L'algorithme essaie de sélectionner les noeuds prometteurs. En promettant que je veux dire qu'ils ont une bonne chance de mentir sur un chemin le plus court. La promesse d'un nœud est représentée par sa 'portée'. La portée d'un sommet sur un chemin est le minimum de ses distances au début et à la fin. La portée d'un sommet dans un graphe est le maximum des portées du sommet sur tous les chemins les plus courts. Pour éventuellement déterminer si un nœud est ajouté à la file d'attente prioritaire dans l'algorithme de Dijkstra, une fonction test() est ajoutée. Test renvoie vrai (si la portée d'un sommet dans le graphique est plus grande ou égale, alors le poids du chemin de l'origine à v à l'instant v doit être inséré dans la file d'attente prioritaire) ou (la portée du sommet dans le le graphe est plus grand ou égal à la distance euclidienne de v au sommet final).

Harm De Weirdt

Answer 1

Votre meilleur pari dans des cas comme celui-ci est à penser comme un chercheur: recherche en général et la recherche en informatique est précisément sur une amélioration progressive, une personne montre qu'ils peuvent calculer quelque chose plus rapide en utilisant l'algorithme de Dijkstra et puis plus tard, ils ou quelqu'un d'autre, montrent qu'ils peuvent calculer la même chose un peu plus vite en utilisant A *. C'est une série de petites étapes. Cela dit, le meilleur endroit pour chercher des façons d'améliorer un algorithme présenté dans un article est dans la section des directions futures. Ce document vous donne un peu de travail dans cette direction, mais votre mine d'or dans ce cas se trouve dans les sections 5 et 6. Il existe plusieurs endroits où les auteurs admettent différentes approches possibles. Essayez de rechercher certaines de ces approches, cela devrait vous conduire soit à une amélioration possible de l'algorithme, soit au moins à un argument discutable. Bonne chance!