Hoppa till innehållet

Bredd-först-sökning

Från Wikipedia
Bredd-först-sökning
Ordning i vilken noderna expanderas Redigera Wikidata
Oinformerad sökalgoritm Redigera Wikidata
Under­klass tillsökalgoritm
 • graph traversal Redigera Wikidata
Upp­täc­ka­re eller upp­fin­na­reKonrad Zuse Redigera Wikidata
Upp­täckts­da­tum1945 Redigera Wikidata
Tids­komp­lex­i­tet i värsta fall Redigera Wikidata
Rums­komp­lex­i­tet i värsta fall Redigera Wikidata
Animering Redigera Wikidata
Binärt träd med 9 noder och höjden 4. I exemplet går bredd-först sökning igenom noderna enligt någon av följande ordningar:
• 8, 3, 10, 1, 6, 14, 4, 7, 13
• 8, 10, 3, 14, 6, 1, 13, 7, 4
osv

Bredd-först sökning (bfs) är en strategi för att traversera ett träd [a] där man undersöker alla noder på en viss nivå i trädet innan man går vidare till nästa nivå.

Strategin kan vara värdefull i många sammanhang och anledningen att välja den beror naturligtvis på vilken data som trädet organiserar. I till exempel ett beslutsträd (ett träd som spänner upp tänkbara konsekvenser av en serie beslut, tex drag i ett schackparti eller en serie strategiska affärsbeslut) utforskar man med denna strategi vilka alternativ man har på en viss nivå innan man går vidare för att utforska alternativen på nästa nivå. Med bredd först kan man i beslutsanalys inte garantera att alltid hitta ett per definition framgångsrikt resultat (tex vinst i ett schackparti) med mindre än att man tittar på samtliga noder. Normalt sett gör man nämligen inte det utan använder en värderingsfunktion för att välja det uppskattat bästa alternativet någon nivå ned. Om man med bredd först finner ett framgångsrikt resultat kan man dock garantera att man också hittar det optimala sättet att ta sig dit.

  1. ^ Ett träd är en hierarkisk datastruktur där varje nod kan ha noll eller flera underordnade noder.