python idastar vs astar解决8 puzz

Question

我开始更新我的人工智能知识，所以我实施了一些寻路算法来解决8字谜。在

• A*
• IDA*
• BFS
• IDFS

我想知道为什么我的IDA*实现会有更长的路要走。它应该是最佳的，就像一个*。在

% 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

更新：

代码现在指向的是一个正在工作的版本。在

^{pr2}$

但我仍然在想，为什么IDA*在pythonpython下花费的时间要比A*长得多。在

更新2:

代码已更改打印现在访问的节点。在

IDASTAR创建4184368ASTAR1748节点。在

Answer 1

因为IDASTAR的实现在每次迭代中都会将限制增加10，这只能保证您的解决方案不会比最优方案多出9个。将增量更改为1，您应该会得到一个最佳结果（但这样做需要更长的时间）。在