python idastar vs astar解决8个难题

Question

我开始刷新我的ai知识，所以我实现了一些pathfind算法来解决8-Puzzle。

• 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 

但我仍然不知道为什么IDA *采用下蟒比 A *长得多。

更新2：

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

IDASTAR创建 ASTAR 节点。

Answer 1

因为在每次迭代中，您的IDASTAR实现将限制增加10，这只能保证您的解决方案不会超过9个而不是最优。将增量更改为1，并且您应该获得最佳结果（但需要更长时间才能完成）。