我只使用曼哈顿启发式和曼哈顿以及线性冲突启发式为15谜题编写了A星算法。
我的问题是，对于某些特定的谜题实例，线性冲突是否会导致创建和探索更多的节点，而不是单独使用a-Star的曼哈顿启发式？
由于我尝试通过我的程序解决的大多数谜题实例需要 <50 次移动，只需使用曼哈顿即可在适当的时间内解决给定内存，并更快地解决将其与线性冲突相结合作为启发式，需要>50 次移动的实例会导致程序无限期运行并挂起我的机器，但对于需要 42 个动作的特定问题，我的程序使用 Manhattan 在 ~8 秒内解决，但使用同样的线性冲突会导致程序无限期运行并挂断我的机器。
我已经一遍又一遍地浏览了我的代码，在我的线性冲突或曼哈顿启发式代码中找不到错误。因此，这个一般性问题要确定。
以下实例会导致上述问题。
2,8,7,11 //Takes 42 Moves to solve
5,0,4,15
13,9,14,3
1,10,6,12
曼哈顿启发式和线性冲突的曼哈顿都是可以接受的启发式，即它们从不高估达到目标的努力。此外，线性冲突的曼哈顿比简单的曼哈顿更知情。
我们说启发式 h2 占主导地位，或者如果每个节点 n 的 h2（n）>= h1（n） 比启发式 h1 更明智。在这种情况下，使用 h2 作为启发式的 A* 将始终扩展由 h1 扩展的节点子集。回答你的问题，A*用曼哈顿和线性冲突启发式不能扩展更多的节点，事实上，不能用简单的曼哈顿启发式扩展任何没有被A*扩展的节点，即用曼哈顿线性冲突扩展的A*节点集是用普通曼哈顿扩展的A*节点的子集。
尝试使用调试器查看代码并找到此方案，这可能会帮助您找到实现中的错误。
对于更正式的答案，我鼓励您仔细阅读这篇文章。
关于您的机器在困难问题中挂起的问题，A* 必须存储所有关闭和打开的节点，从而导致内存的指数级浪费。要解决 15 个谜题问题，请使用迭代深化 （IDA*），其中执行时间和内存消耗更好。
虽然，正如 FrankS101 所述，使用曼哈顿距离启发式线性冲突不可能比简单地使用曼赫坦距离扩展更多的节点，但可能需要更多时间。这是因为计算具有线性冲突的曼哈顿距离将使算法在每个节点上"花费"更多时间，因为计算这种启发式方法需要更多时间。