Riešiteľ bludísk v Jave

1. Úvod

V tomto článku preskúmame možné spôsoby navigácie v bludisku pomocou jazyka Java.

Bludisko považujte za čiernobiely obraz, kde čierne pixely predstavujú steny a biele pixely predstavujú cestu. Špeciálne sú dva biele pixely, jedným je vstup do bludiska a druhým východ.

Vzhľadom na také bludisko chceme nájsť cestu od vstupu k východu.

2. Modelovanie bludiska

Bludisko budeme považovať za 2D celočíselné pole. Význam číselných hodnôt v poli bude podľa nasledujúcej konvencie:

  • 0 -> Cesta
  • 1 -> Stena
  • 2 -> Vstup do bludiska
  • 3 -> Výjazd z bludiska
  • 4 -> Bunková časť cesty od vstupu k východu

Bludisko vymodelujeme ako graf. Vstup a výstup sú dva špeciálne uzly, medzi ktorými sa má určiť cesta.

Typický graf má dve vlastnosti, uzly a hrany. Okraj určuje prepojiteľnosť grafu a spája jeden uzol s druhým.

Preto budeme predpokladať štyri implicitné hrany z každého uzla, ktoré spoja daný uzol s jeho ľavým, pravým, horným a spodným uzlom.

Definujme podpis metódy:

riešenie verejného zoznamu (bludisko bludisko) {}

Vstupom do metódy je a bludisko, ktorý obsahuje 2D pole s vyššie pomenovanou konvenciou pomenovania.

Reakciou metódy je zoznam uzlov, ktoré tvoria cestu zo vstupného uzla k výstupnému uzlu.

3. Rekurzívny spätný sledovač (DFS)

3.1. Algoritmus

Jeden celkom zrejmý prístup je preskúmať všetky možné cesty, ktoré nakoniec cestu nájdu, ak existujú. Ale takýto prístup bude mať exponenciálnu zložitosť a nebude mať mierku dobre.

Je však možné prispôsobiť vyššie uvedené riešenie hrubou silou spätným sledovaním a označovaním navštívených uzlov, aby ste získali cestu v rozumnom čase. Tento algoritmus je tiež známy ako vyhľadávanie do hĺbky.

Tento algoritmus je možné načrtnúť ako:

  1. Ak sme pri stene alebo už navštívenom uzle, zlyhanie vrátime
  2. Inak, ak sme výstupným uzlom, potom vrátime úspech
  3. V opačnom prípade pridajte uzol do zoznamu ciest a rekurzívne cestujte všetkými štyrmi smermi. Ak sa chyba vráti, odstráňte uzol z cesty a chybu vráťte. Po nájdení východu bude zoznam ciest obsahovať jedinečnú cestu

Použijme tento algoritmus na bludisko zobrazené na obrázku 1 (a), kde S je východiskový bod a E je východ.

Pre každý uzol prechádzame každým smerom v poradí: pravý, spodný, ľavý, horný.

V bode 1 (b) preskúmame cestu a narazíme do steny. Potom sa stiahneme, až kým nenájdeme uzol, ktorý nemá susedov mimo steny, a preskúmame inú cestu, ako je to znázornené na obrázku 1 (c).

Znovu narazíme na stenu a postup opakujeme, aby sme nakoniec našli východ, ako je to znázornené na obrázku 1 (d):

3.2. Implementácia

Pozrime sa teraz na implementáciu Java:

Najskôr musíme definovať štyri smery. Môžeme to definovať z hľadiska súradníc. Tieto súradnice, ak sú pridané k akejkoľvek danej súradnici, vrátia jednu zo susedných súradníc:

private static int [] [] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 

Potrebujeme tiež nástrojovú metódu, ktorá pridá dve súradnice:

private Coordinate getNextCoordinate (int riadok, int col, int i, int j) {návrat novej súradnice (riadok + i, col + j); }

Teraz môžeme definovať podpis metódy vyriešiť.Logika je tu jednoduchá - ak existuje cesta od vstupu k východu, potom cestu vráťte, inak vráťte prázdny zoznam:

verejné riešenie zoznamu (bludisko bludisko) {cesta zoznamu = nový ArrayList (); if (preskúmať (maze, maze.getEntry (). getX (), maze.getEntry (). getY (), cesta)) {spiatočná cesta; } vrátiť Collections.emptyList (); }

Definujme preskúmať metóda uvedená vyššie. Ak existuje cesta, potom vráti hodnotu true so zoznamom súradníc v argumente cesta. Táto metóda má tri hlavné bloky.

Najskôr vyradíme neplatné uzly, t. J. Uzly, ktoré sú mimo bludiska alebo sú súčasťou steny. Potom označíme aktuálny uzol ako navštívený, aby sme nenavštívili stále ten istý uzol.

Nakoniec sa rekurzívne presunieme všetkými smermi, ak sa nenájde východ:

private boolean explorer (Maze maze, int row, int col, List path) {if (! maze.isValidLocation (row, col) || maze.isWall (row, col) || maze.isExplored (row, col)) { návrat nepravdivý; } path.add (nová súradnica (riadok, stĺpec)); maze.setVisited (riadok, stĺpec, pravda); if (maze.isExit (row, col)) {return true; } for (int [] direction: DIRECTIONS) {Coordinate coordinate = getNextCoordinate (row, col, direction [0], direction [1]); if (explorer (maze, coordinate.getX (), coordinate.getY (), path)) {return true; }} cesta.odstranit (cesta.size () - 1); návrat nepravdivý; }

Toto riešenie využíva veľkosť stohu až do veľkosti bludiska.

4. Variant - Najkratšia cesta (BFS)

4.1. Algoritmus

Rekurzívny algoritmus opísaný vyššie nájde cestu, ale nemusí to byť nevyhnutne najkratšia cesta. Na nájdenie najkratšej cesty môžeme použiť iný prístup k prechodu grafu, ktorý sa nazýva vyhľadávanie na šírku.

V systéme DFS bolo najskôr preskúmané jedno dieťa a všetky jeho vnúčatá, potom bolo možné prejsť na ďalšie dieťa. Zatiaľ čo v BFS budeme skúmať všetky bezprostredné deti predtým, ako sa presunieme k vnúčatám. To zabezpečí, že všetky uzly v určitej vzdialenosti od nadradeného uzla budú preskúmané súčasne.

Algoritmus je možné načrtnúť nasledovne:

  1. Pridajte počiatočný uzol do poradia
  2. Aj keď front nie je prázdny, vysuňte uzol, postupujte takto:
    1. Ak dôjdeme k stene alebo je uzol už navštívený, preskočte na ďalšiu iteráciu
    2. Ak je dosiahnutý výstupný uzol, nájdite najkratšiu cestu späť od aktuálneho uzla k počiatočnému uzlu
    3. Inak pridajte do frontu všetkých bezprostredných susedov v štyroch smeroch

Jedna dôležitá vec je, že uzly musia sledovať svojho rodiča, t. J. Odkiaľ boli pridané do poradia. Je dôležité nájsť cestu, keď sa vyskytne výstupný uzol.

Nasledujúca animácia zobrazuje všetky kroky pri skúmaní bludiska pomocou tohto algoritmu. Môžeme pozorovať, že najskôr sa preskúmajú všetky uzly v rovnakej vzdialenosti a až potom sa presunieme na ďalšiu úroveň:

4.2. Implementácia

Poďme teraz implementovať tento algoritmus v Jave. Znovu použijeme SMERY premenná definovaná v predchádzajúcej časti.

Poďme najskôr definovať užitočnú metódu na spätné sledovanie z daného uzla k jeho koreňu. Toto sa použije na sledovanie cesty po nájdení východu:

private List backtrackPath (Coordinate cur) {Cesta zoznamu = new ArrayList (); Súradnica iter = cur; while (iter! = null) {path.add (iter); iter = iter.parent; } spiatočná cesta; }

Poďme si teraz definovať základnú metódu vyriešiť. Znovu použijeme tri bloky použité pri implementácii DFS, t. J. Overíme uzol, označíme navštívený uzol a prechádzame susednými uzlami.

Urobíme len jednu miernu úpravu. Namiesto rekurzívneho prechádzania použijeme dátovú štruktúru FIFO na sledovanie susedov a iteráciu nad nimi:

riešenie verejného zoznamu (bludisko bludisko) {LinkedList nextToVisit = nový LinkedList (); Začiatok súradnice = maze.getEntry (); nextToVisit.add (štart); while (! nextToVisit.isEmpty ()) {Coordinate cur = nextToVisit.remove (); if (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {continue; } if (maze.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); ďalej; } if (maze.isExit (cur.getX (), cur.getY ())) {return backtrackPath (cur); } for (int [] direction: DIRECTIONS) {Coordinate coordinate = new Coordinate (cur.getX () + direction [0], cur.getY () + direction [1], cur); nextToVisit.add (súradnica); maze.setVisited (cur.getX (), cur.getY (), true); }} vratit Collections.emptyList (); }

5. Záver

V tomto tutoriáli sme opísali dva hlavné algoritmy grafov, ktoré slúžili na hľadanie hĺbky a šírky na riešenie bludiska. Dotkli sme sa tiež toho, ako BFS dáva najkratšiu cestu od vchodu k východu.

Pre ďalšie čítanie vyhľadajte ďalšie metódy riešenia bludiska, napríklad algoritmus A * a Dijkstra.

Celý kód nájdete ako vždy na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found