python idastar vs astar solving 8 puzzle

Question

Ho iniziato ad aggiornare la mia conoscenza ai quindi ho implementato alcuni algoritmi di pathfind per risolvere 8-Puzzle.

• A*
• IDA*
• BFS
• IDFS

Mi chiedevo perché mia implementazione di IDA * ha un percorso più lungo. Dovrebbe essere ottimale come 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 

Codice è il succo https://gist.github.com/1629405

Aggiornamento:

codice è ora punta a un lavorare versione.

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

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

ma sto ancora chiedendo perché IDA * vuole così tanto più sotto pitone di A *.

Aggiornamento 2:

codice viene cambiato stampe ora visitati nodi.

IDASTAR crea 4.184.368 ASTAR nodi.

Answer 1

Poiché l'implementazione di IDASTAR incrementa il limite di 10 ad ogni iterazione, che garantisce solo che la soluzione non sarà più di 9 in più rispetto all'ottimale. Cambia l'incremento a 1 e dovresti ottenere un risultato ottimale (ma impiegare più tempo per farlo).