所以我为游戏推箱子实现了 2 个不同的求解器。
求解器很简单，给定一个起始状态（位置），如果初始状态是目标状态，则返回结果。否则生成子状态并将它们存储到与算法相对应的任何数据结构中。（BFS 的队列和 A* 的优先级队列）然后它从数据结构中弹出第一个子状态以检查它是否是目标状态，否则生成子状态并存储到结构中，重复此过程直到找到目标状态。
目前，A* 算法确实比 BFS 更好，因此在找到结果之前生成的节点更少。但是，我的问题是 A* 算法需要更长的时间来计算。例如，在其中一个级别中，BFS 算法生成了 26000 个节点，而 A* 只生成了 3488 个节点，但 A* 比 BFS 花费了一秒钟的时间来完成。
通过使用时间分析器，我得出结论，用于存储节点的优先级队列数据结构是造成这种减速的原因。因为每次将节点插入队列时，优先级队列都必须运行启发式函数算法来确定新状态是否应该是最接近目标状态的状态（因此它将该节点放在队列中的第一个位置）。
现在我的问题是，你们认为这是我的实现有问题还是这是正常的，因为计算启发式函数会产生开销。
另一个要研究的假设（假设是我们可以在没有您的代码可供查看的情况下做的最好的事情）：也许您正在重新计算您的启发式分数（我认为在您的情况下计算这是一个相对昂贵的事情）不必要地经常.
您在代码中的哪个位置计算启发式分数？你
Node对象中，以便您可以在需要时立即检索它？Comparator函数/函子/等内部的启发式分数。您的优先级队列使用它来确定节点的顺序？在第二种情况下，您将非常频繁地重新计算您之前已经完成的节点的启发式分数。例如，假设您当前在优先级队列中有 100 个节点，并且您尝试插入一个新节点。在第二种情况下，插入新节点可能需要与这 100 个现有节点中的一堆进行比较，然后才能确定新节点所属的位置，因此可能需要一堆额外的启发式分数计算。
如果您使用第一个选项（这是我推荐的），那么这 100 个现有节点和要添加的新节点都已经计算了它们的启发式分数（恰好一次），并作为成员变量存储在内存中。与一堆现有节点执行一堆比较将非常便宜，它只需要获取已经计算的启发式分数，而不需要重新计算它们。
实际上，根据您问题中的文字，我怀疑您目前确实在使用（低效的）第二个实现。否则，您的优先队列根本不会调用启发式函数。
如果使用上述更高效的第一个实现，您仍然在为成本过高的启发式函数而苦苦挣扎，您可以尝试调查是否有可能在生成后继状态期间编写更高效的增量实现。这是否可能在很大程度上取决于您的启发式函数正在做什么。但是，我可以想象，在某些情况下，如果你已经有了
sh(s)s'您可以推导出一个高效的增量算法，该算法根据所做的移动计算如何h(s)增量修改以确定h(s')（然后您可以立即将其存储在节点中s'）
您确定您实际上使用的是堆栈而不是 BFS 队列吗？如果您使用的是堆栈，那么您正在做的是一个 DFS，这可能并不总是为您提供通往目标的最短路径。
至于为什么你的 A* 更慢，我认为如果你的优先级队列正在执行 O(Log(N)) 插入/删除（如果不是，那是你的问题），我认为在不知道启发式函数的复杂性的情况下很难说）。如果您的启发式方法做了很多工作，它可能会主导所需的计算，并否定查看更少节点的任何收益。
如果启发式函数确实是罪魁祸首，一个可能的解决方案是使用更简单的启发式。
你的实现有问题。当您想比使用基本（但可能是精确的）方法更快地解决问题时，可以使用启发式方法。他们用最优性来换取速度：你冒着获得不完美解决方案的风险来换取快速获得它。使用使您的方法比其确切版本慢的启发式方法是没有意义的。
当然，如果不深入了解您的实现，不可能更有帮助，但我可以向您保证，如果您的启发式方法使您的求解器变慢，那么使用它是不值得的。