Lab3a

Rekursion

Laborationen ger träning på datastrukturer, rekursion och grafik.

Introduktion: i denna laboration kommer du att skriva en rekursiv funktion som kan hitta vägen genom en labyrint. Enligt Wikipedia är det skillnad på labyrinth och maze och laborationen är inriktad på maze-fallet. Här ett citat från Wikipediasidan för labyrinth:

The term labyrinth is often used interchangeably with maze, but modern scholars of the subject use a stricter definition. For them, a maze is a tour puzzle in the form of a complex branching passage with choices of path and direction; while a single-path (unicursal) labyrinth has only a single Eulerian path to the center. A labyrinth has an unambiguous through-route to the center and back and is not designed to be difficult to navigate.

Läser man Oxford English Dictionary (OEP) verkar det dock vara synonyma begrepp. Enligt OEP är maze besläktad med nordgermanska ord som svenskans masa (dvs gå långsamt, släpa sig fram). I brist (vad jag vet) på en svensk term kommer jag att använda ordet labyrint (fast man kunde kanske tänka sig att skapa ord som, mase, mejs eller mäjs).

I följande exempel har jag konstruerat en 10x10-labyrint (10 rutor i vertikalt och horisontellt), de två labyrinterna till vänster och en 30x30 längst till höger. De blå rutorna är startpunkter och de röda slutpunkter. De gröna rutorna visar vägarna.

I laborationen är vi bara intresserade av labyrinter där det existerar en entydig väg (vi går inte tillbaks i rutor vi redan besökt) mellan två godtyckliga punkter i labyrinten. Labyrinterna i exemplet har denna egenskap. Vi begränsar oss också till kvadratiska labyrinter (lika många rader och kolonner).

Laborationen består av en obligatorisk del, vägfinnaren samt lite grafik. För den som vill göra mer så finns det frivilliga delar i slutet av laborationen.

Vägfinnaren
Givet en labyrint, en startruta och en slutruta så skall vägfinnarprogrammet hitta vägen mellan start och slut. Programmet skall vara rekursivt och i varje korsning (grening) testa alla tänkbara avtagsvägar rekursivt. Tänk på att inte gå tillbaks i redan testade vägar. Betrakta t.ex. andra labyrinten i exemplet. När vi står i den blå startrutan kan vi testa tre olika vägar. Man kan gå åt norr, åt väster och åt söder. Om man går söderut finns bara en väg (österut) att testa, eftersom vi inte skall gå tillbaks därifrån vi kom etc. När programmet har nått målet, den röda rutan, skall det rita ut (den gröna) vägen. Eftersom det bara finns en väg mellan start och slut kan programmet avsluta sökande så fort som det har hittat vägen.

Datastruktur
När man bestämmer en datastruktur är det viktigt att tänka på vad den skall användas till, att den ger stöd för de operationer man vill utföra. Om man t.ex. bara vill kunna rita upp labyrinten vore det bekvämt att beskriva labyrintens väggar som en uppsättning polygontåg. Detta vore dock en mycket opraktisk datastruktur för vägfinnaren. Man vill nog också att datastrukturen inte skall kräva för mycket minne, det är dock inte en så viktig fråga i denna laboration, eftersom vi inte kommer att ha enormt stora labyrinter.

I min lösning av laborationen använder jag följande datastruktur. Labyrinten beskrivs av fyra logiska nxn-matriser, N, S, E, W (för de fyra väderstrecken). Om N(row, col) är sann så finns det en väg norrut från rutan med koordinaterna (row, col) och om N(row, col) är falskt finns det inte en väg, utan en vägg. Analogt för de andra matriserna. Rutan längst upp till vänster har (row, col) = (1, 1). Så, för den blå rutan ((row, col) = (6, 3)) i andra labyrinten ovan gäller att N(6, 3) = true, S(6, 3) = true, E(6, 3) = false och W(6, 3) = true. Denna datastruktur är praktisk för vägfinnaren, rätt så praktisk för grafiken och datastrukturen kräver inte så mycket minne eftersom logiska variabler lagras med en byte (inte åtta som flyttalen). Det är inte den mest kompakta datastrukturen, en horisontell vägg beskrivs ju båda av N och S-matriserna och en vertikal vägg av E och W (så det skulle räcka med t.ex. N och E och vetskapen att man har en vägg runt labyrinten, men det är lite mindre bekvämt).

Här följer ett litet exempel där n = 4:

North 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1 South 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 East 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 0 West 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1

Om man tycker att det är klumpigt med fyra matriser, kan man förpacka matriserna i t.ex. en post:

Maze = struct('N', N, 'S', S, 'E', E, 'W', W);

Om du väljer att använda min rutin, construct_maze, för att skapa labyrinter, gör så här.

Öppna ett terminalfönster och cd till den katalog där du vill lagra funktionen.
Under Linux: Ge kommandot cp /chalmers/groups/thomas_math/MATL/VER/construct_maze.* .(notera sista punkten som står för aktuella katalog). VER är namnet på den Matlab-version du använder (kan vara R2008b eller R2009b). Ge kommandot version i Matlab för att se vilken version du har. Det är viktigt att du kör rätt version.
2011-03-01: Cornelia har "kompilerat" en version av construct_maze för Matlab 2010 (som jag inte har tillgång till). Du hittar koden i katalogen /chalmers/groups/thomas_math/MATL/R2010 .

Du kommer att kopiera två filer, construct_maze.m, som innehåller kommentarer (skriv help construct_maze) och construct_maze.p som innehåller koden i en slags kompilerad form så kallad p-code (du kan alltså inte läsa koden, vilket är avsiktligt).

Nu till uppgiften:

Skriv ett Matlabprogram, maze(n), som:

Skapar en nxn-labyrint.
Ritar upp labyrinten.
Läser av, via ginput, startpunkt och slutpunkt.
Tar fram vägen med vägfinnar-algoritmen.
Ritar ut vägen.

Mera ledning:

För markering av startpunkt och slutpunkt: help ginput

Om man har stort n, så kan antalet rekursionsnivåer överskrida Matlabs standardvärde (som är 500) och du kan få ett felmeddelande i stil med:

??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Man kan alltså ändra antalet nivåer med kommandot set(0, 'RecursionLimit', limit) där limit är det nya antalet. Om du har väldigt stora labyrinter och stort värde på limit kan du få problem med att primärminnet tar slut och då kan datorn gå väldigt långsamt (låsa sig).

För att rita en vägg kan man använda skriva något i stil med (x_vec och y_vec får du fixa):

plot(x_vec, y_vec, 'Color', 'k', 'Linewidth', 3) ellerline(x_vec, y_vec, 'Color', 'k', 'Linewidth', 3) som är snabbare än plot-alternativet.

För de prickade delarna kan man använda:

line(x_vec, y_vec, 'Color', 'k', 'Linestyle', ':', 'Linewidth', 1) (eller motsvarande plot)

För att fylla en ruta med färg kan man använda fill (som vi tar upp i kursen) eller patch, som är lite snabbare, t.ex.

patch(x_vec, y_vec, 'r', 'Edgecolor', 'none') % för en röd kvadrat utan kantlinje

axis equal, axis tight, axis off är användbara för hanteringen av axlarna.

Avlusningstips. Det är svårt att avlusa ett program om du hela tiden skapar nya labyrinter, så skapa en liten testlabyrint som du testar ditt program på (tills det fungerar). Du kan ju spara N, S, E, W på en fil (help save, help load)
så har du kvar testdata till nästa labbtillfälle.

Några förslag på frivilliga extrauppgifter:

När du har löst den obligatoriska uppgiften ovan och om du känner att du vill ha en större utmaning kan du pröva att bygga ut din lösning enligt följande förslag:

Skriv en egen construct_maze (jag baserade min på DFS-rutinen som du hittar hos MazeWorks).

Visa dynamiken i rutinen, dvs rita ut hur programmet undersöker nya vägar och backar från misslyckade försök. Du hittar en exempelrutin under /chalmers/groups/thomas_math/MATL/VER/extra_maze.p (under Linux). Rutinen anropas med extra_maze(n, delay), där delay (positivt flyttal) är en fördröjning så att man hinner se grafiken. Testa t.ex. extra_maze(20, 0.02) . För att få bra fart på rutinen måste man nog använda handtagsgrafik.

Lägg till ett GUI. Man vill kanske kunna bestämma storleken på labyrinten via en meny. Man vill kanske kunna testa flera start/slutpunkter för samma labyrint och inte skapa en ny varje gång. Man vill kanske kunna ändra delay-värdet via en slider. Man vill kanske försöka lösa problemet själv (genom att klicka fram en väg med musen).

Den belöning du får om du gör en extrauppgift är att du lär dig mer och får känna tillfredsställelsen av att har löst svårare problem. Du får alltså inte bonuspoäng på tentan eller liknande.

Här är rekursionslabben från 2008 i fall någon är intresserad. Jag vet att problemet, som man löser i labben, kommer att nämnas under Java-kursen i period två.