Optimisation de l'algorithme A-Star

Question

J'ai implémenté l'algorithme A * Selon l'implémentation de Wikipedia au here Cependant, il est trop lent pour fonctionner dans les appareils mobiles. Je dois attendre des heures interminables pour finir la fonction bien que cela fonctionne bien sur l'ordinateur de bureau. Est-ce que je peux faire quelque chose pour optimiser l'algorithme?

Voici le code réel

public DriveRoute findroute(routenode from, routenode to) 
     { 
      Dictionary<int, routenode> openlist = new Dictionary<int, routenode>(); 
      openlist.Add(from.nodeid, from); 
      Dictionary<int, routenode> closedlist = new Dictionary<int, routenode>(); 
      Dictionary<int, double> gscores = new Dictionary<int, double>(); 
      gscores.Add(from.nodeid, 0); 
      Dictionary<int, double> hscores = new Dictionary<int, double>(); 
      hscores.Add(from.nodeid, distanceForRouting(from.latlon, to.latlon)); 
      Dictionary<int, double> fscores = new Dictionary<int, double>(); 
      fscores.Add(from.nodeid, gscores[from.nodeid] + hscores[from.nodeid]); 
      Dictionary<int, routenode> came_from = new Dictionary<int, routenode>(); 
      while (openlist.Values.Count > 0) 
      { 
       routenode x = getLowestFscore(openlist, fscores); 
       if (x.latlon.Equals(to.latlon)) 
       { 
        return rebuildPathWay(came_from, to); 
       } 
       openlist.Remove(x.nodeid); 
       closedlist.Add(x.nodeid, x); 
       foreach (routearc arc in x.outgoingarcs) 
       { 
        if (closedlist.Keys.Contains(arc.endnode)) 
         continue; 
        double tentative_g_score = gscores[x.nodeid] + arc.time; 
        bool tentative_is_better = false; 
        if (!openlist.Keys.Contains(arc.endnode)) 
        { 
         openlist.Add(arc.endnode, map.routenodes[arc.endnode]); 
         tentative_is_better = true; 
        } 
        else if (tentative_g_score < gscores[arc.endnode]) 
        { 
         tentative_is_better = true; 
        } 
        if (tentative_is_better) 
        { 
         if (came_from.ContainsKey(arc.endnode)) 
          came_from[arc.endnode] = x; 
         else 
          came_from.Add(arc.endnode, x); 
         gscores[arc.endnode] = tentative_g_score; 
         hscores[arc.endnode] = distanceForRouting(arc.endlatlon, to.latlon); 
         fscores[arc.endnode] = gscores[arc.endnode] + hscores[arc.endnode]; 
        } 
       } 
      } 
      return null; 
     } 

Answer 1

Il est difficile de donner des conseils sans voir le code entier, mais je peux être en mesure de donner quelques conseils:

L'action principale que vous faites sur le dictionnaire est de trouver quelque chose avec le plus bas coût. La structure de données derrière le dictionnaire devrait être optimisée pour cette opération. Une structure de données classique serait un tas (pas la chose liée à new/delete malloc/free mais la structure de données: http://en.wikipedia.org/wiki/Heap_%28data_structure%29)

Vous trouverez des sous-types de cette structure de données comme fibonacci-heaps et ainsi de suite . Cela vaut la peine de les essayer. Sans jamais avoir implémenté A *, j'essaierais aussi l'arbre splay (faire une recherche sur wiki vous donnera des hits). Deuxièmement: Insérez-vous et supprimez-vous des noeuds pendant l'exécution de l'algorithme? Si c'est le cas, assurez-vous de créer vous-même un pool de noeuds pré-alloués et utilisez ceci au lieu d'appeler new/delete ou malloc/free. Les allocations de mémoire peuvent être très lente.

Answer 2

A * est un bon algorithme heuristique, mais vous devez sans doute trop optimisation.

Une optimisation que j'aurais fait est d'utiliser des groupes de nœuds, au lieu de tous les nœuds, pour trouver le «meilleur» chemin. Disons que vous avez 1000 villes, pourquoi ne pas les regrouper et trouver le meilleur chemin dans une échelle plus globale, puis optimiser le chemin.

J'ai seulement essayé d'implémenter l'A * habituel, mais pas avec cette optimisation. Pourquoi ne pas l'essayer;)

Answer 3

Vous devez mettre en cache vos scores pour chaque nœud dans une file d'attente prioritaire. De cette façon, il vous suffit de sortir le premier noeud de la file d'attente prioritaire chaque fois que vous avez besoin d'un nouveau noeud, au lieu de devoir appeler getLowestFscore. Lors de l'implémentation de PriorityQueue, utilisez simplement SortedDictionary<int, List<routenode>>. Utilisez SetDefault (voir here pour un exemple) pour vous faciliter la vie.

En outre, comme vous rencontrez plus de problèmes sur les périphériques mobiles, cela peut être un problème de mémoire. Dans ce cas, vous pourriez envisager d'utiliser un BeamSearch borné - il ne vous donnera pas les meilleurs résultats à chaque fois, mais il devrait fonctionner plus vite.

Answer 4

Pouvez-vous paralléliser la boucle for? Travaillez-vous avec un appareil mobile spécifique avec plusieurs cœurs? Si oui, regardez dans Tasks.Parallel.For (....) ou Foreach.

En outre, pensez à mettre en cache toutes les informations que vous pouvez.

Une raison pour laquelle vous utilisez A * au lieu de l'algorithme de Djikstra?

Answer 5

La plus grande partie de l'optimisation de A * est destinée à l'implémentation des listes ouvertes et fermées. Plus précisément, les quatre méthodes suivantes: ajouter, supprimer, obtenir le plus petit élément de valeur, et trouver l'entrée qui se rapporte à un nœud spécifique. Personnellement, j'ai trouvé que l'utilisation d'un tas binaire complet pour structurer la liste ouverte augmenterait considérablement la vitesse de mon code A *, qui a été créé en Python. J'espère que cela t'aides!