优化A-Star算法

Question

我已经实现了 A* 算法根据维基百科的实现在这里 然而，在移动设备上运行太慢了。尽管它在台式计算机上运行良好，但我必须等待无数个小时才能完成该功能。我可以做些什么来优化算法？

这是实际的代码

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

如果没有看到完整的代码，很难给出任何提示，但我或许可以给出一些提示：

您对字典所做的主要操作是找到成本最低的东西。应针对此操作优化字典背后的数据结构。经典的数据结构是堆（不是与 new/delete malloc/free 相关的东西，而是数据结构：http : //en.wikipedia.org/wiki/Heap_%28data_structure%29）

你会发现这个数据结构的子类型，比如 fibonacci-heaps 等等。值得一试。在没有实现 A* 的情况下，我也会尝试使用 splay-tree（在 wiki 上进行搜索会给你带来命中）。

第二：您是否在算法运行期间插入和删除节点？如果是这样，请确保您自己构建一个预先分配的节点池并使用它而不是调用 new/delete 或 malloc/free。内存分配可能非常慢。