0

当我们将 A* 与不可允许的启发式方法一起使用时，我们有时会得到一条非最优路径。

但是当它被允许具有零成本的路径时，我想到的唯一可接受的启发式是h(x) = 0，它将 A* 变成一个“简单”的 Dijkstra 算法。

我对么？这是唯一可能的启发式方法吗？不使用可接受的启发式算法的真正损失是什么？还有其他寻路算法更适用于零成本路径吗？

一个例子：

假设下图（边上方的数字显示成本）：

   1      1      0      1      1
S --> V1 --> V2 --> V3 --> V4 --> G

在哪里：

  • S 表示起始顶点
  • V 表示内部顶点
  • G 表示目标顶点

通过查看图表，我们看到C(S) = 4.

我可以使用什么启发式函数h(x)？如果我使用欧几里得距离，我得到：

f(S) = g(S) + h(S)
f(S) = 0 + 5 = 5

我们可以看到，这种启发式方法高估了真实距离，因此对于更复杂的图，它可能找不到最优解。

4

1 回答 1

2

不对。启发式函数h(x)具有x由当前搜索状态组成的参数。x它返回对目标距离的估计。在一个简单的图中，x是一个图节点。

可接受性要求h(x)只能低估（或等于目标距离）。此条件适用于每个特定的 x。（您似乎在推断条件适用于所有可能的 x，这太强了。如果有必要， A* 将毫无用处。）

关于您提出的案例的正确陈述是，只有当是一个与目标距离为零的状态时才有h(x) = 0必要。任何其他值都将被高估。但是，对于任何其他（在同一状态空间中）需要总成本至少达到目标的转换，我们可以有任何这样的。xxC>0hh(x)<=C

当然，如果x' 到目标的距离为零，x 则为目标状态，搜索完成。所以你的担忧是空洞的——没有任何值得关注的案例。

要构建的信息h(x)来自您对搜索空间的了解（例如图的特征）。光靠一般的图表并不能提供任何有用的东西。您可以做的最好的事情是h(x) = cost of min weight outgoing edge of x针对非目标节点，并且如前所述，h(x) = 0针对目标。再次注意这是到目标距离的下限。它给了你 Dijkstra！

为了做得更好，您需要了解图表的结构。

编辑

在您的示例中，您提供了详细的知识，因此制作商品h很简单。您可以使用

        /  4   if x == S
       |   3   if x == V1 
h(x) = {   2   if x == V2 or V3 
       |   1   if x == V4
        \  0   if x == G

或者您可以使用任何其他功能h'(x)，例如h'(x) <= h(x)all x。例如，这是可以接受的：

         /  3   if x == S
        |   2   if x == V1 
h'(x) = {   2   if x == V2 or V3 
        |   1   if x == V4
         \  0   if x == G

添加

OP指出，对于许多问题，h(x)可能很难选择！这是完全正确的。如果你找不到一个好的可接受的启发式算法，那么 A* 就是错误的算法！尽管如此，A* 对于可以找到启发式的问题非常有效。我自己试过的例子：

  1. 欧几里得距离是任意两个节点之间可能距离的良好下界的图。例如，每对城市 A 和 B 之间的距离为 D，“就像乌鸦飞过一样”，但是从 A 到 B 的道路距离至少是 D 并且可能更多，即它的成本 C 大于或等于 D。在这种情况下，D 是一个很好的启发式算法，因为它是一个低估计值。

  2. 与获胜状态的“距离”涉及移动游戏棋子的谜题。在这种情况下，当前相对于获胜状态不在位置的棋子数量是一种很好的启发式方法。例如，来自第 7 位客人的 8 主教问题（尚未处于最终位置的主教数量）和魔方问题（从所有棋子当前位置到获胜状态下正确位置的总曼哈顿距离）。

于 2013-07-07T02:23:34.707 回答