python idastar vs astar解决8个难题

Question

我开始更新我的 AI 知识，所以我实现了一些寻路算法来解决 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

但我仍然想知道为什么 IDA* 在 python 下比 A* 花费的时间长得多。

更新 2:

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

IDASTAR 创建 4184368 ASTAR 1748 节点。

Answer 1

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