Autor Wątek: 8 Puzzle A*  (Przeczytany 4677 razy)

Offline Arkinghor

  • Użytkownik

# Czerwiec 07, 2013, 22:25:13
Witam

Tak jak w temacie mam problem z gra 8 Puzzle i algorytmem A*. Cała zabawa polega na tym że nie bardzo wiem jak użyć tego algorytmu dla takiej gry. Wszystko jest dla mnie jasne w tym algorytmie przy wyszukiwaniu ścieżki z punktu a do punktu b, jednak nie mam bladego pojęcia jak się zabrać dzięki niemu do układania puzzli. Prosiłbym o jakieś nakierowanie bym mógł ruszyć z tematem. Osobiście zastanawiałem się nad tym by po prostu na chama sprawdzić wszystkie możliwości jednak liczę że pomożecie mi wpaść na pomysł jak to zrobić zgrabniej. Z góry dziękuje za zainteresowanie (w google  sprawdzałem jednak wiadomości jakie tam znalazłem były dla mnie nie wystarczające).

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Avaj

  • Użytkownik

# Czerwiec 07, 2013, 22:27:16
Jak wyszukujesz ścieżkę to tworzysz graf, z jakiego pola można przejść do jakiego. Na tym zapuszczasz A* i masz ścieżkę które po kolei węzły odwiedzać.

Tu robisz graf wszystkich możliwych pozycji i jaki ruch prowadzi do jakiej innej pozycji. Zapuszczasz A* i w wyniku dostaniesz kolejne ruchy które trzeba wykonać żeby z pozycji A do pozycji B dojść.

Offline koirat

  • Użytkownik

# Czerwiec 07, 2013, 22:44:39
Ponoć google nie boli.
Cytuj
http://www.brian-borowski.com/Software/Puzzle/
Hasło to "8 puzzle solver"

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 07, 2013, 23:11:09
Cytuj
Tu robisz graf wszystkich możliwych pozycji i jaki ruch prowadzi do jakiej innej pozycji.
Nie robisz, tylko myślisz o grafie. Może jeszcze nie przy 8, ale w tego typu układankach kombinacji mnoży się tyle, że szkoda pamięci na jawne budowanie grafu. Wystarczy tylko kompaktowo pamiętać gdzie się już było i przechodzić między stanami.

Offline Avaj

  • Użytkownik

# Czerwiec 08, 2013, 00:44:39
Nie robisz, tylko myślisz o grafie. Może jeszcze nie przy 8, ale w tego typu układankach kombinacji mnoży się tyle, że szkoda pamięci na jawne budowanie grafu. Wystarczy tylko kompaktowo pamiętać gdzie się już było i przechodzić między stanami.
Mowa jest o 8 puzzle, w 8 puzzle możliwych stanów jest 9, więc nie jest to tak duża liczba. Jak będzie cięższy problem to pogadamy inaczej :)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +1
# Czerwiec 08, 2013, 00:59:58
Cytuj
Mowa jest o 8 puzzle, w 8 puzzle możliwych stanów jest 9, więc nie jest to tak duża liczba.
W swoim szacowaniu pominąłeś jedynie 181431 stanów. Taka niewielka różnica. ;)

W sumie stanów masz dokładnie 9!/2 - połowa z wszystkich permutacji 9 elementów (włącznie z pustym polem) na planszy. Połowa, bo z tego co pamiętam nie jest możliwa zamiana dwóch ostatnich elementów jeżeli układ początkowy był niepoprawny.

Tak czy inaczej, zaczyna tego być na tyle dużo, że szkoda budować jawny graf, bo czas zbudowania grafu ze wszystkimi cache missami może być większy od czasu wyszukiwania.

Offline Arkinghor

  • Użytkownik

# Czerwiec 08, 2013, 08:15:06
Avaj i Krzysiek dziękuję wam bardzo za odpowiedź. Właśnie to stanowiło dla mnie problem nie bardzo wiedziałem jak taki graf ma wyglądać. Teraz już zrozumiałem dzięki :]. Co do twojej odpowiedzi koirat to podkreśliłem że w google szukałem i informacje tam zawarte nie wiele mi pomogły więc twoja wypowiedź jest po prostu ignorancka.

Offline Avaj

  • Użytkownik

# Czerwiec 08, 2013, 09:44:33
W swoim szacowaniu pominąłeś jedynie 181431 stanów. Taka niewielka różnica. ;)

W sumie stanów masz dokładnie 9!/2 - połowa z wszystkich permutacji 9 elementów (włącznie z pustym polem) na planszy. Połowa, bo z tego co pamiętam nie jest możliwa zamiana dwóch ostatnich elementów jeżeli układ początkowy był niepoprawny.

Tak czy inaczej, zaczyna tego być na tyle dużo, że szkoda budować jawny graf, bo czas zbudowania grafu ze wszystkimi cache missami może być większy od czasu wyszukiwania.
dobra, jestem idiotą ;) tak to jest jak się siedzi na forum zamiast iść spać

Offline koirat

  • Użytkownik

# Czerwiec 08, 2013, 13:02:45
Co do twojej odpowiedzi koirat to podkreśliłem że w google szukałem i informacje tam zawarte nie wiele mi pomogły więc twoja wypowiedź jest po prostu ignorancka.
Rzeczywiście napisałeś o gogle, jakoś umknęło to mojej uwadze. Wybacz.
Swoją drogą moja wypowiedź nie jest ignorancka.

Offline Arkinghor

  • Użytkownik

# Czerwiec 08, 2013, 14:42:59
koirat każdemu zdarza się przeoczenie :]. Jeśli chodzi zaś o określenie twojej wypowiedzi jako ignoranckiej nie znałem wszystkich faktów i wydałem werdykt przepraszam za tak pochopne zachowanie. Odnośnie tematu jeśli chodzi o graf to rozumiem że kolejne węzły to stadium naszej układanki.
Można to porównać do pól pokonywanych przez gracza. W A* mam takie wartości jak G,H,F czy tymi wartościami dla węzła będzie suma wartości poszczególnych puzzli?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 08, 2013, 15:14:26
Cytuj
W A* mam takie wartości jak G,H,F czy tymi wartościami dla węzła będzie suma wartości poszczególnych puzzli?
A* opiera się na tym, że możesz mniej więcej określić jaka odległość została Ci do celu. W tym przypadku można policzyć odległość każdego kafelka od miejsca gdzie powinien być (metryką taksówkarską), zsumować i podzielić przez dwa - to będzie dolne ograniczenie na liczbę ruchów.

Offline koirat

  • Użytkownik

# Czerwiec 08, 2013, 15:29:54
Użyłeś chyba najmniej powszechnej nazwy na tą metrykę (taksówkarska), aż zmusiłeś mnie do wejścia na google :). Aby oszczędzić wycieczek forumowiczom dodam iż chodzi o metrykę Manhattan albo inaczej zwaną metrykę miejską. Na polskiej wiki nazywają ją nawet Metryką "Miasto".

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +2
# Czerwiec 08, 2013, 15:58:23
Użyłeś chyba najmniej powszechnej nazwy na tą metrykę (taksówkarska)
W sumie to prawdziwa metryka taksówkarska powinna naliczać dychę na samym starcie i w nocy mnożyć przez dwa, ale wtedy by nie była metryką. ;)

Offline Kos

  • Użytkownik
    • kos.gd

# Czerwiec 08, 2013, 16:05:10
Te metryki to śmieszna sprawa; wiążą się z normami wektorów.

N-ta Norma wektora 2D to (a^N + b^N) ^ (1/N). Dla wyższych wymiarów analogicznie.

- Dla N=1 mamy zwykłe a+b, czyli metrykę taksówkową, miejską, Manhattan, whatever.
- Podstawiając za N dwójkę otrzymujemy sqrt(a*a + b*b) - czyli w praniu odległość Euklidesową (patrz też: norma Frobeniusa)
- Natomiast jak N idzie do nieskończoności, to równanie zbiega się do zwykłego max(a,b), czyli do metryki Czebyszewa (szachownicowej).

wiki: odległość Minkowskiego


Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 08, 2013, 17:08:23
Cytuj
Te metryki to śmieszna sprawa; wiążą się z normami wektorów.
Normy wektorów to tylko bardzo specyficzny zbiór metryk dla bardzo specyficznej grupy przestrzeni.