python idastar vs astar解决8个难题

Question

我开始刷新我的知识,所以我实现了一些路径查找算法来解决8-Puzzle.

• 一个*
• 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

代码在gist 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

但我仍然想知道为什么IDA*在python下比A*需要更长的时间.

更新2:

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

IDASTAR创建4184368个爱仕达1748个节点.

Answer 1

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