Lab1

Rekursion

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

Introduktion: Tänk dig att du har ett sommarjobb där du med motorbåt hämtar (och levererar) post från en uppsättning öar i en skärgård. Skärgården är stor och du vill minimera körtid och bränsleåtgång. Centralposten är belägen på en given ö och det är din start- och slutdestination. Öarna kan besökas i godtycklig ordning (inga grund eller landtungor i vägen) och du kan åka mellan två öar utmed en rät linje. Problemet är alltså att hitta den kortaste vägen som sammanbinder alla öarna i en sluten slinga.

Detta är ett exempel på handelsresandeproblemet, travelling salesman problem (TSP) och problemet brukar då formuleras med städer i stället för öar och en matematisk formulering brukar göras i termer av grafteori. Så här kan det se ut med fyra öar. Den första bilden visar öarna och de tre graferna visar olika vägar.

Punkterna markerar öar och den röda är start- och slutdestination. De tre graferna visar alla möjliga vägar, förutsatt att det är samma kostnad att åka från a till b som från att åka från b till a (a och b är namn på två öar). Låt oss numrera öarna medurs och låter den röda vara nummer ett. Vägarna ovan svara då mot sekvenserna: 1, 2, 3, 4, 1, nästa är 1, 3, 2, 4, 1 och sista är 1, 2, 4, 3, 1. Vi antar alltså att 1, 2, 3, 4, 1 är likvärdig med 1, 4, 3, 2, 1 etc. Så om vi har n (n > 2) öar finns det (n-1)! / 2 tänkbara vägar. n-1, pga att en ö (den röda) är låst och division med två eftersom vi inte tar hänsyn till vägens orientering. I exemplet ovan är den första vägen den kortaste.

En tänkbar algoritm, för att hitta den kortaste vägen, är att genomsöka alla (n-1)!/2 tänkbara varianterna, men om man har många öar så blir det snabbt för många vägar. Tjugo öar ger ungefär 6e16 tänkbara vägar. I den här labben kommer du att skapa en lite smartare algoritm som gör att vi orkar med kanske 17 öar. Tio öar tar ett ögonblick.

Ett annat sätt att formulera det hela: att undersöka alla tänkbara vägar, i ett exempel med 12 öar, tog på min dator 5457 sekunder, ungefär 1.5 timme. Den algoritm du kommer att implementera tog 3.7 sekunder på samma problem.
Betoningen på lite är avsiktlig, det finns tjocka böcker om TSP, så man kan göra mycket mer. Syftet med denna laboration är i första hand att ge träning på rekursion, TSP kommer i andra hand.

Ett sätt att angripa problemet är att rita upp ett sökträd som representerar alla vägar (även de med omvända orienteringen). Så, vi börjar i roten (överst) och följer en väg genom trädet tills vi träffar på ett löv (nederst). Löven är likadana eftersom vi alltid skall återvända till den första noden.

Antag att vi söker i trädet efter vägar och håller reda på längden av den kortaste väg vi har hittat så långt. När vi söker efter nästa väg kontrollerar vi, för varje ny ö, om en undre begränsning av vägsträckan kommer att överstiga den kortaste vi har hittat. Om så är fallet så kan vi stryka hela den delen av trädet (den del från den aktuella noden och alla döttrar till den aktuella noden). Vi kan alltså stryka den del av trädet som är rotat (har sin rot) i den aktuella noden. Här en bild för ett större antal öar (jag har inte ritat ut alla kanter).

Om vägen 1-5-4-1 (vi skall ju tillbaks till 1) är längre än den hittills kortaste vägen, kan hela delträdet, med rot i nod 4, strykas. Vi behöver t.ex. inte gå ned till nod 9. Eftersom många vägar snabbt blir längre, än den hittills kortaste, kommer stora delar av trädet aldrig att behöva undersökas. Längden av vägen 1-5-4-1 är en undre begränsning av hela vägen som börjar med 1-5-4. Ju större undre begränsning, av den aktuella vägen, som vi kan hitta desto större delar av sökträdet kan avlägsnas. Denna typ av tekniker brukar kallas branch and bound.

Här är en bättre metod, som du skall använda i ditt program, för att räkna ut en undre begränsning. Antag att vi har kommit en bit på vägen: n₁-n₂-n₃-...-n_p, där n₁, n₂, ..., n_p är p stycken nodnummer (nummer på öar) med n₁ = 1. Låt n vara numret på en nod (kan finnas flera), skild från n₁, n₂, ..., n_p, som maximerar a(n_p, n) + a(n, n₁), där a(n_j, n_k) är avståndet mellan öarna med nummer n_j och n_k. En undre begränsning av vägsträckan är då längden av vägen n₁-n₂-n₃-...-n_p-n-n₁. Observera att detta är billigt att räkna ut.

Varför är ovanstående resonemang korrekt?

Så, antag att vi har 10 öar och står i nod 4 (som i bilden ovan), dvs p = 3 och n₁ = 1, n₂ = 5, n₃ = 4. Vi beräknar numret, n, på den ö som maximerar a(4, n) + a(n, 1). Säg att n = 7. En undre begränsning, av längden på den aktuella vägen, är då längden av vägen 1-5-4-7-1. Om denna begränsning är större än lika med längden av den hittills kortaste vägen stryker vi den del av sökträdet som är rotat i tre. Om begränsningen är mindre än längden av den hittills kortaste vägen får vi fortsätta att gå ned i trädet.

När vi börjar söka med ett nytt träd har vi ingen hittills kortaste väg. Ett sätt att snabba upp programmet är att tillhandahålla en hyfsad startgissning av kortaste vägen. Här följer en beskrivning av två varianter, implementera åtminstone en av följande algoritmer.

En glupsk algoritm (greedy algorithm på engelska)
En glupsk algoritm gör det som är bäst (optimalt) i ett enstaka steg (val av nästa ö). Detta behöver dock inte vara det optimala valet sett över alla steg. Ibland lönar det sig att göra ett till synes dåligt lokalt val. En fördel med glupska algoritmer är att de normalt är enkla att implementera. En nackdel är att de kan ge lösningar som är långtifrån optimala.

I vårt problem kan en glupsk algoritm formuleras på följande sätt.
Första noden (ön) är nummer ett. Så n₁ = 1. Nästa nod, n₂, är den som minimerar a(n₁, n₂), det är ju det lokalt bästa valet. n₃ är den nod som minimerar a(n₂, n₃). Man fortsätter på detta sätt tills man har besökt alla öar en gång. Man får sedan sluta vägen så att man återvänder till nod 1.

Denna algoritm kan fungera bra, om öarna ligger på en cirkel till exempel. Kan du komma på ett exempel när metoden fungerar dåligt?

En algoritm baserad på grafisk inmatning
Den andra metoden utnyttjar människans förmåga att hitta en bra väg. Denna förmåga är normalt riktigt bra om antalet öar inte är för stort. Om man plottar upp öarna kan användaren av programmet klicka på öarna i en lämplig ordning och därmed skapa en startgissning. Här lite idéer:

% skapa lite data (ö-positioner)
n = 10;
x = rand(n, 1);
y = rand(n, 1);

% plotta ö-positioner
figure(1)
hold off
plot(x(1), y(1), 'ro') % start-ö
hold on
plot(x(2:n), y(2:n), 'k*') % övriga

% låt användaren klicka
xp = []; yp = [];
for k = 1:n
% läs av musposition
[xp(k), yp(k)] = ginput(1);

% rita större ringar där man har klickat
% så att man får lite feedback och
% inte behöver komma ihåg var man klickat
plot(xp(k), yp(k), 'ro', 'markersize', 10)
end

Ett problem är kvar. Användaren torde inte klicka exakt på en ö, utan denne borde kunna slarva lite och klicka i närheten av en ö. Det gör att man måste para ihop (xp, yp) med (x, y). Denna ihop-parning ger också besöksordningen bland öarna.

Ytterligare en uppsnabbning
För att slippa räkna ut avstånd mellan städer hela tiden och för att förenkla programmeringen, skapar man en avståndsmatris (kostnadsmatris), C säg, där C(j, k) är avståndet mellan öar j och k. Man bildar bara matrisen en gång i programmet.

Användargränssnitt
Implementera en av följande lösningar. Den första är enklast.

Skriv en funktion, tsp, [order, len] = tsp(x, y), som tar två kolonnvektorer x, y som inparametrar. (x(1), y(1)) är koordinaterna för start- och slut-ö. Koordinaterna för övriga öar lagras i resterande element i (x, y). order är ordningsföljden (en heltalsvektor med order(1) = 1) på den optimala ordningen och len är längden på den optimala vägen.
Skriv tsp ovan och förpacka det i GUI, så att man kan klicka ut öarnas positioner (man kan alltså ge (x, y) via ett GUI). Beroende på ambitionsnivå (du får nog läsa lite manual på egen hand) kan man lägga in knappar och annat som behövs. Du har alltså stora friheter att utforma denna lösning, men tsp-funktionen från uppgift 1, måste finnas med.

Nu till uppgiften:

Skriv ett rekursivt Matlabprogram som räknar ut och ritar ut kortaste vägen enligt specifikationerna ovan. Testa åtminstone på följande data och bifoga längden på kortaste vägen och bilder med den kortaste vägen utritad. Se exempelbilden nedan.

Testfall. Indata är (x1, y1), (x2, y2) respektive (x3, y3). Börja med att testa på något enklare!

phi = linspace(0, 2 * pi, 13)'; phi = phi(1:12);
x1 = cos(phi); y1 = sin(phi);

x2 = [2 3 8 1 3 0 4 2 7 5 9 6 5]';
y2 = [3 3 0 2 6 6 9 2 8 6 0 4 4]';

phi = linspace(0, 4 * pi, 13)';
r = (1:13)'; x3 = r .* cos(phi); y3 = r .* sin(phi);

Jag har fått frågor om körtider för dessa tre fall. Med greedy-startgissningarna tar mitt program 0.2s, 12.8s respektive 97.4s.

Tips: Den rekursiva funktionen, som är en del av tsp-rutinen, kan ha (åtminstone) två indatavariabler done och remain, där done innehåller numren på de öar man undersökt i den aktuella vägen och remain innehåller de som är kvar. Vid första anropet är done = 1 och remain = 2:n, om n = antalet öar.
Den rekursiva kan givetvis ha andra parametrar eller så använder man globala variabler.

Så här kan en typisk resultatbild se ut:

Om du inte har någonstans att resa i sommar. Tom hittade denna trevliga länk om TSP-problemet. En kortaste tur genom 24978 orter i Sverige (72,500 km). På sidan står: The total CPU time for the five cutting-plane runs and for the five branch-and-cut runs was approximately 84.8 CPU years.