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