Python中IDastar与Astar解决八数码问题的比较

Question

我开始重新学习人工智能的知识，所以我实现了一些路径寻找算法来解决8拼图问题。

• A*
• IDA*
• 广度优先搜索（BFS）
• 迭代加深深度优先搜索（IDFS）

我在想，为什么我实现的IDA*算法路径更长。它应该和A*一样是最优的。

% python puzzle8.py -a idastar -d hard
IDASTAR - RESULT in 161.6099:
1 | 2 | 3
4 | 5 | 6
7 | 8 | N

cost: 0 total_cost: 121
...
nodes 28

% python puzzle8.py -a astar -d hard
Max nodes 665 loops 1085
ASTAR - RESULT in 0.3148:
1 | 2 | 3
4 | 5 | 6
7 | 8 | N

cost: 0 total_cost: 115
...
nodes 24

代码在这个链接上 https://gist.github.com/1629405

更新：

代码现在指向一个可用的版本。

% python puzzle8.py -a idastar -d hard
IDASTAR - RESULT in 234.4490: 

1 | 2 | 3
4 | 5 | 6
7 | 8 | N
...
nodes 24

但我还是在想，为什么在Python下IDA*的运行时间比A*要长这么多。

更新 2：

代码已经修改，现在可以打印出访问过的节点。

IDASTAR创建了4184368个节点，而ASTAR只创建了1748个节点。

Answer 1

因为你实现的IDASTAR每次迭代时把限制增加10，这样做只能保证你的结果最多比最优解多出9。把增加的数改成1，你就能得到最优解（不过这样会花更多时间）。