2012-01-17 21 views
6

Zacząłem odświeżać moją wiedzę ai, więc zaimplementowałem kilka algorytmów pathfind do rozwiązania 8-Puzzle.python idastar vs astar solving 8 puzzle

Zastanawiałem się, dlaczego moja realizacja IDA * ma dłuższą drogę. Powinno być optymalne jak 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 

Kod jest na GIST https://gist.github.com/1629405

Aktualizacja:

Code jest teraz wskazując na pracy wersję.

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

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

Ale wciąż zastanawiam się dlaczego tak IDA * trwa znacznie dłużej pod pytona niż A *.

UPDATE 2:

Kod zmienia się drukuje odwiedził teraz węzły.

IDASTAR tworzy ASTAR węzłów.

Odpowiedz

4

Ponieważ twoja implementacja IDASTAR zwiększa z każdą iteracją limit o 10, co gwarantuje, że twoje rozwiązanie nie będzie więcej niż o 9 więcej niż optymalne. Zmień inkrement na 1, a powinieneś uzyskać optymalny wynik (ale zajmie to więcej czasu).

+0

Dzięki zmieniłem kod, aby zwiększyć limit teraz o 1. Ale inne pytanie, dlaczego to tak cholernie ** długie ** zakończyć w idastarze? – delijati

+0

Ile iteracji wykonuje idastar? Ile węzłów rozrasta się w całości, nie tylko w ostatniej iteracji? Odpowiedz na te pytania, a powinieneś znać odpowiedź. –

+1

O tak, tak. Zmieniony kod maxnode zlicza teraz każdy oglądany węzeł. ** ASTAR ** ma 1748 węzłów i ** IDASTAR ** 4184368 węzłów. – delijati