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 gudsur ä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 ärsur barnbarnbarnbarnbarn till söt, men sur finns säkert redan tidigare iproblemträdet. För att finna den första förekomsten gör man enbreddenfö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 ärkopior av tidigare släktingar (t ex nöts barn söt), såkallade besöktabarn. Uppgiften är så komplicerad att det är lämpligt attlösa den stegvis.

* Första versionen Låt filen bfs.py utgå från förra labben, som ju hartvå 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 bokstavi startordet (aöt, böt, ..., söö), kollar att det nya ordet finns iordlistan 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.
* 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.
* 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 fansöt och gudsur 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
* Perfekt program
* Labben inlämnad via KTH Social i tid och redovisad i tid (se datum under Laborationer).Du ska också:
* Implementera bokens sätt att skapa noder i problemträdet.
* Provkör med både word3.txt och fembokstavsordlistan word5.txt.
* Jämföra med grunduppgiftens algoritm och beskriv fördelar och nackdelar.

betyg A:

* Kraven för C uppfyllda
* Följande två extrauppgifter:
* Längst från söt: Undersök vilka trebokstavsord som har längst väg till söt (längsta kortaste vägen, inte längsta omvägen).
* 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? Ledning: Iterera över föregående uppgift.

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