fan -> man -> mun -> tun -> tur -> hur -> hud -> gud
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 mans barn fan), så kallade dumbarn. Breddenförstsökningsalgoritmen kan sammanfattas så här.
Breddenförstsökning ger alltid den kortaste lösningen. Ofta är det den man är ute efter. Några andra problemexempel är följande.
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 breddenförst-trä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 breddenförst-trä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 med
raise 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
Om man har en abstrakt kö med metoderna put, get 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):
# breddenförst-trä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.put(urmoder)
try:
while not q.isEmpty():
node = q.get()
makechildren(node)
# I makechildren görs "raise Klar(kedja)"
print("Ingen lönsam växling")
except Klar as k:
print("Växla fort:", k)
|
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.
Djupetförst-Trä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. Djupetförst-Trä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 lista,
där varje listelement är ett heltal som representerar damens position
på just den raden. Då betyder
queen[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örst-Trä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.
000000010002000300040005000600070008000900100011...9999Det 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?
Djupetförst-Trä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!
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.
Breddenförst-träd och djupetförst-trä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 sökträd (binärträd)!
