Till KTH:s startsida Till KTH:s startsida

Laboration 4

Laboration 4 - Grafer, breddenförstsökning

Läsning

Läs kapitel 6.1-6.4.1 om Grafer i kursboken (från Objectives fram till och med implementing breadth first search).

Problembeskrivning

Du ska skriva ett program som kan lösa problem av följande typ: 

Finn kortaste vägen från söt till sur 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 ordlistan word3.txt  från förra laborationen.

Ditt program ska finna en kortare väg till sur ä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.

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?

Breddenförstsökning

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

Problemträdets urmoder/stamfar söt har barnen  nöt, sot, söm med flera,
barnbarnen döm, som, not osv.

Enligt kedjan söt->söm->döm->dum->dur->sur är
sur barnbarnbarnbarnbarn 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 urmodern/stamfadern som första och enda post i en kö.
  2. Upprepa sedan följande så länge det finns poster kvar i kön:
    • 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 dumbarn (eller redan-besökta-noder)

  1. Första versionen

    Låt filen bfs.py utgå (importera) 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).
    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 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 

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


    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.

 

Redovisning

Labben lämnas in via git och redovisas muntligt av bägge gruppmedlemmarna.

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

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 nästa period.