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