streamalism.org

1. Introduktion

I denne artikel undersøger vi mulige måder at navigere i en labyrint ved hjælp af Java.

Overvej labyrinten for at være et sort / hvidt billede med sorte pixels, der repræsenterer vægge, og hvide pixels, der repræsenterer en sti. To hvide pixels er specielle, den ene er indgangen til labyrinten og en anden udgang.

I betragtning af en sådan labyrint ønsker vi at finde en sti fra indgang til udgang.

2. Modellering af labyrinten

Vi betragter labyrinten som et 2D-heltal. Betydningen af ​​numeriske værdier i arrayet vil være som følger af følgende konvention:

• 0 -> Vej
• 1 -> Væg
• 2 -> Labyrintindgang
• 3 -> Maze exit
• 4 -> Celle del af stien fra indgang til afslutning

Vi modellerer labyrinten som en graf. Indgang og udgang er de to specielle knudepunkter, mellem hvilke stien skal bestemmes.

En typisk graf har to egenskaber, noder og kanter. En kant bestemmer grafens tilslutningsmuligheder og forbinder en node til en anden.

Derfor antager vi fire implicitte kanter fra hver knude, der forbinder den givne knude til dens venstre, højre, øverste og nederste knude.

Lad os definere metodesignaturen:

offentlig liste løse (labyrint labyrint) {}

Input til metoden er en labyrint, som indeholder 2D-array med navngivningskonvention defineret ovenfor.

Metodens respons er en liste over noder, der danner en sti fra indgangsnoden til udgangsnoden.

3. Rekursiv Backtracker (DFS)

3.1. Algoritme

En ret åbenlys tilgang er at udforske alle mulige stier, som i sidste ende vil finde en sti, hvis den findes. Men en sådan tilgang vil have eksponentiel kompleksitet og skaleres ikke godt.

Det er dog muligt at tilpasse brute force-løsningen, der er nævnt ovenfor, ved backtracking og markering af besøgte noder for at opnå en sti på en rimelig tid. Denne algoritme er også kendt som Dybde-første søgning.

Denne algoritme kan skitseres som:

1. Hvis vi er ved væggen eller en allerede besøgt node, skal du returnere fejl
2. Ellers hvis vi er udgangsknudepunktet, så returner succes
3. Ellers tilføj knudepunktet i kurslisten og rejs rekursivt i alle fire retninger. Hvis fejl returneres, skal du fjerne noden fra stien og returnere fejl. Sti-listen indeholder en unik sti, når exit findes

Lad os anvende denne algoritme på labyrinten vist i figur 1 (a), hvor S er startpunktet, og E er udgangen.

For hver node krydser vi hver retning i rækkefølge: højre, bund, venstre, top.

I 1 (b) udforsker vi en sti og rammer væggen. Derefter går vi tilbage, indtil der findes en knude, der har naboer, der ikke er væg, og udforsker en anden sti som vist i 1 (c).

Vi rammer igen væggen og gentager processen for endelig at finde udgangen, som vist i 1 (d):

3.2. Implementering

Lad os nu se Java-implementeringen:

Først skal vi definere de fire retninger. Vi kan definere dette i form af koordinater. Disse koordinater, når de føjes til en given koordinat, returnerer et af de nærliggende koordinater:

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

Vi har også brug for en hjælpemetode, der tilføjer to koordinater:

privat Koordinering getNextCoordinate (int række, int kol, int i, int j) {returner ny Koordinering (række + i, kol + j); }

Vi kan nu definere metodesignaturen løse.Logikken her er enkel - hvis der er en sti fra indgang til afgang, skal du returnere stien, ellers skal du returnere en tom liste:

offentlig liste løse (labyrint labyrint) {Liste sti = ny ArrayList (); hvis (udforske (labyrint, labyrint.getEntry (). getX (), labyrint.getEntry (). getY (), sti)) {retursti; } returner Collections.emptyList (); }

Lad os definere udforske ovennævnte metode. Hvis der er en sti, skal du returnere sand med listen over koordinater i argumentet sti. Denne metode har tre hovedblokke.

For det første kasserer vi ugyldige noder, dvs. de noder, der er uden for labyrinten eller er en del af væggen. Derefter markerer vi den aktuelle node som besøgt, så vi ikke besøger den samme node igen og igen.

Endelig bevæger vi os rekursivt i alle retninger, hvis udgangen ikke findes:

privat boolsk udforskning (labyrint labyrint, int række, int col, liste sti) {if (! maze.isValidLocation (række, col) || maze.isWall (række, col) || maze.isExplored (række, col)) { returner falsk; } path.add (ny Koordinering (række, kolonne)); maze.setVisited (række, kol, sandt); hvis (maze.isExit (række, kol)) {returner sand; } for (int [] retning: DIRECTIONS) {Koordinatkoordinat = getNextKoordinat (række, kol, retning [0], retning [1]); hvis (udforske (labyrint, koordinat.getX (), koordinat.getY (), sti)) {returner sand; }} path.remove (path.size () - 1); returner falsk; }

Denne løsning bruger stakstørrelse op til labyrintens størrelse.

4. Variant - korteste sti (BFS)

4.1. Algoritme

Den rekursive algoritme, der er beskrevet ovenfor, finder stien, men det er ikke nødvendigvis den korteste sti. For at finde den korteste sti kan vi bruge en anden graf-traversal-tilgang kendt som bredde-første søgning.

I DFS blev et barn og alle dets børnebørn først udforsket, inden de gik videre til et andet barn. Mens vi i BFS udforsker alle de umiddelbare børn, inden vi går videre til børnebørnene. Dette vil sikre, at alle noder i en bestemt afstand fra forældrenoden udforskes på samme tid.

Algoritmen kan skitseres som følger:

1. Tilføj startknudepunktet i kø
2. Mens køen ikke er tom, skal du pope en knude og gøre følgende:
   1. Hvis vi når væggen, eller noden allerede er besøgt, skal du springe til næste iteration
   2. Hvis exitknudepunktet er nået, skal du gå tilbage fra den aktuelle knude til startknudepunktet for at finde den korteste sti
   3. Ellers tilføj alle umiddelbare naboer i de fire retninger i kø

En vigtig ting her er, at noderne skal holde styr på deres forældre, dvs. hvorfra de blev føjet til køen. Dette er vigtigt at finde stien, når udgangsnoden er stødt.

Følgende animation viser alle trin, når man udforsker en labyrint ved hjælp af denne algoritme. Vi kan se, at alle knudepunkter i samme afstand udforskes først, inden vi går videre til det næste niveau:

4.2. Implementering

Lad os nu implementere denne algoritme i Java. Vi vil genbruge ANVISNINGER variabel defineret i forrige afsnit.

Lad os først definere en hjælpemetode til at spore fra en given node til dens rod. Dette vil blive brugt til at spore stien, når udgangen er fundet:

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

Lad os nu definere kernemetoden løse. Vi genbruger de tre blokke, der bruges i DFS-implementering, dvs. validerer node, markerer besøgte node og krydser tilstødende noder.

Vi foretager bare en lille ændring. I stedet for rekursiv traversal bruger vi en FIFO-datastruktur til at spore naboer og gentage dem:

offentlig liste løse (labyrint labyrint) {LinkedList nextToVisit = ny LinkedList (); Koordinat start = labyrint.getEntry (); nextToVisit.add (start); while (! nextToVisit.isEmpty ()) {Koordinat cur = nextToVisit.remove (); hvis (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {fortsæt; } hvis (maze.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); Blive ved; } hvis (labyrint.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 (koordinat); labyrint.setVisited (cur.getX (), cur.getY (), sandt); }} returner Collections.emptyList (); }

5. Konklusion

I denne vejledning beskrev vi to store grafalgoritmer Dybde-første søgning og Bredde-første søgning for at løse en labyrint. Vi berørte også, hvordan BFS giver den korteste vej fra indgangen til afgangen.

For yderligere læsning, se andre metoder til at løse en labyrint, som A * og Dijkstra algoritme.

Som altid kan den fulde kode findes på GitHub.