A-Star Algorithm Optimization

Question

I implemented the A * algorithm. In accordance with the Wikipedia implementation in here , however, on mobile devices it is too slow. I have to wait an infinite clock to finish the function, although it works fine on a desktop computer. Can I do something to optimize the algorithm?

Here is 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 whole code, but I can give some hints:

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

You will find subtypes of this data structure, such as fibonacci-heaps, etc. It is worth a try. Without doing A *, I would also ask splay-tree to try (do a wiki search to get hits).

Second: do you insert and delete nodes while the algorithm is running? If so, make sure you create a pool of pre-allocated nodes and use this instead of calling new / delete or malloc / free. Memory allocation can be very slow.

Answer 2

You must cache your points for each node in the priority queue. So you just need to pull the first node out of the priority queue every time you need a new node, instead of calling getLowestFscore. When implementing PriorityQueue, just use SortedDictionary<int, List<routenode>> . Use SetDefault (see here for an example) to make your life easier.

Also, since you have more problems with mobile devices, this could be a memory problem. In this case, you may want to use a limited BeamSearch - it will not give you better results every time, but it should work faster.

Answer 3

Can you parallelize the for loop? Do you work with a specific mobile device with multiple cores? If so, take a look at Tasks.Parallel.For (....) or Foreach.

Also, consider caching any information you may have.

Any reason you use A * instead of the Jikstra algorithm?

Answer 4

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

The optimization I would do is use the groups of nodes, not all nodes, to find the "best" way. Let's say you have 1000 cities, why not combine them together and find a better way on a more global scale, and then optimize the way.

I was just trying to implement the usual A *, but not with this optimization. Why don't you try?)

Answer 5

Most of the optimization of A * is in the implementation of open and closed lists. In particular, the following four methods: add, delete, get the least significant element, and search for a record related to a particular node. Personally, I have found that using a full binary heap to structure an open list will significantly increase the speed of my A * code that was created in Python. Hope this helps!