Python idastar vs astar puzzle solution 8

Question

I started updating my ai knowledge, so I implemented some pathfind algorithms to solve 8-Puzzle.

• A *
• IDA *
• Bfs
• IDFS

I was wondering why my IDA * implementation has a longer way. It should be optimal, like 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 

The code is on gist https://gist.github.com/1629405

Update:

Now the code points to the working version.

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

But I'm still wondering why IDA * takes much longer python time than A *.

Update 2:

Changed the code that prints now visited sites.

IDASTAR creates 4184368 ASTAR 1748 nodes.

Answer 1

Since your implementation of IDASTAR with each iteration increases the limit by 10, which guarantees only that your solution will be no more than 9 more than optimal. Change the increment to 1, and you should get the optimal result (but this takes more time).