状态空间搜索: A*和广度优先搜索

Question

因此，我已经实现了两个不同的解决方案的游戏索科班。

如果初始状态是目标状态，则返回结果。否则生成子状态并将其存储到与该算法相对应的任何数据结构中。( 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'的节点中)进行计算。

Answer 2

您确定您实际上使用的是堆栈而不是BFS的队列吗？如果您使用的是堆栈，那么您所做的就是DFS，这可能并不总是给您达到目标的最短路径。

至于为什么您的A*速度较慢，如果您的优先级队列正在执行O(Log(N))插入/删除(如果不是，则有问题)，那么很难不知道您的启发式函数的复杂性。如果您的启发式正在做大量的工作，它可能主导所需的计算，并否定任何好处从看更少的节点。

如果启发式函数确实是罪魁祸首，那么一个可能的解决方案就是使用更简单的启发式。

Answer 3

你的实现有问题。当您想要解决问题时，更快会使用启发式方法，而不是使用基本(但可能精确)的方法。他们用最优来换取速度:你冒着得到一个不完美的解决方案的风险，而换来的是快速得到它。使用一种使您的方法比其精确版本慢的启发式方法是没有意义的。

当然，如果不了解更多关于您的实现的知识，就不可能提供更多帮助，但我可以向您保证，如果您的启发式使您的求解程序更慢，那么使用它是不值得的。