我已经使用曼哈顿距离启发式和曼哈顿距离与线性冲突启发式编写了15数码问题的A星算法。
我的问题是,对于某些特定的谜题实例,线性冲突是否会比仅使用A星的曼哈顿启发式导致更多的节点被创建和探索?
由于我尝试通过我的程序解决的大多数谜题实例需要少于50步才能在给定的内存和时间范围内得到解决,我发现仅使用曼哈顿启发式或将其与线性冲突启发式组合可以更快地解决问题。但是,需要超过50步的实例会导致程序无限运行并挂起我的机器。但是,对于一个需要42步的特定问题,使用曼哈顿距离可以在约8秒钟内解决,但使用线性冲突则会导致程序无限运行并挂起我的机器。
我已经反复检查了我的代码,但是我找不到线性冲突或曼哈顿启发式代码中的错误。因此,这是一个一般性问题,以确保。
以下实例导致了上述问题。
我的问题是,对于某些特定的谜题实例,线性冲突是否会比仅使用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