Föreläsning 5 Grafer och grafalgoritmer
- Grafer
- Problemträd
- Breddenförstsökning
- Djupetförstsökning
Grafer
- En allmän graf består av en samling hörn (vertices) med kanter (edges) emellan.
- Grafen är riktad om kanterna är riktade (pilar).
- Antalet kanter från ett hörn är hörnets grad (degree).
- En stig (path) är en väg från ett hörn till ett annat, dvs en följd av intilliggande kanter.
- En cykel är en stig där man startar och slutar i ett och samma hörn.
- Om grafen inte har några cykler är den acyklisk.
- I en viktad graf har kanterna vikter.
Abstrakt datatyp för grafer
Följande metoder skulle en graf kunna ha:
addVertex(node) Lägger till hörnet node till grafen.
addEdge(node1, node2) Drar en kant mellan hörnen node1 och node2.
v = getVertex(key) Hittar det hörn som har nyckeln key
vlist = getVertices() Returnerar en lista med alla hörn.
En graf kan implementeras med en grannmatris (adjacency matrix) eller grannlista (adjacency list).
En grannmatris har ett element för varje möjlig kant mellan två hörn. Elementet kan vara True/False (för en oviktad graf) eller ha ett värde som anger kantens vikt (för en viktad graf).
A | B | C | D | |
A | 5 | 1 | ||
B | 5 | |||
C | 2 | |||
D | 1 | 2 |
En gles grannmatris ger ineffektiv lagring, så för grafer med relativt få kanter är det bättre att använda en grannlista. Grannlistan har ett element för varje hörn, och i det lagras en lista med kanterna.
A | [B, 5], [D, 1] |
B | [A, 5] |
C | [D, 2] |
D | [A, 1], [C, 2] |
Exempel på grafproblem
Ett klassiskt problem är handelsresandeproblemet (TSP - travelling salesman problem). En handelsresande vill hitta den kortaste/billigaste rutten mellan flera städer. Hen vill endast besöka varje stad en gång och sluta rutten där hen började. Varje stad är ett hörn i grafen och kanterna är vägen mellan städerna. Ett sätt att lösa problemet är med en brute-force algoritm vilket innebär att man provar alla möjliga vägar men antal vägar att testa ökar med fakulteten på antalet städer. I fortsättningskurser inom datalogi får man lära sig visa om ett datalogiskt problem går att lösa i polynom tid eller inte.
Problemträd
En mycket stor klass av praktiska problem kan beskrivas med problemträd och lösas med trädgenomgång, bredden först eller djupet först.
Laboration 4 går ut på att finna kortaste vägen från söt till sur genom att byta en bokstav i taget och bara använda ord i ordlistan, till exempel så här:
söt -> söm -> döm -> dum -> dur -> sur
Problemträd uppkommer ständigt i praktiken. Man brukar kalla startobjektet för urmoder eller stamfar och objekten under det för barn.
Breddenförstsökning
Problemträdets stamfar söt har barnen göt, löt, nöt, röt osv och barnbarnen get, gök, göl, lat, lön osv. Enligt kedjan ovan är sur barnbarnbarnbarnbarn till söt, men sur finns säkert redan tidigare i problemträdet. För att finna den första förekomsten gör man en breddenförstsökning enligt följande.
Lägg stamfadern som första och enda objekt i en kö. Gör sedan följande om och om igen: Plocka ut den första ur kön, skapa alla barn till denne och lägg in dom sist i kön. Första förekomsten av det sökta ordet ger kortaste lösningen.
Man kan spara in både tid och utrymme om man undviker att skapa barn som är kopior av tidigare släktingar (t ex nöts barn söt), så kallade dumbarn. Breddenförstsökningsalgoritmen kan sammanfattas så här.
- Lägg stamfadern i kön.
- Ta ut det första objektet ur kön.
- Skapa alla dess barn och lägg in dom i kön.
- Om någon av barnen är lösningen så är vi klara. Annars - upprepa från punkt 2 tills kön blir tom.
- När lösningen hittas, följ förälderpekarna och skriv ut kedjan.
Om man bara lägger själva orden i kön finns det ingen möjlighet att i efterhand tala om vägen från söt till sur. Därför bör man för varje nytt ord skapa en liten nod som innehåller ordet och en referens till föräldern och det man lagrar i kön är denna nod.
Breddenförstsökning ger alltid den kortaste lösningen. Ofta är det den man är ute efter. Några andra problemexempel är följande.
Flygresa från Stockholm till Windhoek
Stockholm är urmoder, destinationer med direktflyg från Stockholm blir söner och så vidare. Dumbarn är destinationer man redan "passerat". Breddenförstsökning ger en resa med så få mellanlandningar som möjligt.
Lönsam valutaväxling
Finns det någon lönsam växlingskedja av typen 1.00 SEK -> 0.11 EURO -> 0.13 USD -> ... -> 1.02 SEK ? Vi vill ha en algoritm som kan besvara den frågan.
Vi antar att alla växlingskurser är kända, t ex 1.00 SEK -> 0.14 USD och 1.00 USD -> 7.05 SEK. En valutanod är ett belopp i en viss valuta. Vi utgår från valutanoden 1.00 SEK och låter den vara urmoder i ett problemträd. Urmoderns barn är alla valutanoder som kan åstadkommas med en växling, till exempel 0.14 USD och 16.5 JPY. Barnet 0.14 USD har i sin tur barn, däribland 0.987 SEK. Just den är ett så kallat dumbarn och kan lugnt glömmas bort, eftersom den är sämre än en tidigare valutanod.
Om man går igenom problemträdet nivå för nivå, dvs generation efter generation, kanske man till sist stöter på noden 1.05 SEK. Därmed har man funnit en lönsam växlingskedja och det är bara att sätta igång och växla så fort som möjligt innan kurserna ändras. För att avbryta trädgenomgången och hals över huvud återvända till huvudprogrammet kan man generera ett särfall medraise Klar(meddelande) och se till att huvudprogrammet har
try: - - - # Om särfallet uppstår här... except Klar: - - - # ...teleporteras man hit
Allra enklaste sättet att definiera Klar är:
class Klar(Exception): pass
Att använda ett särfall (exception) för programmeringslogik är kontroversiellt då särfall är tänkt att användas för felhantering. I andra språk kan man använda en GOTO-sats för att bryta en rekursionskedja men GOTO är också kontroversiellt eftersom det historiskt förknippas med dålig kod.
Om man har en abstrakt kö med metoderna enqueue, dequeue och isEmpty kan breddenförstsökningen programmeras ungefär så här.
class Node(object): def __init__(self, amount=1.00, currency=1, parent=None): # problemträdsobjekt self.amount = amount # belopp self.currency = currency # valuta, SEK, USD,... self.parent = None # förälderpekare def makechildren(node): # Skapar barn och lägger dom i kön #Inläsning av växlingskurserna q = Queue() urmoder = Node() q.enqueue(urmoder) try: while not q.isEmpty(): node = q.dequeue() makechildren(node) # I makechildren görs "raise Klar(kedja)" print("Ingen lönsam växling") except Klar as k: print("Växla fort:", k) |
Metoden makechildren skapar alla barn och lägger sist i kön. Om man vill bli av med dumbarnen kan man ha en global lista best med hittills högsta belopp av varje valuta.
Problemträdet vi får när vi söker vägen från söt till sur är exempel på en riktad (från startordet till barnen), acyklisk (dumträdet hjälper oss att slippa repriser) graf. Breddenförstsökning och djupetförstsökning är två olika sätt att gå igenom alla hörn.
I breddenförst går vi först igenom alla hörn som ligger en kant från starthörnet, sen alla hörn som ligger två kanter bort osv. Om det finns flera lösningar till problemet stöter vi på den närmaste först (men om vi inte bryter där går vi igenom alla hörnen).
Med djupetförst följer vi istället en stig så långt det går via första kanten från starthörnet. När det tar stopp backar vi ett steg (flera vid behov) tills det går att fortsätta framåt igen.
Problemträd är ett sätt att tänka på problem för att kunna lösa dom med grafalgoritmer. Blanda inte ihop problemträd med den abstrakta datastrukturen binärträd!
Djupetförstsökning
Djupetförstsökning skiljer sig från breddenförstsökning i två avseenden:
- Den första lösning man hittar är inte nödvändigtvis den kortaste.
- Metoden fungerar inte om problemträdet har oändligt djup.
Åttadamersproblemet
Man ska placera åtta damer på ett schackbräde så att ingen dam står på samma vågräta, lodräta eller diagonala linje som någon annan.
Problemträdets urmoder är ett tomt bräde. Dom åtta barnen har en dam placerad på översta raden, barnbarnen ytterligare en dam på näst översta raden etc. Problemträdet har djup åtta (fler damer kan vi inte placera ut).
Den första idén man får är ju att representera schackbrädet med en matris. Men lösningen blir enklare om man använder en vektor, där varje vektorelement är ett heltal som representerar damens position på just den raden. Då betyderqueen[0]=5 att damen på rad noll står i position 5.
Rekursiv tanke:
Att lösa problemet färdigt när det redan står damer på rad 0..row-1 är detsamma som...
...att för varje tillåten damplacering på rad row lösa problemet färdigt...
... men om row=8 har man hittat en lösning.
def completePartialSolution(row): # Fullborda partiell lösning som har damer på rad 0..row-1 if row == n: printSolution() else: for col in range(n): if posOK(row,col): queen[row] = col completePartialSolution(row+1) def posOK(row, col): # Kolla om damen på rad row kan slås av damerna ovanför for i in range(row): if queen[i] == col: return False #rakt ovanför if queen[i]-col == row-i: return False #snett ovanför (NV) if col-queen[i] == row-i: return False #snett ovanför (NO) return True def printSolution(): # Skriver ut den lösning som just nu är lagrad i "queen" for r in range(n): for col in range(n): if queen[r] == col: print("D", end = "") else: print("*", end = "") print() print("===============") n = 8 queen=[None]*n completePartialSolution(0) |
Djupetförstsökning kan också programmeras som breddenförstsökningen, med den lilla skillnaden att kön byts mot en stack.
Här följer några fler exempel på problem som kan lösas med djupetförstsökning.
Hitta ut ur labyrint
En välkänd praktisk metod att utforska en labyrint, uppfunnen av den förhistoriska datalogen Ariadne, är att ha ett garnnystan med ena änden fastknuten i startpunkten. Man går så långt man kan, markerar med krita var man varit, går bara outforskade vägar framåt och backar en bit längs snöret när man kör fast. Snöret kan representeras av en stack med dom positioner som snöret för tillfället ringlar igenom.
Problemträdet har startpositionen som urförälder, alla positioner på ett stegs avstånd som barn och så vidare. En position som man varit på förut är ett dumbarn.
Luddes portkodssekvens
En teknolog som glömt sin fyrsiffriga portkod tryckte sej igenom alla tiotusen kombinationer så här.
000000010002000300040005000600070008000900100011...9999
Det kräver fyrtiotusen tryckningar. Men man kan klara sej med bara tiotusentre tryckningar om man har en supersmart sekvens där varje fyrsiffrigt tal förekommer någonstans. Hur ser sekvensen ut?
Problemträdets urförälder 0000 har tio barn 00000, 00001,..., 00009, varav det första är ett dumbarn. Breddenförst eller djupetförst? Vi vet att trädet har djupet tiotusen och att alla lösningar är lika långa, därför går djupetförst bra. Men breddenförst skulle kräva biljoner noder!