streamalism.org

1. Introduksjon

I denne artikkelen vil vi utforske mulige måter å navigere i en labyrint ved hjelp av Java.

Betrakt labyrinten som et svart-hvitt bilde, med svarte piksler som representerer vegger, og hvite piksler som representerer en sti. To hvite piksler er spesielle, en er inngangen til labyrinten og en annen utgang.

Gitt en slik labyrint, vil vi finne en sti fra inngang til utgangen.

2. Modellering av labyrinten

Vi vil betrakte labyrinten som et 2D-heltall. Betydningen av numeriske verdier i matrisen vil være i henhold til følgende konvensjon:

• 0 -> Veien
• 1 -> Vegg
• 2 -> Labyrintoppføring
• 3 -> Maze exit
• 4 -> Celle del av banen fra inngang til avslutning

Vi skal modellere labyrinten som en graf. Inngang og utgang er de to spesielle noder, mellom hvilken bane skal bestemmes.

En typisk graf har to egenskaper, noder og kanter. En kant bestemmer tilkoblingen til grafen og knytter en node til en annen.

Derfor antar vi fire implisitte kanter fra hver node, som knytter den gitte noden til sin venstre, høyre, øverste og nederste node.

La oss definere metodesignaturen:

offentlig liste løse (labyrint labyrint) {}

Inngangen til metoden er en labyrint, som inneholder 2D-matrisen, med navnekonvensjonen definert ovenfor.

Responsen til metoden er en liste over noder, som danner en bane fra inngangsnoden til utgangsnoden.

3. Rekursiv Backtracker (DFS)

3.1. Algoritme

En ganske åpenbar tilnærming er å utforske alle mulige stier, som til slutt vil finne en sti hvis den eksisterer. Men en slik tilnærming vil ha eksponentiell kompleksitet og vil ikke skaleres godt.

Det er imidlertid mulig å tilpasse brute force-løsningen nevnt ovenfor, ved å spore tilbake og merke besøkte noder, for å oppnå en sti på en rimelig tid. Denne algoritmen er også kjent som dybde-første søk.

Denne algoritmen kan skisseres som:

1. Hvis vi er ved veggen eller en allerede besøkt node, kan du returnere feil
2. Ellers hvis vi er utgangsnoden, så returner suksess
3. Ellers, legg til noden i banelisten og reis rekursivt i alle fire retninger. Hvis feil returneres, fjern noden fra banen og returner feilen. Sti-listen vil inneholde en unik bane når exit er funnet

La oss bruke denne algoritmen på labyrinten vist i figur 1 (a), der S er startpunktet, og E er utgangen.

For hver node krysser vi hver retning i rekkefølge: høyre, bunn, venstre, topp.

I 1 (b) utforsker vi en sti og treffer veggen. Deretter går vi tilbake til en node er funnet som har naboer som ikke er vegg, og utforsker en annen vei som vist i 1 (c).

Vi treffer igjen veggen og gjentar prosessen for å endelig finne utgangen, som vist i 1 (d):

3.2. Gjennomføring

La oss nå se Java-implementeringen:

Først må vi definere de fire retningene. Vi kan definere dette i form av koordinater. Disse koordinatene, når de blir lagt til en gitt koordinat, vil returnere en av nabokoordinatene:

privat statisk int [] [] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 

Vi trenger også en verktøymetode som vil legge til to koordinater:

private Koordinere getNextCoordinate (int rad, int col, int i, int j) {return new Coordinate (rad + i, col + j); }

Vi kan nå definere metodesignaturen løse.Logikken her er enkel - hvis det er en sti fra innreise til utgang, så returner stien, ellers, returner en tom liste:

public List løse (Labyrint labyrint) {List path = new ArrayList (); hvis (utforske (labyrint, labyrint.getEntry (). getX (), labyrint.getEntry (). getY (), sti)) {returvei; } returner Collections.emptyList (); }

La oss definere utforske metode referert til ovenfor. Hvis det er en sti, kan du returnere sant, med listen over koordinater i argumentet sti. Denne metoden har tre hovedblokker.

Først kaster vi ugyldige noder, dvs. nodene som er utenfor labyrinten eller er en del av veggen. Etter det markerer vi den nåværende noden som besøkt, slik at vi ikke besøker den samme noden igjen og igjen.

Til slutt beveger vi oss rekursivt i alle retninger hvis utgangen ikke blir funnet:

privat boolsk utforsking (Maze labyrint, int rad, int col, List path) {if (! maze.isValidLocation (row, col) || maze.isWall (row, col) || maze.isExplored (row, col)) { returner falsk; } path.add (ny Koordinering (rad, kolonne)); maze.setVisited (rad, kol, sann); hvis (labyrint.isExit (rad, kol)) {returner sann; } for (int [] retning: DIRECTIONS) {Koordinatkoordinat = getNextKoordinat (rad, kol, retning [0], retning [1]); hvis (utforske (labyrint, coordinate.getX (), coordinate.getY (), sti)) {return true; }} path.remove (path.size () - 1); returner falsk; }

Denne løsningen bruker stabelstørrelse opp til størrelsen på labyrinten.

4. Variant - korteste bane (BFS)

4.1. Algoritme

Rekursiv algoritme beskrevet ovenfor finner banen, men det er ikke nødvendigvis den korteste banen. For å finne den korteste veien, kan vi bruke en annen graf traversal tilnærming kjent som bredde-første søk.

I DFS ble ett barn og alle barnebarna utforsket først, før de gikk videre til et annet barn. Mens i BFS, vil vi utforske alle nærmeste barn før vi går videre til barnebarna. Dette vil sikre at alle noder i en bestemt avstand fra foreldrenoden blir utforsket samtidig.

Algoritmen kan skisseres som følger:

1. Legg til startnoden i køen
2. Mens køen ikke er tom, trykk på en node, gjør følgende:
   1. Hvis vi når veggen eller noden allerede er besøkt, kan du hoppe til neste iterasjon
   2. Hvis utgangsnoden er nådd, kan du gå tilbake fra nåværende node til startnoden for å finne den korteste banen
   3. Ellers, legg til alle nærmeste naboer i de fire retningene i køen

En viktig ting her er at nodene må holde rede på foreldrene sine, dvs. hvor de ble lagt til køen. Dette er viktig for å finne stien når avkjøringsnoden oppstår.

Følgende animasjon viser alle trinnene når du utforsker en labyrint ved hjelp av denne algoritmen. Vi kan observere at alle nodene på samme avstand utforskes først før vi går videre til neste nivå:

4.2. Gjennomføring

La oss nå implementere denne algoritmen i Java. Vi vil gjenbruke ANVISNINGER variabel definert i forrige avsnitt.

La oss først definere en verktøymetode for å spore fra en gitt node til roten. Dette vil bli brukt til å spore stien når avkjørsel er funnet:

private List backtrackPath (Coordinate cur) {List path = new ArrayList (); Koordinere iter = cur; while (iter! = null) {path.add (iter); iter = iter.parent; } returvei; }

La oss nå definere kjernemetoden løse. Vi vil gjenbruke de tre blokkene som brukes i DFS-implementering, dvs. validere node, merke besøkt node og krysse naboene.

Vi vil bare gjøre en liten modifikasjon. I stedet for rekursiv traversal bruker vi en FIFO-datastruktur for å spore naboer og gjenta dem:

offentlig liste løse (labyrint labyrint) {LinkedList nextToVisit = ny LinkedList (); Koordinatstart = labyrint.getEntry (); nextToVisit.add (start); while (! nextToVisit.isEmpty ()) {Coordinate cur = nextToVisit.remove (); hvis (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {fortsett; } hvis (maze.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); Fortsette; } hvis (maze.isExit (cur.getX (), cur.getY ())) {return backtrackPath (cur); } for (int [] retning: DIRECTIONS) {Koordinatkoordinat = ny Koordinat (cur.getX () + retning [0], cur.getY () + retning [1], cur); nextToVisit.add (koordinere); labyrint.setVisited (cur.getX (), cur.getY (), sant); }} returner Collections.emptyList (); }

5. Konklusjon

I denne opplæringen beskrev vi to store grafalgoritmer Dybde-første søk og Bredde-første søk for å løse en labyrint. Vi berørte også hvordan BFS gir den korteste veien fra inngangen til utgangen.

For videre lesing, slå opp andre metoder for å løse en labyrint, som A * og Dijkstra-algoritme.

Som alltid kan hele koden bli funnet på GitHub.