星型算法：使用启发式值作为节点具有相同 F 值的决胜局

Question

背景：我目前正在研究原始 A Star 算法的 8-puzzle 实现，并将其与旨在改善节点扩展的略微修改的算法进行比较（使用附加信息，当然，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);
    }

问题：我的问题是：

1. 是否允许在 A-star 下使用启发式成本（H 值）在 A-Star 中实施进一步的决胜局，以打破许多节点之间与 F 值的任何僵局（其中存在具有相同 F 值的节点）？ Open List 它们将按启发式值（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);
    }

2. 如果允许这样做，是否有任何理由让我对这样做保持警惕？从逻辑上讲，我理解订购 Open List 的成本会更高。但是从我的实验来看，差异似乎不足以阻止我使用它。

非常感谢大家~

Answer 1

是的，这是允许的，几乎是出于mcdowella 的回答中所述的原因。

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

直观地，您可以通过考虑G成本与H成本的不同“可靠性”级别来理解它是如此有效。G成本是非常可靠的，它们是真实的，它们正是你到达一个节点真正必须支付的成本。H成本更不可靠，它们是启发式的，它们可能是非常错误的。通过实施决胜你建议，你基本上是说“只要两个节点具有相同的价值F = G + H，我更喜欢那些有更大G和更小的H比那些规模较小G和较大H”。这是明智的，因为当更可靠的G组件F支配不太可靠的H组件时，F 本身也会更加可靠。

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