Programozás‎ > ‎Feladatok‎ > ‎Tologatós játék‎ > ‎

Megoldás

1. módszer

Algoritmus

A játék állapotai a tábla elrendezéséből és az elrendezéshez vezető lépésszámból fognak állni. Kezdetben nulla lépést tettünk meg, és a kiinduló helyzetben van a tábla. Ezt a keresési csomópontot egy sorba tesszük. Az algoritmus mindig kiveszi a sorból a következő állapotot, és annak összes rákövetkezőjét (ahova léphetünk belőle) beteszi a sorba, amennyiben az új csomóponthoz tartozó állás még nem fordult elő.

Hornák Bence ötlete: A keresési csomópontokhoz ne csupán azt tároljuk el, hogy hány lépésben jutottunk abba az állapotba, hanem írjuk fel az odavezető lépéseket is. Itt a lépés a {F, J, L, B} egy eleme, így 2 biten kódolható.

Ennek a megoldásnak az a gyenge pontja, hogy nagyon sok állást bejárhatunk, amíg a célba érünk, ezért amikor egy új állapot korábbi előfordulását ellenőrizzük, előfordulhat, hogy nagyon hosszú listában kell keresnünk. Lineáris keresést használva az algoritmus összlépésszáma négyzetes lesz, ami nem elég gyors, már egy 4x4-es tábla esetén sem.

Kód

Hornák Bence (java): Tologatos.java    Allapot.java    Utvonal.java     becsomagolva: Tologatos.jar

2. módszer

Algoritmus

Robert Sedgewick jegyzete alapján.

A* algoritmus

Az előző algoritmus egy lehetséges javítása: legrövidebb út illetve leggyorsabb megoldás megtalálásához használható az A* algoritmus. Hasonlóan a naiv algoritmushoz egy sorban tároljuk a felfedezett csomópontokat. Az újdonság abban van, hogy nem egyszerű sort, hanem prioritási sort használunk. 

Út hosszának becslése

A prioritási sor rendezési kulcsa két tételből adódik össze:
  • az adott állapotba vezető út hossza;
  • egy alsó becslés (heurisztika) arra nézve, hogy az adott állapotból még hány lépés kell a cél eléréséhez.
Az algoritmus a prioritási sorból mindig a legkisebb kulcsú csomópontot veszi ki, vagyis abból az állapotból próbál továbbhaladni, amiről pillanatnyilag úgy látszik, hogy rajta keresztül vezet a legrövidebb út a célba.

Körök kezelése

A ciklikusság kizárására két módszer került szóba:
  • tárolhatjuk egy halmazban a már bejárt állapotokat
  • illetve ha tudjuk, hogy van út a célba, akkor elég, ha a triviális A -> B -> A alakú köröket zárjuk ki, hiszen a hosszabb körök a prioritási sor rendezése miatt nem kerülnek be a felépített útba. A rövid körök kizárásához csak annyi kell, hogy mindig tároljuk az előző állapotot, és azt nem rakjuk be újra a sorba, rögtön a következő lépésben.

Mikor oldható meg egy tábla?

Viszonylag ismert, hogy a tologatós játék megoldhatósága a kinduló permutáció paritásán múlik. Páros és páratlan N esetén picit máshogy néz ki az invariáns.

Kód

Erben Péter (a Sedgewick jegyzet alapján, java): Solver.java    Board.java    MinPQ.java