使用A星算法寻找路径的启发式函数

Question

我正在尝试寻找以下问题的最优解决方案：

每个节点内表示为（x，y）。

相邻节点始终具有当前节点y值+1的y值。

当我们从一个节点到其相邻节点时，x值的更改会产生1的成本。

如果节点之间没有x值的变化，则从节点到其相邻节点不需要成本。

具有相同y值的任何两个节点都不被视为相邻。

最佳解决方案是成本最低的方法，我考虑使用A*路径查找算法来找到最佳解决方案。

我的问题是，A*是否是这种类型问题的好选择，还是我应该看看其他算法，我也在考虑使用递归方法计算启发式成本，但我感觉这不是一个好主意。

这是我如何想到启发式函数的示例：

节点的启发式权重=其子节点的启发式权重的最小值。

子节点也是如此。

但就我所知，启发式应该是近似值，因此我认为我在启发式函数方面走错了路。

- Vamsi

---

该启发式函数必须是可接受的（否则它不仅是A，而只是A），而不仅仅是“近似”的。此外，它还应该计算速度快，否则你得不偿失。除此之外，它还应该是“有用的” - 如果所有成本都是非负数，那么一个常数零启发式将起作用，但这时A *就会降级为BFS。 - harold

那么，你对我目前的启发式算法有什么想法？ - Vamsi

你可以用O(n)的时间复杂度完成它（只需一次），这并不是非常糟糕，但这意味着要触及每个节点（并记住所有结果），所以A*算法失去了其优势。关键在于，毕竟不要探索整个节点空间（因此不是摊销的O(1)）。此外，正如所写的那样，它只有0或1，不是很“有用”，也许你漏了一个+1？ - harold

Answer 1

A*保证可以在非负边路径成本的图中找到最低成本路径，前提是您使用适当的启发式。什么样的启发式函数才是合适的呢？

首先，它必须是“可达到”的，也就是说，对于任何节点，它应该产生低估或正确估计的成本，以便从该节点到任何目标节点的最便宜路径。这意味着启发式函数不应该高估从节点到目标的成本。

请注意，如果你的启发式计算每个节点的估计成本为0，那么A*将变成广度优先的穷举搜索。因此h(n)=0仍然是一个可达到的启发式，只是最糟糕的启发式而已。因此，对于所有可达到的启发式来说，更紧密地估计到目标的成本越好，它就越好。

其次，它必须容易计算。它肯定应该是O(1)，最好只看当前节点。正如您所提出的那样递归地评估成本会使您的搜索显著变慢，而不是更快！

A*的适用性问题在于能否想出一个合理的启发式。根据您的问题描述，不清楚是否可以轻松想出一个。

根据问题域的不同，如果放松要求，则A*可能非常有用。如果启发式变得不可达到，则您将失去找到最佳路径的保证。但是根据距离高估的程度，解决方案仍然可能足够好（对于“足够好”的问题特定定义）。优点在于有时你可以更快地计算出这条“足够好”的路径。在某些情况下，启发式的概率估计效果很好（它可以具有额外的约束条件以保持可达到范围内）。

一般来说，对于可处理的问题，你可以使用广度优先搜索，如果需要更快速的搜索，则可以使用A*算法，其具有可接受的启发式策略。如果你的问题对于广度优先的穷尽搜索来说是不可处理的，并且没有适用的启发式方法，那么你的唯一选择就是接受一个“足够好”的次优解决方案。同样地，即使使用不可接受的启发式策略，A*仍可能适用于此处的问题，或者你可以考虑采用beam search的变体。区别在于，beam search在探索图时有一个当前被探索路径数的限制，而A*则通过选择某些代价较小的子集间接地限制路径数。实际上存在一些无法通过放宽可接受条件后的A*算法来解决的问题，特别是当不同搜索路径之间的成本差距很小时。在这种情况下，beam search的硬性路径数量限制能够更有效地解决问题。

- kkm

Answer 2

似乎使用A*算法有些过度，使用Dijkstra的算法就可以了。在这个例子中，Dijkstra只能用于非负成本转换，这是正确的。如果你可以有负成本转换，那么Bellman-Ford算法也可以使用。

- Justin