使用A星查找路径的启发式函数

Question

我正在尝试为以下问题找到最佳解决方案

1. 每个节点内表示的数字表示为(x,y).
2. 节点的相邻节点总是具有y(当前节点y值+1)的值.
3. x当我们从一个节点到另一个节点时,值的变化为1
4. 如果没有值的变化,从节点到其相邻节点没有成本x.
5. 没有2个具有相同y值的节点被认为是相邻的.

最优解是成本最低的解决方案,我正在考虑使用A*路径寻找算法来寻找最优解.

我的问题,A*是这类问题的一个很好的选择,或者我应该看看任何其他算法,而且我还在考虑使用递归方法来计算启发式成本,但我感觉它不是好主意.

这是我如何认为启发式函数将是这样的例子

• 节点的启发式权重= Min(它的子节点的启发式权重)
• 子节点也是如此.

但就我所知,启发式意味着是一种近似,所以我认为就启发式函数而言,我的方向是错误的

Answer 1

如果使用适当的启发式算法,A*保证在非负边缘路径成本的图形中找到成本最低的路径.什么使启发式函数适当？

首先,它必须是可接受的,即对于任何节点,它应该对从该节点到任何目标节点的最便宜路径的成本产生低估或正确的估计.这意味着启发式算法永远不应高估从节点到目标的成本.

请注意,如果您的启发式计算每个节点的估计成本为0,那么A*只会变为广度优先的穷举搜索.所以h(n)= 0仍然是一个可接受的启发式算法,只有最差的启发式算法.因此,在所有可接受的启发式算法中,更严格的估算目标的成本越高.

其次,计算必须便宜.它当然应该是O(1),并且最好应该单独查看当前节点.按照您的建议递归评估成本将使搜索速度显着降低,而不是更快!

因此,A*适用性的问题是你能否提出一个相当好的启发式方法.从你的问题描述中,不清楚你是否可以轻松拿出一个.

根据问题域,如果放宽要求,A*可能非常有用.如果启发式变得不可接受,那么你就失去了找到最佳路径的保证.根据对距离的过高估计程度,解决方案可能仍然足够好(对于"足够好"的问题特定定义).优点是,有时您可以更快地计算"足够好"的路径.在某些情况下,启发式的概率估计工作良好(它可能有额外的约束条件,以保持在允许的范围内).

所以,一般来说,你有广度优先搜索易处理问题,接下来你可以更快地得到A*用于可接受启发式的易处理问题.如果你的问题对于广度优先的穷举搜索来说是难以解决的并且不承认启发式,那么你唯一的选择就是找到一个"足够好"的次优解决方案.同样,A*仍然可以在此处使用不可接受的启发式算法,或者您应该查看波束搜索变量.不同之处在于光束搜索对图表当前正在探索的方式有多少限制,而A*通过选择一些较低成本的子集来间接限制它们.有实际情况不是A*即使放松可容许,在不同的搜索路径之间的成本差异是轻微的解.具有对路径数量的硬限制的波束搜索在这些问题中更有效地工作.