Optimisation de l'algorithme A-Star

Question

J'ai implémenté l'algorithme A* Selon l'implémentation de Wikipedia à ici Cependant, il est trop lent pour fonctionner sur les appareils mobiles. Je dois attendre des heures interminables pour terminer la fonction alors qu'elle fonctionne bien sur un ordinateur de bureau. Y a-t-il quelque chose que je puisse faire pour optimiser l'algorithme ?

Voici le code actuel

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 l'ensemble du code, mais je peux peut-être vous donner quelques indications :

La principale action que vous faites sur le dictionnaire est de trouver quelque chose au coût le plus bas. La structure de données derrière le dictionnaire doit ê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 les tas de fibonacci, etc. Cela vaut la peine de les essayer. Sans avoir jamais implémenté A*, j'essaierais aussi le splay-tree (une recherche sur wiki vous donnera des résultats).

Deuxièmement : insérez-vous et supprimez-vous des nœuds pendant l'exécution de l'algorithme ? Si c'est le cas, assurez-vous de vous constituer un pool de nœuds pré-alloués et utilisez-le au lieu d'appeler new/delete ou malloc/free. Les allocations de mémoire peuvent être muy lent.

Answer 2

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

Par ailleurs, comme vous rencontrez plus de difficultés sur les appareils mobiles, il peut s'agir d'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 s'exécuter plus rapidement.

Answer 3

Peut-on paralléliser la boucle for ? Travaillez-vous avec un appareil mobile spécifique qui possède plusieurs cœurs ? Dans ce cas, utilisez Tasks.Parallel.For(....) ou Foreach.

Pensez également à mettre en cache toutes les informations que vous pouvez.

Pourquoi utilisez-vous A* au lieu de l'algorithme de Djikstra ?

Answer 4

A* est un bon algorithme heuristique, mais vous avez probablement besoin d'une optimisation également.

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

J'ai seulement essayé de mettre en œuvre le A* habituel, mais pas avec cette optimisation. Pourquoi ne pas l'essayer ;)

Answer 5

L'essentiel de l'optimisation de A* réside dans l'implémentation des listes ouvertes et fermées. Plus précisément, les quatre méthodes suivantes : ajout, suppression, obtention du plus petit élément de valeur et recherche de l'entrée correspondant à un nœud spécifique. Personnellement, j'ai constaté que l'utilisation d'un tas binaire complet pour structurer la liste ouverte augmente considérablement la vitesse de mon code A*, qui a été créé en Python. J'espère que cela vous aidera !