□ Förberedande uppgifter

1. 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?
2. Rita upp en graf med riktade kanter (bestäm riktningar själv), och skriv upp grannmatris samt grannlista för följande ord: arg ärg agg alg ark arm art arv. 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
(noterat: I filen word3.txt saknas "döm" men principen bör framgå)

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.

1. Lägg ursprungsordet som första och enda ord i en kö.
2. 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.

1. Första versionen

   Låt filen bfs.py utgå från förra labben, som ju har
   två binärträd. Nu kallar vi dom svenska (ordlistan) och gamla (dumbarnen).
   Huvudprogrammet ska
   1. läsa in ordlistan,
   2. fråga efter startord och slutord,
   3. och göra anropet makechildren(startord).
   Funktionen makechildren ska systematiskt gå igenom alla sätt att byta ut en bokstav
   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.

2. 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(): nod = q.dequeue() makechildren(nod, q)

   
   När makechildren() stöter på slutordet gör den utskriften

       print("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.

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 4.

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

Vi ska inte ha någon kattis-inlämning på denna uppgift (efter synk med andra kursledare)