python idastar vs astar giải quyết 8 câu đố

Question

Tôi bắt đầu làm mới kiến ​​thức của mình để tôi thực hiện một số thuật toán pathfind để giải quyết 8-Puzzle.

• A*
• IDA*
• BFS
• IDFS

tôi đã tự hỏi tại sao thực hiện của tôi về IDA * có một con đường dài hơn. Nó phải tối ưu như 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 

Mã là vào ý chính https://gist.github.com/1629405

Cập nhật:

Mã hiện đang trỏ đến một làm việc phiên bản.

% python puzzle8.py -a idastar -d hard 
IDASTAR - RESULT in 234.4490: 

1 | 2 | 3 
4 | 5 | 6 
7 | 8 | N 
... 
nodes 24 

Nhưng tôi vẫn tự hỏi tại sao IDA * phải mất quá nhiều thời gian hơn dưới python hơn A *.

Cập nhật 2:

Mã được thay đổi bản in hiện nay đã đến thăm các nút.

IDASTAR tạo ASTAR nút.

Answer 1

Do việc triển khai IDASTAR của bạn tăng giới hạn lên 10 với mỗi lần lặp, điều này chỉ đảm bảo rằng giải pháp của bạn sẽ không vượt quá 9 tối ưu. Thay đổi số gia tăng thành 1 và bạn sẽ nhận được kết quả tối ưu (nhưng mất nhiều thời gian hơn để thực hiện).