线性冲突启发式算法在使用A*算法解决15数码问题时，是否会创建和探索更多的节点比曼哈顿启发式算法？

Question

我已经使用曼哈顿距离启发式和曼哈顿距离与线性冲突启发式编写了15数码问题的A星算法。

我的问题是，对于某些特定的谜题实例，线性冲突是否会比仅使用A星的曼哈顿启发式导致更多的节点被创建和探索？

由于我尝试通过我的程序解决的大多数谜题实例需要少于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

- PhoenixDD

Answer 1

曼哈顿启发式和带有线性冲突的曼哈顿都是可接受的启发式算法，即它们永远不会高估到达目标的努力。此外，带有线性冲突的曼哈顿比简单的曼哈顿更加明智。

我们说一个启发式h2支配或比启发式h1更明智，如果对于每个节点n，h2(n) >= h1(n)。在这种情况下，使用h2作为启发式的A*将始终扩展由h1扩展的节点的子集。回答您的问题，使用曼哈顿和线性冲突启发式的A*不能扩展更多的节点，实际上，不能扩展任何未被简单曼哈顿启发式扩展的节点，即使用曼哈顿-线性冲突的A*扩展的节点集是由纯曼哈顿A*扩展的节点集的子集。

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

对于更正式的回答，我建议您仔细阅读这篇文章。

关于您的机器在遇到困难问题时挂起的问题，A*必须存储所有关闭和打开的节点，导致指数级的内存浪费。要解决15拼图问题，请使用迭代加深（IDA*），其中执行时间和内存消耗更好。

- FrankS101

---

是的，我找到了程序中的问题，但我仍然想确认一下。另外，让我用不同的方式提问，对于某些问题，使用线性冲突是否会导致选择正确的目标路径比使用曼哈顿更晚？我希望你能理解我在这里尝试询问的内容。 - PhoenixDD

总之，是的，这种情况可能发生，但我在评论中没有足够的空间来回答。请在一个新问题中详细说明，并且我会在那里回答。 - FrankS101

Answer 2

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

- oded betzalel

---

这可能是真的，但只适用于非常罕见的情况，因为当使用线性冲突时，扩展的节点数量与曼哈顿相比会大大减少，因此计算线性冲突+曼哈顿和仅使用曼哈顿之间的时间差似乎微不足道，因为算法仍然比仅使用曼哈顿快得多！ :) - PhoenixDD