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

A* is a good heuristic algorithm, but you probably need optimization too.

An optimization I would have done is using groups of nodes, instead of all nodes, to find the "best" path. Say you have 1,000 cities, why not group these together and find the best path in a more global scale, then optimize the path.

I only tried implementing the usual A*, but not with this optimization. Why don't you try it ;)

Answer 2

Please add the classes used in the program (routeNode), and be more specific about how your graph looks like:

1. Does it have a specific form? Mash? Tree?
2. How many nodes are there in the average graph.

Another importent question is what is your heuristicfunction?

Answer 3

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.

Answer 4

Can you parallelize the for loop? Are you working with a specific mobile device that has multiple cores? If so, look into Tasks.Parallel.For(....) or Foreach.

Also, consider caching any information you can.

Any reason you're using A* instead of Djikstra's algorithm?

Answer 5

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.