Till KTH:s startsida Till KTH:s startsida

Laboration 4

Laboration 4 - Från söt till sur

Det gäller att finna kortaste vägen från söt till sur genom att byta ut en bokstav i taget, till exempel så här:

söt->söm->döm->dum->dur->sur

Alla mellanliggande ord måste finnas i ordlistan word3.txt från förra laborationen.

Ditt program ska finna en kortare väg till gud än den här föreslagna. 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.

Breddenförstsökning

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

Problemträdets urmoder/stamfar söt har barnen nöt, sot, söm med flera,
barnbarnen döm, som, not osv. Enligt kedjan ovan är
sur barnbarnbarnbarnbarn till söt, men sur 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 nöts barn söt), så
kallade besöktabarn. Uppgiften är så komplicerad att det är lämpligt att
lösa den stegvis.

  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 läsa in ordlistan, fråga efter startord och slutord,
    och göra anropet makechildren(startord).
    Denna funktion går systematiskt igenom alla sätt att byta ut en bokstav
    i startordet (aöt, böt, ..., söö), kollar att det nya ordet finns i
    ordlistan men inte finns i gamla och skriver i så fall ut det nya ordet på
    skärmen och lägger in det i gamla.
    Om du gjort rätt ska söt få 10 barn.
  2. Andra versionen

    För fortsatt genomgång av fans barnbarn osv behövs den köklass som du använde i kortkonstlabben. Importera den och skapa kön q. I stället för att skriva ut barnen på skärmen lägger makechildren in dom i kön. Huvudprogrammet lägger in startordet i kön och går sedan i en slinga

    while not q.isEmpty():
        nod = q.get()
        makechildren(nod)
    


    När makechildren() stöter på slutordet gör den utskriften
        print("Det finns en väg till", slutord)
    
    Provkör med lite olika start- och slutord, bland annat blå - röd, ful - fin och ute - hit.
  3. Tredje versionen

    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
    


    Huvudprogrammet skapar ett sådant objekt och lägger 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 makechildren.

    När makechildren finner slutordet vill den skriva ut hela kedjan genom ett anrop writechain(child). Metoden writechain() ska skrivas rekursivt, så att man får ut kedjan med slutordet sist.

    Om kön töms utan att någon lösning påträffats bör programmet meddela att det är omöjligt. Och när en lösning skrivits ut bör programmet avbryta körningen. Ett sätt att göra det är sys.exit() om man importerar modulen sys.

Betyg

betyg E: Ditt program ska lösa uppgifterna ovan.
Vid redovisningen ska du också 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 hur utskriften av lösningen fungerar

betyg C: Kraven för E uppfyllda +  Labben inlämnad via KTH Social i tid och redovisad i tid (se datum under Laborationer).
Du ska också:

  • implementera djupetförstsökning för samma problem
  • kunna jämföra algoritmerna och förklara skillnaden i resultat

betyg A: Kraven för C uppfyllda + en av följande extrauppgifter:

  • Längst från söt: Undersök vilket trebokstavsord som har längst väg till söt. Du måste då skriva en rekursiv countchain(child) som returnerar kedjans längd. Ledning: Om startord och slutord byter roller ändrar det inte kedjans längd.

  • Längst från varandra: Vilka två ord är längst från varandra?

Denna labb ska du redovisa tillsammans med labb 2 och labb 3.

Alexander Baltatzis created page 14 January 2014

commented 7 February 2014

På C uppgiften på labb fyra så undrar jag om man fortfarande ska lösa problemet kortaste vägen till gud eller om det bara är en väg till gud man ska få fram. Om det bara är en väg till gud så tycker jag frågan kan formuleras tydligare för att undvika merarbete för andra elever.

commented 9 February 2014

Jag har samma fundering som Patrik. :)

commented 17 February 2014

Hej! Vi har en liten fundering på A-uppgiften 'Längst från gud'. Är det så att countchain(child) ska ingå i lösningen eller är den bara till för att visa längden på den väg som vi hittar?

Teacher commented 19 February 2014

@Patrik, Ludvig - nej det ska inte formuleras tydligare. Den som strävar efter betyg C ska kunna skillnaderna mellan bredden-först och djupet-först och vad som karakteriserar dem.

@Emil - Att hitta längst från Gud är rätt svårt. Kraven är inte lika höga på exakt rätt lösning, det räcker med att ni tänkt till ordentligt. En sak som är svårt är t.ex. redan-besökta-noder. Du måste kanske rensa så att vissa noder som redan-var-besökta blir obesökta i en annan gren som du undersöker.

commented 20 February 2014
The content of this comment is hidden.
commented 20 February 2014

*jag utgår ifrån att det inte är vad som avses...

commented 20 February 2014
The content of this comment is hidden.

has hidden kommentaren 20 February 2014

Reason: Uppgiften för C lyder: * implementera djupetförstsökning för samma problem * kunna jämföra algoritmerna och förklara skillnaden i resultat Alexander har redan förklarat att det är denna uppgift som ska lösas. Andra frågan handlar just om skillnaden - det ska varje kursdeltagare få fundera ut själv. ..." t ex om en student i en kurs presenterar färdiga lösningar på uppgifter som skulle ha lösts individuellt av alla studenter på kursen."

has hidden kommentaren 20 February 2014

Reason: Vilseledande kommentar.
commented 21 February 2014

Jag vet att det varit lite olikheter i tolkningen av A uppgiften längst från gud. Kan någon klargöra vilken tolkning som ska anses den 'officiella'? mao är det 'vilket ord har längst kortaste väg' eller är det 'längsta möjliga väg från ord x till gud'?

commented 21 February 2014

Jag redovisade A uppgiften med en lösning som hittade det ord vars kortaste väg till gud var längst. Det var det assarna sa till mig var rätt och som de även givit mig rätt på.

commented 21 February 2014

Kan man redan redovisa?

Teacher commented 21 February 2014

@Beatrice: Vi godkänner båda tolkningarna, oroas icke!

@Didrik: Ja - jag vet t ex att det var några som redan var klara i måndags och redovisade då. Men just nu finns det nog ingen på plats...

commented 21 February 2014

Vilken tur att ni ni inte ger någon tidsbegränsning på A uppgiften för mitt program tar 15 min att köra :)

Teacher commented 22 February 2014

Det är inget du behöver oroa dig för!

Men det är nog bra om du sparar utskrift  av en körning att visa up vid redovisingen :-)