Optimizing A-Star Algorithm

Question

I have implemented the A* Algorithm According to Wikipedia's implementation at here However, it is too slow to run in mobile devices. I have to wait endless hours to finish the function though it runs fine on desktop computer. Is there anything I can do to optimize the algorithm?

Here's the actual code

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

It is hard to give any hints without seeing the entire code, but I may be able to give some hints:

The main action you do on dictionary is to find something with the lowest cost. The data-structure behind dictionary should be optimized for this operation. A classic data-structure would be a heap (not the thing related to new/delete malloc/free but the datastructure: http://en.wikipedia.org/wiki/Heap_%28data_structure%29 )

You'll find sub-types of this data-structure like fibonacci-heaps and so on. It's worth to give them a try. Without ever having implemented A* I'd also give the splay-tree a try (do a search on wiki will give you hits).

Second: Do you insert and remove nodes during the run-time of the algorithm? If so make sure you build yourself a pool of pre-allocated nodes and use this instead of calling new/delete or malloc/free. Memory allocations can be very slow.

Answer 2

You should cache your scores for each node in a priority queue. That way, you just need to pop off the first node from the priority queue each time you need a new node, instead of having to call getLowestFscore. When implementing the PriorityQueue, just use a SortedDictionary<int, List<routenode>>. Use SetDefault (see here for an example) to make your life easier.

Also, since you are having more trouble on mobile devices, it might be a memory issue. In which case, you might want to consider using a bounded BeamSearch - it won't give you the best results each time, but it should run faster.