我已经用曼哈顿启发式和曼哈顿线性冲突启发式为15个谜题编写了a-star算法。
我的问题是，对于某些特定的谜题实例，线性冲突是否会导致创建和探索比仅使用a-star的曼哈顿启发式方法更多的节点？
由于我试图通过我的程序解决的大多数谜题实例需要50个移动的实例会导致程序无限期运行并挂断我的机器，但是对于一个需要42步的特定问题，我的程序用曼哈顿在8秒钟内就解决了，但是使用线性冲突同样会导致程序无限期运行并挂断我的机器。
我一遍又一遍地检查我的代码，在我的线性冲突或曼哈顿启发式代码中找不到错误，因此，要确定这个一般性的问题。
以下实例导致上述问题。
2,8,7,11 //Takes 42 Moves to solve
5,0,4,15
13,9,14,3
1,10,6,12
最佳答案
曼哈顿启发式算法和曼哈顿线性冲突启发式算法都是可接受的，即它们从不高估达到目标的努力。此外，线性冲突的曼哈顿比简单的曼哈顿更为知情。
我们说启发式的h2占主导地位，或者如果h2（n）>=h1（n）对于每个节点n比启发式的h1更有信息。在这种情况下，使用h2作为启发式的a*将总是扩展h1扩展的节点子集。回答你的问题，a*用曼哈顿和线性冲突启发式不能扩展更多的节点，事实上，用简单的曼哈顿启发式不能扩展任何没有a*扩展的节点，即用曼哈顿线性冲突扩展a*的节点集是用普通曼哈顿扩展a*的节点子集。
尝试使用调试器检查代码并找到此方案，这可能有助于在实现中找到错误。
对于更正式的回答，我鼓励您仔细阅读这篇post。
关于您的机器在困难问题中挂起的问题，a*必须存储所有关闭和打开的节点，导致内存的指数级浪费。要解决15个谜题，可以使用迭代深化（ida*），这样执行时间和内存消耗会更好。