Inlämningsuppgift 1p

Söktekniker

Av

Ulrika Attermo

Maria Björkman

Elisabeth Mirow

Anne Thelander

Tillbaka

Inledning

Den teknik som används för att söka i exempelvis ett frågeträd kan kallas "blind" sökning. Denna grundar sig på en väl strukturerad sökning ner genom trädet tills man finner en lösning eller har avverkat hela sökområdet. Två olika procedurer beskriver detta förlopp, sökning på djupet samt sökning på bredden.

Sökning på djupet

Sökningen börjar i rotnoden, det vill säga den översta noden i ett frågeträd och letar sig därefter systematiskt ner till de underliggande nodnivåerna. På så vis fortlöper sökningen tills en lösning hittas eller tills det avlästa området är genomsökt. Då en död nod (closed path) påträffas letar sig sökmetoden helt enkelt tillbaka samma väg.

Exempel

Den översta noden (initiala) i vårt sökträd kallar vi A, grenarna i nästa nivå (nivå 1) B och C. I nivå 2 betecknas de D, G samt F (vilket är ett måltillstånd). I nivå 3 närmast under D hittar vi E som är en död nod och under G finns H, E samt F varav H och E är döda noder. Vi startar i nod A, i nästa lägre nivå går sökningen via nod B och då vi inte hittar någon lösning fortsätter sökningen ner ytterligare en nivå till exempelvis nod D. Inte heller här hittas någon tillfredställande lösning och då nästa steg ner i trädet är en död nod (E) går sökningen inte vidare utan istället tillbaka uppåt till B i nivå 1. Sökningen börjar om och via nod G nås slutligen en tillfredställande lösning i nod F (som inte ska förväxlas med F i nivå 2) och sökproceduren avslutas (Se bild nedan).

Sökning på bredden

Denna sökningsmetod går ut på att söka horisontellt och vertikalt ner genom trädet. Rotnoden undersöks givetvis först, därefter alla noder som denna genererar och så vidare ner genom trädet. Allmänt kan sägas att alla noder på nivå d i trädet undersöks innan sökningen går vidare till nivå d+1.

Exempel

Följ samma exempel som vid sökning på djupet genom att börja i rotnod A. Därefter går sökningen vidare neråt en nivå till nod B. Nästa nod att genereras blir alltså nod C, som ligger på samma nivå som B. C är inget önskat sluttillstånd men eftersom alla noder på denna nivå sökts igenom fortsätter sökningen ytterligare en nivå ner, med början i nod D. Eftersom inte heller detta är önskat mål, genereras nästa nod på denna nivå som är G. Inte heller detta är önskvärt varför F genereras, här hittas ett sökt måltillstånd och sökningen avbryts (Se bild nedan).