问线性冲突启发会导致更多的节点被创建和探索比曼哈顿启发与A星15-谜？

EN

具有线性冲突的曼哈顿启发式算法和具有线性冲突的曼哈顿都是容许启发式算法()，也就是说，它们从不高估实现目标的努力。此外，具有线性冲突的曼哈顿比简单的曼哈顿更有见识。

如果(N) >= h1(n)对于每一个节点n，则称为h2(n) >= h1 (N)，或者说它比启发式h2 (N)>=h1(N)更明智。在这种情况下，使用A*使用h2作为启发式，总是会扩展由h1扩展的节点子集。在回答您的问题时，A*使用曼哈顿和线性冲突启发式不能扩展更多的节点，实际上，不能用简单的曼哈顿启发式扩展任何未被A*扩展的节点，即A*与曼哈顿线性冲突扩展的节点集合是A*与普通曼哈顿扩展的节点的子集。

尝试使用调试器检查您的代码并找到这个场景，这可能会帮助您在实现中找到错误。

对于一个更正式的答案，我鼓励你仔细阅读这个post。

关于您的问题，您的机器挂在困难的问题上，A*必须存储所有关闭的和开放的节点，造成内存的指数浪费。为了解决15个难题，需要迭代深化(IDA*)，在那里执行时间和内存消耗更好。

虽然，正如FrankS101所述，使用带有线性冲突的曼哈顿距离启发式算法比简单地使用manhttan距离扩展更多的节点是不可能的，但可能需要更多的时间。这是因为用线性冲突计算曼哈顿距离会使算法在每个节点上“花费”更多的时间，因为计算这种启发式需要更多的时间。