星型算法：使用启发式值作为节点具有相同 F 值的 Tie-breaker

Question

背景：我目前正在研究原始 A Star 算法的 8 拼图实现，并将其与略微修改的算法进行比较，该算法旨在改善节点扩展（使用额外信息，当然，A Star 在同样知情的单向搜索已被证明是最佳的）。节点的 Open List 当前按其 F 值排序（G-Cost+ H-Cost）。

所以在 Java 中实现这个时，我设置了一个比较器，它按 F 值升序排列列表。

       @Override
    public int compare(PNode o1, PNode o2) {
        return Integer.compare(o1.costF, o2.costF);
    }

问题：我的问题是：

A-star 是否允许使用启发式成本（H 值）在 A-Star 中实施进一步的决胜局，以打破许多节点之间的 F 值僵局（其中节点与Open List 中相同的 F 值，它们将按启发式值 (H-Cost) 升序排序）。我对此感到困惑的原因是实际的 A 星算法伪代码仅按 F 值对 Open List 进行排序。

扩展上面的相同代码，实现将是：

        @Override
    public int compare(PNode o1, PNode o2) {
        if (o1.costF == o2.costF) {
            return Integer.compare(o1.costH, o2.costH);
        }
        return Integer.compare(o1.costF, o2.costF);
    }

如果允许这样做，有什么理由让我应该警惕这样做吗？从逻辑上讲，我很欣赏订购开放列表会更昂贵。但从我的实验来看，差异似乎不足以阻止我使用它。

非常感谢大家~

Answer 1

我认为这是可以的，原因有二

1) 你只是改变了关系的行为，所以你所做的只是从原始版本可能的更大的一组执行路径中选择一个可能的执行路径。

2) 你保留属性如果你从开放列表中检索目标节点，开放中的每个其他节点的 G-Cost + H-Cost 至少与节点的 G-Cost + H-Cost 一样昂贵您刚刚检索到，因此必须通向目标节点的路径至少与您刚刚检索到的节点一样昂贵。

通过在平局的情况下偏爱具有低启发式成本的节点，您在平局的情况下偏爱任何目标节点，所以我猜您可能会稍微早一点检索目标节点，因此会稍微早一点完成。

Answer 2

是的，这是允许的，几乎是出于 .

中所述的原因

但是，我想补充一点，这通常实际上是一个非常好的主意，并且比该答案中暗示的要有益得多。这种决胜局可以 比仅仅更早地找到目标更显着地提高性能 。例如，参见 this page，它可视化了 A* 如何在没有决胜局的情况下仍然探索相当大的区域，并且在有决胜局的情况下仅沿着最佳路径探索非常窄的带。

直觉上，您可以通过思考 "reliability" 的 G 成本与 H 成本的不同水平来理解它是如此有效。 G 成本是非常可靠的，它们是真实的，它们恰恰是你为了到达一个节点而真正已经必须支付的成本。 H 成本不太可靠，它们是启发式的，它们可能会大错特错。通过实施您提议的决胜局，您实际上是在说 "whenever two nodes have the same value for F = G + H, I prefer those with greater G and smaller H over those with smaller G and greater H"。这是明智的，因为当 F 的更可靠的 G 组件支配不太可靠的 H 组件时，F 本身也会更可靠。

另一个主要优点是，正如我链接到的页面上所描述的那样，这个决胜局可以避免探索许多不同路径的大部分，这些路径都是平等的并且都是最优的。

Answer 3

可以更改启发式以保证更少的点等于 F [本文]1

The quick hack to work around this problem is to either adjust the g or h values. The tie breaker needs to be deterministic with respect to the vertex (i.e., it shouldn’t be a random number), and it needs to make the f values differ. Since A* sorts by f value, making them different means only one of the “equivalent” f values will be explored.

One way to break ties is to nudge the scale of h slightly. If we scale it downwards, then f will increase as we move towards the goal. Unfortunately, this means that A* will prefer to expand vertices close to the starting point instead of vertices close to the goal. We can instead scale h upwards slightly (even by 0.1%). A* will prefer to expand vertices close to the goal.

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001

星型算法：使用启发式值作为节点具有相同 F 值的 Tie-breaker

A star algorithm: using Heuristic value to act as Tie-breaker where nodes have identical F-values

algorithm

a-star

heuristics