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.
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
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ź. –
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