我已经根据维基百科在 here 的实现实现了 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;
}
最佳答案
没有看到完整的代码很难给出任何提示,但我也许可以给出一些提示:
你在字典上做的主要 Action 是找到成本最低的东西。应该为此操作优化字典背后的数据结构。一个经典的数据结构是堆(不是与 new/delete malloc/free 相关的东西,而是数据结构:http://en.wikipedia.org/wiki/Heap_%28data_structure%29)
您会发现此数据结构的子类型,如斐波那契堆等。值得一试。在没有实现 A* 的情况下,我也会尝试一下 splay-tree(在 wiki 上搜索会给你命中)。
其次:您是否在算法运行时插入和删除节点?如果是这样,请确保您自己构建了一个预分配节点池并使用它而不是调用 new/delete 或 malloc/free。内存分配可能非常慢。
关于c# - 优化A星算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3435674/