1. módszerAlgoritmusA 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ód2. módszerAlgoritmusRobert 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. A prioritási sor rendezési kulcsa két tételből adódik össze:
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. A ciklikusság kizárására két módszer került szóba:
További részletek: http://en.wikipedia.org/wiki/A*_search_algorithm 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
|
|
|
2004-2016 BDG algoritmus szakkör