Długi czas przeszukiwania grafu

Witam wszystkich,

Dostałem zadanie napisania programu układanki nxn z jednym pustym polem, który przesuwamy (bodajże Pietnastka). Program ma się opierać na losowości tj. ma sprawdzać wszystkie możliwe opcje i kiedy natrafi na wynik ma podać do pliku listę kroków od stanu początkowego do wynikowego strategią wszerz. Zrobiłem i działa ale mam wątpliwości co do czasu wykonania. Dla macierzy 2x2 znajduje w sekundę. Na macierzy 3x3 zajmuje mu to od minuty do 40 minut nawet. Na 4x4 raz się zdarzyło, że znalazł po chwili, a później mogłem sobie czekać ale nie mam pojęcia ile bym na to czekał... Taki długi czaj jest normalny?

Co mogę zrobić by przyśpieszyć jego zadanie? Dodam, że następnym programem na liście mam zaimplementować to samo ale ze strategią A*, który jeśli dobrze rozumie to muszę najpierw stworzyć cały graf z możliwymi stanami, a później go przeszukać i znaleźć najkrótszą drogę.. Toż to będę musiał go odpalić na godzinę przed zajęciami żeby go pokazać wykładowcy..

Obawiam sie że chyba nie zrozumiałeś polecenia. Przecież taki algorytm który robi losowe ruchy to moze działać i milion lat. Wystarczy że ci się zapętli i będzie robił x->y, y->x w kółko. Tutaj należy jednak trochę pomyśleć.

Tutaj:
https://github.com/truongkma/ctf-tools/blob/master/puzzlefull.py
masz przykład jak się to rozwiązuje.

W szczególności dość istotne jest żeby nie wchodzić ponownie do stanu który już odwiedziłeś. To co miałeś zrobić na początku to pewnie poszukiwanie wyczerpujące, czyli testowanie rekurencyjnie wszystkich możliwych stanów na zasadzie BFSa albo DFSa. Czyli:
Dla DFS -> wykonujemy losowy ruch, wykonujemy losowy ruch, ...., nie możemy wykonać ruchu bo każdy ruch z tego miejsca prowadzi do stanu który juz odwiedzilismy, więc wycofujemy się o 1 ruch i sprawdzamy kolejną opcje z tamtej pozycji.

Dokładnie tak jak mówisz, sprawdzam czy dany element już nie występuje w kolejce. Jeśli występuje to nie dodaje go ponownie, a biorę kolejny możliwy losowy ruch. I to działa bo kiedy biorę macierz 2x2 i zamienię elementy tak że będzie biegał w kółko to od razu się wysypuje bo zapełnia graf wszystkimi możliwymi ruchami, a nie znajduje rozwiązania. Polecenie brzmi: Napisz program rozwiązujący układankę nxn wykorzystując strategie przeszukiwaniu grafu wszerz.

Ty chyba sobie robisz żarty teraz. Umiesz ty liczyć? Matematyka dyskretna była? To weź mi policz ile jest możliwych układów tych 3 biednych klocków na planszy 2x2. A teraz weź policz ile będzie możliwych układów 8 klocków na planszy 3x3. 3x3 to jest raptem 9 pól czyli masz 9! możliwości przy założeniu ze wszystkie są osiągalne. To jest raptem 500k możliwych ustawień. Twój komputer ma zapewne procesor ~3GHz czyli potrafi wykonać 3 miliardy cykli zegarowych na sekundę. Nawet jakby sprawdzenie jednego układu zajmowało 1000 cykli (a nie zajmuje pewnie nawet 100) to nadal miałbyś 3 milony możliwości sprawdzonych na sekundę. A ty twierdzisz że 0,5mln sprawdza ci sie 20 minut.

Poza tym skoro to jest BFS to przecież jest deterministyczny i nie jest możliwe żeby czasy ci się nagle diametralnie różniły między wywołaniami, nawet jeśli randomizujesz kolejność ścieżek z danego wierzchołka.

Twój problem jest tutaj: sprawdzam czy dany element już nie występuje w kolejce co jest idiotyczne. Interesuje cie czy wierzchołek KIEDYKOLWIEK nie był już odwiedzony a kolejka przechowuje przecież tylko te które planujesz odwiedzić w przyszłości. W efekcie oczywiście wielokrotnie sprawdzasz te same ustawienia. Musisz oznaczać wierzchołki na których już kiedyś byłeś i nie wchodzić do nich ponownie.