python idastar vs astar solving 8 puzzle

Question

私は私の知識をリフレッシュし始めたので、私は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 *は*よりもパイソンの下でそんなに長い時間がかかり、なぜ私はまだ思ったんだけど。

アップデート2：

コードが変更されたプリントは、今のノードを訪問しました。

IDASTARは、 ASTAR ノードを作成します。

Answer 1

IDASTARを実装すると、反復ごとに10ずつ増分されるため、ソリューションの最適性が9を超えないことが保証されます。インクリメントを1に変更すると、最適な結果が得られるはずです（ただし、それにかかる時間は長くかかります）。