val*_*ldo 5 algorithm geometry graph path dijkstra
我需要找到连接两个平面点的最佳路径.我给出了一个确定最大前进速度的函数,它取决于位置和时间.
我的解决方案基于Dijkstra算法.首先,我通过2D晶格覆盖平面,仅考虑离散点.点与指定顺序的邻居相连,以获得足够的方向分辨率.然后我找到了(有点)Dijkstra算法的最佳路径.接下来,我提高了找到的路径的分辨率/质量.我增加了网格密度和邻居连接顺序,同时将搜索仅限制在足够接近已找到路径的点上.这可以重复,直到达到所需的分辨率.
这通常很好,但是我想提高整体算法性能.我已经基于价格函数的"平滑度"实现了几个技巧,例如可变网格密度和邻居连接顺序.但是我相信有可能改进Dijkstra算法本身(适用于我的特定图形),我还没有完全意识到.
首先让我们就术语达成一致.我将所有格点分为3类:
在每一步,Dijkstra算法选择"最便宜"的暖格点,然后尝试提高其邻居的价格.由于我的图形的性质,我得到了一种稳定点的云,周围是一层薄薄的暖点.在每个步骤中的温暖在浊点周长被处理,那么它加入到稳定云,并且暖周长是(潜在的)展开.
的问题是,暖被随后通过算法处理点通常是在空间上(因此-拓扑)无关.典型的温暖周界由数十万个点组成.在每一步的下一个暖点的过程是伪randomal(空间),因此实际上有没有机会,两个相关点被处理了一个又一个.
这确实会产生CPU缓存利用率的问题.在每一步,CPU处理伪随机存储器位置.由于存在大量的热点 - 所有相关数据可能都不适合CPU缓存(它的数量级为几十到几百MB).
嗯,这确实是Dijkstra算法的含义.无论其他属性如何,整个想法都明确地选择最便宜的热点.
但直观地说,很明显,大云外围一侧的点对另一侧的点(在我们的具体情况下)没有任何意义,并且交换其处理顺序没有问题.
因此,我考虑了"调整" 暖点处理顺序的方法,但一般不会影响算法.我想到了几个想法,比如将飞机划分为块,并且在满足某些标准之前将其部分解决,这意味着他们的解决方案可能会受到干扰.或者可选地忽略干扰,并且可能允许"重新解决"(即从稳定回到温暖).
但到目前为止,我找不到严谨的方法.
有什么想法怎么做？也许这是一个已知的问题,现有的研究和(希望)解决方案？
提前致谢.抱歉这个长期的问题.
您所描述的是A*搜索算法背后的动机,这是对Dijkstra 算法的修改,它可以通过引导搜索方向来显着改善运行时间,该方向可能会选择越来越靠近目的地的点.A*永远不会比天真的Dijkstra实现更多的工作,并且通常倾向于扩展聚集在最靠近目标节点的暖节点的边界上的节点.
在内部,A*通过使用启发函数扩充Dijkstra算法来工作,该启发函数估计到目标节点的剩余距离.这意味着如果你得到的可以得到一个给定节点离目的地有多远的粗略近似值,你最终可能会忽略那些不需要处理的节点,而有利于可能更好的节点.
A*并未设计为缓存最优算法,但我认为速度的提高归因于
将为您带来巨大的性能提升和更好的缓存性能.
希望这可以帮助!