Hur ska vi använda breddenförstsökning i det här problemet?

Problemträdets urmoder/stamfar fan har barnen fin, man, far med flera, barnbarnen hin, mun, får osv. Enligt kedjan ovan är gud barnbarnbarnbarnbarnbarnbarn till fan, men gud finns säkert 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 urmodern/stamfadern som första och enda post i en kö. Gör sedan följande om och om igen:

• Plocka ut den första ur kön,
• skapa alla barn till den
• 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), redan tidigare besökta noder/barn (i den här kursen men ingen annanstans i världen kallas de ibland dumbarn). Uppgiften är så komplicerad att det är lämpligt att lösa den stegvis.

Skriv en funktion makechildren som givet ett ord genererar alla andra ord man kan få genom att byta ut en bokstav i ordet. Du kan utgå från lilla alfabetet och det är tillåtet att hårdkoda längden till tre (men skriv det i funktionskommentaren). Skriv en testfunktion som anropar makechildrenoch kollar att antal genererade ord stämmer matematiskt. Det finns flera olika sätt att strängmanipulera bokstavsutbytet men det finns inga krav på koden mer än att testet stämmer.

Ladda ner alla tre-staviga ord i svenska språket i filen word3.txt

• word3.txt UTF8-format, använd den här i första hand
• word3_ISO8859.txt ASCII-format iso-latin-1, prova denna om du har problem med åäö

Läs in alla orden och spara dem i en hashtabell DictHash som du tillverkade i lab d2.

Modifiera makechildren så att enbart giltiga barn (som finns i ordlistan) genereras. Testa funktionen med ordet fan som ska ge 17 unika barn.

Ett av barnen till fan är fin och motsvarande; ett av barnen till fin är fan.

Om man inte tar hänsyn till redan besökta ord så kan man få oändliga kedjor och aldrig komma fram till någon lösning.

fan -> fin -> fan -> fin -> fan -> fin -> fan ...
fan -> fin -> din -> dan -> fan -> fin -> din ...

Spara undan redan besökta ord i en ny DictHash och modifiera makechildren så att enbart barn som inte förekommit tidigare genereras.

Skapa minst ett fördefinierat testfall där du på förhand lägger in några av fans barnord och kollar att dessa inte genereras av makechildren

För fortsatt genomgång av fans barnbarn osv behövs den köklass som du använde i kortkonstlabben. Importera den koden och skapa kön queueOfWords.

Läs igenom föreläsningen om grafer och bredenförstsökning. Skriv en funktion som tar ett startord och slutord och tar reda på om det finns en väg mellan dem. Algoritmen (från föreläsningsanteckningarna) ser ut ungefär så här:

1. Lägg startordet i kön.
2. Ta ut det första ordet ur kön.
3. Om vi tagit ut slutordet så är vi klara (break) annars
4. Skapa alla barn och lägg in dom i kön och upprepa från 2
5. Om kön är tom fanns ingen väg

queueOfWords.enqueue(startord)  
while not queueOfWords.isEmpty():
    nextWord = q.dequeue()
    # anropa makechildren och lägg in nya barn i kön
    # ...

if queueOfWords.isEmpty(): 
    return False
else:             # Kan också returnera direkt i while-satsen
    return True

Det tråkiga med programmet är att det bara talar om att det finns en lösning. För att programmet ska kunna skriva ut alla ord på vägen mellan fan och gud måste varje ord kunna peka på sin förälder. Det är alltså inte typen string man ska arbeta med utan en ParentNode som ser ut så här.

class ParentNode:
    def __init__(self, word, parent = None):
        self.word = word
        self.parent = parent

Låt ditt program skapa ett sådant objekt och lägga in startordet. Det som sätts in i kön och plockas ut ur kön är nu inte längre ord utanParentNode, och det betyder att du måste ändra i din kod. Istället för att returnera True/False så returnerar din funktion noden med slutordet eller None om det inte fanns en väg.

Skriv en rekursiv funktion writechain som tar en ParentNode och skriver ut hela kedjan i rätt ordning d.v.s. slutordet sist. Prova att variera placeringen av det rekursiva anropet så att du kan förklara hur writechain fungerar. (Liten instuderingsuppgift i att rekursivt vända en lista från  motsvarande laboration på systerkursen TILDA.)

Skriv ett huvudprogram som tar två kommandoradsargument (via sys.argv) som start- och slutord och skriver ut vägen, om det finns en väg, och ett annat meddelande om det inte finns en väg.

Kontrollera att programmet anropas med tillräckligt många kommandoradsargument t.ex. genom följande kod.

import sys

if len(sys.argv) < 3:
    print("Start- och slutord saknas")
    print("Använd programmet så här: \n\t python3", sys.argv[0], " [startord] [slutord]")
    sys.exit()

#...

Vid redovisningen ska du kunna

• rita upp problemträdet,
• förklara i detalj hur breddenförstsökningen fungerar,
• förklara varför breddenförstsökning ger den kortaste lösningen,
• visa och förklara hur utskriften av lösningen fungerar
• visa att funktionen makechildren är bra kommenterad (in, ut, intention)