streamalism.org

1. Bemutatkozás

Ebben a cikkben megvizsgáljuk az útvesztőben történő navigálás lehetséges módjait a Java használatával.

Tekintsük az útvesztőt fekete-fehér képnek, amelynek fekete képpontjai a falakat, a fehér képpontok pedig egy utat jelölnek. Két fehér képpont különleges, az egyik a labirintusba való belépés, a másik pedig a kijárat.

Ilyen labirintusban meg akarunk találni egy utat a bejárattól a kijáratig.

2. Az útvesztő modellezése

A labirintust 2D-s egész tömbnek tekintjük. A tömb számértékeinek jelentése a következő megegyezés szerint történik:

• 0 -> Út
• 1 -> Fal
• 2 -> Labirintus bejegyzés
• 3 -> Labirintus kijárat
• 4 -> Az út cellájának része a belépéstől a kilépésig

A labirintust grafikonként modellezzük. A belépés és kilépés a két speciális csomópont, amelyek között meg kell határozni az utat.

Egy tipikus gráfnak két tulajdonsága van, csomópontok és élek. Egy él határozza meg a gráf kapcsolatát, és összeköti az egyik csomópontot a másiksal.

Ezért négy implicit élt feltételezünk minden csomópontból, összekapcsolva az adott csomópontot annak bal, jobb, felső és alsó csomópontjával.

Határozzuk meg a metódus aláírását:

nyilvános lista megoldása (labirintus labirintus) {}

A módszer bemenete a labirintus, amely tartalmazza a 2D tömböt, a fent definiált elnevezési szokásokkal.

A módszer válasza a csomópontok listája, amely utat képez a belépési csomóponttól a kilépési csomópontig.

3. Rekurzív backtracker (DFS)

3.1. Algoritmus

Az egyik meglehetősen nyilvánvaló megközelítés az összes lehetséges út feltárása, amely végül megtalálja az utat, ha létezik. De egy ilyen megközelítés exponenciális összetettséggel bír, és nem méretezhető jól.

Lehetséges azonban a fent említett nyers erőmegoldás testreszabása a visszalátogatással és a meglátogatott csomópontok megjelölésével, ésszerű idő alatt elérni az utat. Ez az algoritmus más néven Mélység-első keresés.

Ez az algoritmus a következőképpen vázolható fel:

1. Ha a falnál vagy egy már meglátogatott csomópontnál vagyunk, akkor a visszatérési hiba
2. Egyébként, ha mi vagyunk a kilépési csomópont, akkor térjen vissza a sikerhez
3. Másként adja hozzá a csomópontot az útvonallistához, és rekurzívan haladjon mind a négy irányba. Ha a hiba visszatér, távolítsa el a csomópontot az útvonalról, és adja vissza a hibát. Az elérési útvonal egyedi utat fog tartalmazni, amikor a kilépés megtalálható

Alkalmazzuk ezt az algoritmust az 1 (a) ábrán látható labirintusra, ahol S a kiindulópont és E a kijárat.

Minden csomópontnál minden irányt keresztezünk sorrendben: jobbra, lentre, balra, fentre.

Az 1 (b) bekezdésben feltárunk egy utat és a falnak ütközünk. Ezután visszalépünk, amíg meg nem találunk egy olyan csomópontot, amelynek nem fali szomszédjai vannak, és vizsgáljuk meg az 1 (c) pontban bemutatott másik utat.

Ismét a falnak ütközünk, és megismételjük a folyamatot, hogy végül megtaláljuk a kijáratot, amint az az 1. d) pontban látható:

3.2. Végrehajtás

Most nézzük meg a Java implementációt:

Először meg kell határoznunk a négy irányt. Ezt koordinátákkal határozhatjuk meg. Ezek a koordináták, ha hozzá vannak adva egy adott koordinátához, a szomszédos koordináták egyikét adják vissza:

privát statikus int [] [] IRÁNYOK = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 

Szükségünk van egy segédprogramra is, amely két koordinátát ad hozzá:

privát koordináta getNextCoordinate (int sor, int col, int i, int j) {return new Coordinate (row + i, col + j); }

Most definiálhatjuk a metódus aláírását megoldani.A logika itt egyszerű - ha van útvonal a belépéstől a kilépésig, akkor adja vissza az utat, különben pedig adjon vissza egy üres listát:

public List megoldás (Maze labirintus) {List path = new ArrayList (); if (Explore (labirintus, labirintus.getEntry (). getX (), labirintus.getEntry (). getY (), elérési út)) {return path; } return Collections.emptyList (); }

Határozzuk meg a Fedezd fel fent hivatkozott módszer. Ha van elérési út, akkor adja vissza az igaz értéket, a koordináták listájával az argumentumban pálya. Ennek a módszernek három fő blokkja van.

Először elvetjük az érvénytelen csomópontokat, vagyis azokat a csomópontokat, amelyek az útvesztőn kívül vannak, vagy a fal részét képezik. Ezt követően meglátogatjuk az aktuális csomópontot látogatottként, hogy ne keressük fel újra és újra ugyanazt a csomópontot.

Végül rekurzívan haladunk minden irányba, ha a kijárat nem található:

privát logikai felfedezés (Labirintus labirintus, int sor, int col, Lista útvonala) {if (! labirintus.isValidLocation (sor, oszlop) || maze.isWall (sor, oszlop) || maze.isExplored (sor, oszlop)) { return false; } path.add (új Koordinátor (sor, oszlop)); labirintus.setVisited (sor, oszlop, igaz); if (labirintus.isExit (sor, oszlop)) {return true; } for (int [] direction: DIRECTIONS) {Koordináta koordináta = getNextCoordinate (sor, oszlop, irány [0], irány [1]); if (explore (labirintus, koordináta.getX (), koordináta.getY (), elérési út)) {return true; }} path.remove (elérési út.méret () - 1); return false; }

Ez a megoldás a verem méretét használja a labirintus méretéig.

4. Változat - legrövidebb út (BFS)

4.1. Algoritmus

A fent leírt rekurzív algoritmus megtalálja az utat, de nem feltétlenül a legrövidebb út. A legrövidebb út megtalálásához használhatunk egy másik gráfátjárási megközelítést, amelyet Szélesség-első keresés néven ismerünk.

A DFS-ben először egy gyermeket és annak unokáit fedezték fel, mielőtt egy másik gyermekhez költöztek volna. Míg a BFS-ben az összes közvetlen gyereket felfedezzük, mielőtt áttérnénk az unokákra. Ez biztosítja, hogy az összes csomópont egy bizonyos távolságban legyen a szülőcsomóponttól, egyidejűleg feltárásra kerül.

Az algoritmus a következőképpen vázolható fel:

1. Adja hozzá a kezdő csomópontot a sorba
2. Amíg a sor nem üres, nyisson meg egy csomópontot, tegye a következőket:
   1. Ha elérjük a falat, vagy ha a csomópont már meglátogatott, ugorjon a következő iterációra
   2. Ha eléri a kilépési csomópontot, akkor a legrövidebb út megtalálásához lépjen vissza az aktuális csomóponttól az indító csomópontig
   3. Egyébként adja hozzá az összes közvetlen szomszédot a sorban lévő négy irányba

Egy fontos dolog itt az, hogy a csomópontoknak nyomon kell követniük szülőjüket, vagyis onnan, ahonnan felvették őket a sorba. Ez fontos az elérési út megtalálásához, ha a kilépési csomópont találkozik.

A következő animáció megmutatja az labirintus ezen algoritmus segítségével történő felfedezésének összes lépését. Megfigyelhetjük, hogy az azonos távolságban lévő összes csomópontot először feltárjuk, mielőtt a következő szintre lépnénk:

4.2. Végrehajtás

Most már megvalósíthatjuk ezt az algoritmust a Java-ban. Újra felhasználjuk a IRÁNYMUTATÁSOK az előző szakaszban definiált változó.

Először definiálhatunk egy segédprogram-metódust, amely visszalép egy adott csomóponttól a gyökérhez. Ezt fogják használni az útvonal nyomon követésére, miután megtalálta a kijáratot:

private List backtrackPath (Koordináta cur) {Lista útvonala = új ArrayList (); Koordináta iter = cur; while (iter! = null) {path.add (iter); iter = iter.parent; } visszatérési útvonal; }

Most definiáljuk a mag módszerét megoldani. Újra felhasználjuk a DFS megvalósításában használt három blokkot, azaz validáljuk a csomópontot, megjelöljük a meglátogatott csomópontot és bejárjuk a szomszédos csomópontokat.

Csak egy apró módosítást hajtunk végre. Rekurzív áthaladás helyett FIFO adatstruktúrát használunk a szomszédok nyomon követésére és azokon történő iterálásra:

public List megoldás (Maze labirintus) {LinkedList nextToVisit = new LinkedList (); Koordinátor kezdete = labirintus.getEntry (); nextToVisit.add (start); while (! nextToVisit.isEmpty ()) {cur = nextToVisit.remove () koordináta; if (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {folytatás; } if (labirintus.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); folytatni; } if (labirintus.isExit (cur.getX (), cur.getY ())) {return backtrackPath (cur); } for (int [] direction: DIRECTIONS) {Koordináta koordináta = új Koordináta (cur.getX () + irány [0], cur.getY () + irány [1], cur); nextToVisit.add (koordináta); maze.setVisited (cur.getX (), cur.getY (), true); }} return Collections.emptyList (); }

5. Következtetés

Ebben az oktatóanyagban két fő gráf-algoritmust írtunk le: Mélység-első keresés és Szélesség-első keresés egy labirintus megoldására. Kitértünk arra is, hogy a BFS hogyan adja meg a legrövidebb utat a bejárattól a kijáratig.

A további olvasáshoz keressen más módszereket az útvesztő megoldására, például az A * és a Dijkstra algoritmust.

Mint mindig, a teljes kód megtalálható a GitHubon.