Datalogilaboration 7 - Salighet

Salighet är att finna kortaste vägen från fan till gud genom att byta ut en bokstav i taget, till exempel så här:
fan -> man -> mun -> tun -> tur -> hur -> hud -> gud
Alla mellanliggande ord måste finnas i ordlistan word3 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 finns också beskriven i läroboken, sid 382-386, men då för kortaste väg i en graf.

Breddenförstsökning

Problemträdets stamfar fan har sönerna fin, man, far med flera, sonsönerna hin, mun, får osv. Enligt kedjan ovan är gud sonsonsonsonsonsonson 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 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 söner till denne 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 söner som är kopior av tidigare släktingar (t ex mans son fan), så kallade dumsöner.

Första versionen

Uppgiften är så komplicerad att det är lämpligt att lösa den stegvis. Skriv i filen Fan.java först en class Fan1 och utgå från förra labben, som ju har två binärträd, ordträd och oldwords. Huvudprogrammet ska läsa in ordlistan, fråga efter startord och slutord, och göra anropet makeSons(startord). Denna metod går systematiskt igenom alla sätt att byta ut en bokstav i startordet, kollar att det nya ordet finns i ordlistan men inte finns i oldwords och skriver i så fall ut det nya ordet på skärmen. Det kan vara lämpligt att deklarera startord, slutord och dom båda binärträden globalt, så att dom kan användas i makeSons().

Om du gjort rätt ska fan få sjutton söner.

Andra versionen

För fortsatt genomgång av fans sonsöner osv behövs den köklass som du använde i swahiliglosförhöret. Versionen class Fan2 deklarerar och skapar inte bara träden ordträd och oldwords utan även kön q. I stället för att skriva ut sönerna på skärmen puttar makeSons in dom i kön. Huvudprogrammet puttar in startordet i kön och går sedan i en slinga
    while (!q.isEmpty()) 
        makeSons((String)q.get());
(Minns du varför (String) behövs?) När makeSons() stöter på slutordet gör den utskriften
    System.out.println("Det finns en väg till " + slutord);
Provkör med lite olika start- och slutord, bland annat röd - blå 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 veta hur det har funnit gud måste varje ord kunna peka på sin far. Det är alltså inte typen String man ska arbeta med utan typen Node som ser ut så här.
    class Node {
        String word;
        Node father = null;
    }
Huvudprogrammet skapar en sådan post och lägger in startordet. Det som sätts in i kön och plockas ut ur kön är nu inte längre String utan Node, och det medför några ändringar i makeSons. När makeSons finner slutordet vill den skriva ut hela kedjan genom ett anrop writeChain(son). 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 System.exit(0), ett annat är throw new Exception("Det finns en väg till " + slutord).

Frivillig uppgift: Försök göra ditt program till en applet på din webbsida. Tips finns i filen Appletfan.java på kursbiblioteket.

Suveränt hackat av ..................................... suckar.............................. den .................


^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 27 oktober 2000
Tekniskt stöd: <webmaster@nada.kth.se>