CODEWITHSUNDEEP
c#routesnavigationgps
VOX
VOX

Reputation: 2923

Optimizing A-Star Algorithm

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;
        }

Upvotes: 6

Views: 8683

Answers (5)

RatherBKnitting
RatherBKnitting

Reputation: 421

Most of the optimization of A* goes into the implementation of the open and closed lists. Specifically, the following four methods: adding, removing, getting the smallest valued item, and finding the entry that pertains to a specific node. Personally, I have found that using a Complete Binary Heap to structure the open list will significantly increase the speed of my A* code, which was created in Python. Hope this helps!

Upvotes: 0

Nils Pipenbrinck
Nils Pipenbrinck

Reputation: 86443

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.

Upvotes: 5

Chad
Chad

Reputation: 3237

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?

Upvotes: 1

Shaun McCarthy
Shaun McCarthy

Reputation: 1690

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.

Upvotes: 1

Marcus Johansson
Marcus Johansson

Reputation: 2667

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 ;)

Upvotes: 0

Related Questions