Labb 4: Grafer, breddenförstsökning del 1
- Inlämningsdatum 22 sep 2023 av 18:00
- Poäng 10
- Lämnar in en filuppladdning
Mål | Läs i kursboken |
Laborationens tema är grafer och breddenförstsökning. Se Föreläsning 6, Övning 4 | Kapitel 8.1 - 8.10 Links to an external site. |
□ Förberedande uppgifter
- Rita upp en graf, och skriv upp grannmatris samt grannlista för följande ord: tre öre tri tro trå trä. Grafen ska ha kanter (oviktade, oriktade) mellan de ord som bara skiljer sig åt i en bokstav. Svara på frågorna:
- Hur många noder har din graf?
- Hur många kanter?
- Hur stor andel av grannmatrisen är fylld?
- Rita upp en graf, och skriv upp grannmatris samt grannlista för följande ord: arg ärg agg alg ark arm art arv. Grafen ska ha kanter (oviktade, riktade) mellan de ord som bara skiljer sig åt i en bokstav. Du får bestämma riktningar själv. Svara på frågorna:
- Hur många kanter har din graf?
- Hur stor andel av grannmatrisen är fylld?
- Finns det cykler i grafen?
□ Problembeskrivning
I labb 4 och 5 ska du lösa följande problem.
Finn kortaste vägen från ett ord till ett annat genom att byta ut en bokstav i taget. Exempel:
söt -> söm -> döm -> dum -> dur -> sur
Alla mellanliggande ord måste finnas i en ordlista (t ex ordlistan word3.txt Download word3.txt från förra laborationen). Kan du komma på en kortare väg än den med sex ord ovan?
Nu i labb 4 ska du skriva ett program som avgör om det finns en väg eller inte. Lösningsprincipen gås igenom nedan och den beskrivs ofta i läroböcker för det analoga problemet att finna kortaste väg i en graf. Exempel:
Startord: söt
Slutord: sur
Det finns en väg från söt till sur.
I labb 5 ska du sedan skriva ut vägen, dvs orden i lösningen.
□ Breddenförstsökning
Hur ska vi använda breddenförstsökning i problemet? Det här är ett grafproblem, men vi ska inte lagra grafen i en grannmatris eller grannlista. Istället skapar vi grafens hörn under tiden som programmet körs, enligt följande algoritm.
Problemträdets urmoder/stamfar söt har barnen nöt, sot, söm med flera,
barnbarnen not, som, döm osv.
Enligt kedjan söt -> söm -> döm -> dum -> dur -> sur är
sur barnbarnsbarnbarnsbarn till söt, men sur finns kanske 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 ursprungsordet som första och enda ord i en kö.
- Upprepa sedan följande så länge det finns ord kvar i kön:
- Plocka ut det första ordet ur kön,
- ...skapa alla barn till det,
- ...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.
-
Första versionen
Låt main.py (där du skriver ditt huvudprogram) utgå från förra labben, som ju har
två binärträd. Nu kallar vi dom svenska (ordlistan med orden från word3.txt) och gamla (här ska dumbarnen läggas in vartefter).
Huvudprogrammet ska- läsa in ordlistan,
- fråga efter startord och slutord,
- och göra anropet makechildren(startord).
i startordet (aöt, böt, ..., söö), kolla att det nya ordet finns i
ordlistan men inte finns i gamla och i så fall skriva ut det nya ordet på
skärmen och lägga in det i gamla.
Provkör! Om du gjort rätt ska söt få 10 barn. -
Andra versionen
För fortsatt genomgång av söts barnbarn osv behövs den köklass LinkedQ som du skrev i labb 2, kortkonstlabben. Importera den och skapa kön q. I stället för att skriva ut barnen på skärmen ska nu makechildren() lägga in dom i kön. Huvudprogrammet lägger in startordet i kön och går sedan i en slinga, ungefär så här:
while not q.isEmpty(): word = q.dequeue() makechildren(word, q)
När makechildren() stöter på slutordet gör den utskriftenprint("Det finns en väg till", slutord)
eller talar om att ingen väg fanns. Provkör med lite olika start- och slutord, bland annat blå - röd, ful - fin och ute - hit.
Du får själv välja vilka parametrar (och ev returvärden) du vill ha i makechildren.
Betyg
Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i period 2.
Redovisning
Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!
Vid redovisningen ska du kunna
- visa upp och redogöra för de förberedande uppgifterna ovan,
- förklara varför en kö används i bredden-först-sökning,
- förklara varför bredden-först-sökning ger den kortaste lösningen
Ingen Kattis-inlämning för denna labb!