F17 bästa förstsökning, girig algoritm
Bästaförstsökning
Labb d3 behandlar problemet att finna kortaste vägen från FAN till GUD. Man har då ett problemträd med FAN som stamfar/urmoder, på nivån därunder barnen MAN, FIN, FAT osv, på nästa nivå fans barnbarn osv. Om man lägger barnen i en kö kommer man att gå igenom problemträdet nivå för nivå, alltså breddenförst. Om man byter kön mot en stack blir sökningen djupetförst. Med en prioritetskö får man bästaförstsökning, dvs det mest lovande barnet prioriteras och får generera barn.
Det här är exempel på en girig algoritm, där man i varje steg väljer den väg som verkar bäst för stunden, utan att reflektera över vad konsekvenserna blir i längden. Ofta ger giriga algoritmer inte den bästa lösningen, men i just det här fallet fungerar det faktiskt! Algoritmen kallas Dijkstra's algoritm (efter den holländske datalogen Edsger W. Dijkstra) och att den fungerar bevisas i fortsättningskursen DD1352 Algoritmer, datastrukturer och komplexitet (Länkar till en externa sida.).
Det finns flera varianter på Dijkstra's algoritm. Nedan en variant för att räkna ut billigaste vägen från en startnod till en slutnod i en graf med kostnader. För att förklara algoritmen börjar jag med de första stegen.
- Sätt alla noders prioritet/kostnad till ∞ (i praktiken något maximalt värde)
- Sätt startnodens prioritet till 0.
- Stoppa in startnoden i en min-prioritetskö.
Startnoden ligger nu först i kön. I fortsättningen kan noder mitt i prioritetskön behöva omprioriteras. Ett sätt att omprioritera är att införa en remove-funktion som tar bort en nod ur en prioritetskö. Det får inte bli ett "hål" utan i princip sker en upp- och nertrappning på ungefär samma sätt som vid isättning och urtagning från en prioritetskö.
Den fortsatta algoritmen för att hitta billigaste vägen blir ungefär:
- Plocka ut en nod p från prioritetskön.
- Undersök noden p:s barn ett och ett
- Räkna ut kostnaden att gå från p till barnet.
- Om kostnaden är billigare än barnets nuvarande prioritet (från början var kostnaden ∞)
- sätt om barnets prioritet till den nya ackumulerade kostnaden (att gå från startnoden via p till barnet)
- sätt föräldrapekaren att peka på p
- Omprioritera barnet genom att
- plocka bort barnet ur prioritetskön
- stoppa in barnet i prioritetskön
- Upprepa från 1. tills prioritetskön är tom (det går att avbryta tidigare när bättre vägar inte finns)
- Skriv ut billigaste vägen genom att följa föräldrapekarna från slutnoden till startnoden.
Exempel 1: Sök billigaste transport från Teknis till Honolulu. All världens resprislistor finns tillgängliga.
Problemträdets objekt innehåller en plats, ett pris och en förälderpekare. Överst i trädet står Teknis med priset noll. Barnen är alla platser man kan komma till med en transport och priset, till exempelT-centralen, 20.00. Man söker en Honoluluobjekt i problemträdet. Med breddenförstsökning får man den resa som har så få transportsteg som möjligt.
Med bästaförstsökning får man den billigaste resan.
Exempel 2: Sök effektivaste processen för att framställa en önskad substans från en given substans. All världens kemiska reaktioner finns tillgängliga med uppgift om utbytet i procent.
Problemträdets objekt innehåller substansnamn och procenttal. Överst i trädet står utgångssubstansen med procenttalet 100. Barnen är alla substanser man kan framställa med en reaktion och utbytet, till exempel C2H5OH, 96%.
Med en max-prioritetskö får man fram den effektivaste process som leder till målet.
Girig algoritm
Exempel: Fyll en skattkista med guldtackor av olika storlekar. Den giriga algoritmen är att börja med de största och fortsätt med de mindre tills skattkistan är full. Det ger inte alltid den bästa lösningen.
En