algorithm - 状态空间搜索 : A* and Breadth First Search

Question

所以我为推箱子游戏实现了 2 个不同的求解器。

求解器很简单，给定一个起始状态(位置)，如果初始状态是目标状态，则返回结果。否则生成子状态并将它们存储到与算法相对应的任何数据结构中。 (BFS 的队列和 A* 的优先级队列)然后它从数据结构中弹出第一个子状态以检查它是否是目标状态，否则生成子状态并存储到结构中，重复此过程直到找到目标状态。

目前，A* 算法确实比 BFS 更好，因此在找到结果之前生成的节点更少。但是，我的问题是 A* 算法需要更长的时间来计算。例如，在其中一个级别中，BFS 算法生成了 26000 个节点，而 A* 仅生成了 3488 个，但 A* 比 BFS 花费了多一秒的时间来完成。

通过使用时间分析器，我得出结论，用于存储节点的优先级队列数据结构是导致这种速度下降的原因。因为每次将节点插入队列时，优先级队列都必须运行启发式函数算法来确定新状态是否应该是最接近目标状态的状态(因此它将该节点放在队列中的第一位)。

现在我的问题是，你们认为这是我的实现的问题，还是由于计算启发式函数引起的开销，这是正常的。

Answer 1

要研究的另一个假设(假设是我们在没有您的代码可供查看的情况下可以做的最好的事情):也许您正在重新计算您的启发式分数(我认为在您的情况下计算这是一个相对昂贵的事情) 不必要的频繁。

您在代码的哪个位置计算启发式分数？你有吗

1. 在将每个节点插入优先级队列之前，对每个节点执行一次此操作，然后将结果存储在某个 Node 对象中，以便您可以在需要时立即检索它？
2. 或者您只计算任何 Comparator 函数/仿函数/等中的启发式分数。您的优先级队列使用它来确定节点的顺序？

在第二种情况下，您将非常频繁地重新计算您之前已经计算过的节点的启发式分数。例如，假设您当前在优先级队列中有 100 个节点，您尝试插入一个新节点。在第二种情况下，插入该新节点可能需要与这 100 个现有节点中的一堆进行比较，然后才能找出新节点所属的位置，因此可能需要进行一系列额外的启发式分数计算。

如果您选择第一个选项(这是我推荐的)，那么这 100 个现有节点和要添加的新节点都将已经计算出它们的启发式分数(恰好一次)，并作为成员存储在内存中多变的。与一堆现有节点执行一堆比较将非常便宜，它只需要获取已经计算的启发式分数而不需要重新计算它们。

实际上，根据您问题中的文字，我怀疑您目前确实在使用(低效的)第二种实现方式。否则您的优先级队列根本不会调用启发式函数。

---

如果使用上述更高效的第一个实现，您仍然在与成本过高的启发式函数作斗争，您可以尝试调查是否有可能在生成后续状态期间编写更高效的增量实现。这是否可能在很大程度上取决于您的启发式函数正在做什么。但是，我可以想象，在某些情况下，如果您已经拥有

• 当前状态s
• 当前启发式得分 h(s)
• 移动到后继状态s'

您可能能够推导出一种高效的增量算法，该算法根据所进行的移动计算如何增量修改 h(s) 以确定 h(s') (然后您可以立即将其存储在 s' 的节点中)