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