|
|
变种1：束搜索（Beam Search）
在A*算法的住循环中，OPEN集存储可能需要搜索的节点，用来以查找路径。
束搜索是A*的变体，它限制了OPEN集的大小。
如果集合变得太大，则丢弃给出良好路径的最差机会的节点。
束搜索的一个缺点是你必须保持你的设置排序这样做，这限制了你选择的数据结构的种类。
变种2：迭代加深（Iterative Deepening）
迭代加深是一种在许多AI算法中使用的方法，以近似答案开始，然后使其更准确。
该名称来自游戏树搜索，您可以在其中查看前面的一些移动（例如，在国际象棋中）。
您可以通过向前看更多动作来尝试加深树木。
一旦你的答案没有改变或改善很多，你就会认为你有一个非常好的答案，当你试图让它再次变得更准确时它不会改善。
在IDA*中，“深度”是f值的截止值。
当f值太大时，甚至不考虑节点（即，它不会被添加到OPEN集）。
第一次通过你处理很少的节点。
每次后续传递，都会增加您访问的节点数。
如果您发现路径有所改善，那么您将继续增加截止值；否则，你可以停下来。
我个人认为在游戏地图上不太需要用IDA*查找路径。
因为ID算法倾向于增加计算时间，同时减少内存需求。
然而，在地图寻路中，“节点”非常小-它们只是坐标。
我没有看到节约存储这些节点有什么巨大优势。
变种3：动态加权（Dynamic Weighting）
通过动态加权，您可以假设——
在搜索开始时，快速到达目的地所在区域更重要；
在搜索结束时，得到到达目标的最佳路径更重要。
有一个与启发式相关的权重（w>=1）。
随着你越来越接近目标，你减轻了权重；这降低了启发式的重要性，并增加了路径实际成本的相对重要性。
变种4：带宽搜索（Bandwidth Search）
有一些人可能觉得有用的带宽搜索有两个属性。
这种变化假设h是高估的，但它并没有高估超过一些数e。
如果您的搜索就是这种情况，那么您获得的路径的成本不会超过最佳路径的成本超过e。
再次，您的启发式越好，您的解决方案就越好。
您获得的另一个属性是，如果您可以删除OPEN集中的某些节点。
每当h+d大于路径的真实成本（对于某些d），您可以丢弃任何f值至少比OPEN中最佳节点的f值高e+d的节点。
这是一个奇怪的属性。
你有一个很好的f值“带宽”；这个频段以外的所有东西都可以丢弃，因为可以保证它不会走在最佳路径上。
奇怪的是，您可以对这两个属性使用不同的启发式方法，但事情仍然有效。
您可以使用一个启发式方法来保证您的路径不是太糟糕，另一个用于确定OPEN集中的内容。
注意：
带宽搜索看起来可能有用，但在游戏行业很少使用到。
搜索Google以获得更多信息，尤其是相关论文。
变种5：双向搜索（Bidirectional Search）
您可以不从开始到结束搜索，而是并行开始两次搜索，一次从头到尾，一次从完成到开始。
当他们见面时，你应该有一条好路。
在某些情况下，这是一个好主意。
双向搜索背后的想法是搜索结果在地图上扇出的“树”。
一棵大树比两棵小树要糟糕得多，所以最好有两棵小树。
从面对面的变化将两个搜索链接在一起。
不是选择最佳前向搜索节点【g(start,x)+h(x,goal)】或最佳后向搜索节点【g(y,goal)+h(start,y)】
该算法选择具有最佳【g(start,x)+h(x,y)+g(y,goal)】的节点对。
重定向方法（retargeting approach）放弃了向前和向后方向的同时搜索。
相反，它会在短时间内执行前向搜索，选择最佳前向候选者N；
然后在终点执行后向搜索，搜索的目标不是起点，而是最佳前向候选者N。
过了一会儿，它选择了一个最好的后向候选人M，并执行从N到M的前向搜索。
这个过程一直持续循环，直到两个候选人是同一个点。
Holte，Felner，Sharon，Sturtevant在2016年的论文《具有近似最优节点扩展的前端双向启发式搜索》是最近的结果，具有接近最优的A*双向变体。
Pijls和Post在2009年的论文《另一种用于最短路径的双向算法》提出了一种比平衡双向搜索运行得更快的不平衡双向A*。
变种6：动态A*（Dynamic A*）和终身规划A*（Lifelong Planning A*）
A*的变体允许在计算初始路径之后改变世界。
D*适用于没有完整信息的情况。
如果你没有所有的信息，A*会犯错误；D*的贡献在于它可以在不花费太多时间的情况下纠正这些错误。
LPA*旨在用于成本变化时使用。
使用A*，路径可能会因地图的更改而失效；LPA*可以重复使用先前A*的计算来生成新路径。
但是，D*和LPA*都需要很大的空间——需要保存在最佳路径周围的很多节点的内部信息（OPEN/CLOSED集，路径树，g值）
然后当地图改变时，D*或LPA*会告诉您是否需要调整路径以考虑地图更改。
对于具有大量移动单位的游戏，您通常不希望保留所有这些信息（因为太大），因此D*和LPA*不适用。
它们是专为机器人设计的，如果只有一个机器人——您不需要将内存重用于其他机器人的路径。
如果您的游戏只有一个或少数单位，您可能需要试试D*或LPA*。
LPA*概述
LPA*小程序
变种7：跳点搜索（Jump Point Search）
许多加速A*的技术实际上都是关于减少节点数量。
在具有统一成本的方形网格中，一次一个地查看所有单独的网格空间是相当浪费的。
一种方法是构建关键点（例如角点）的图形并将其用于寻路。
但是，如果您不希望预先计算航点图，那就可以了解一下跳转点搜索，这是A*的变体，可以在方格网格上向前跳跃。
当考虑当前节点的子节点可能包含在OPEN集中时，跳转点搜索会向前跳到从当前节点可见的远端节点。
每个步骤都更昂贵，但它们更少，减少了OPEN集中的节点数量。
有关详细信息，请参阅此博客。
此文章提供了一个很好的可视化程序用来解释。
另请参阅矩形对称缩减，它可以分析地图并将跳转嵌入到图形本身中。
这两种技术都是为方形网格开发的。
这个网站是为六边形网格扩展的算法。
变种8：Theta*
网格用于寻路，是因为地图是在网格上制作的，而不是因为我们实际上想要在网格上移动。
如果给出关键点（例如角点）而不是网格的图形，A*将运行得更快并产生更好的路径。
但是，如果您不想预先计算角点图形，则可以使用在方形网格上运行的A*变体Theta*来查找不严格遵循网格的路径。
在构建父指针时，如果该节点与祖先节点有一条视线，互相可见，那么Theta*将该节点直接指向祖先节点，并跳过他俩中间的节点。
与路径平滑不同，路径平滑在A*找到路径之后拉直路径；而Theta*可以在A*过程中分析这些路径的，是A*的一部分。
这可以得到比将网格路径后处理成任意角度路径更短的路径。
这篇文章是对该算法的合理介绍；这里是Lazy Theta*。
Theta*的想法很可能也适用于导航网格。
另请参阅Block A*，它声称通过使用分层方法比Theta*快得多。
作者：howeXu_吼徐
博客地址：https://www.cnblogs.com/xuuold/p/10366834.html
|
|
发表于 2019-4-3 11:32:23
