Föreläsning 9: Problemträd

Problemträd

En mycket stor klass av praktiska problem kan beskrivas med problemträd och lösas med trädgenomgång, bredden först eller djupet först. På tentan kommer något sådant problem och det gäller att beskriva lösningsalgoritmen. Laboration 7 går ut på att finna kortaste vägen från fan till gud genom att byta en bokstav i taget och bara använda ord i ordlistan, till exempel så här:
    fan -> man -> mun -> tun -> tur -> hur -> hud -> gud
Problemträd uppkommer ständigt i praktiken och man brukar använda en sexistisk terminologi med stamfar, söner etc. PROBLEMTRÄD

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.

Breddenförstsökningsalgoritmen kan sammanfattas så här.

Om man bara lägger själva orden i kön finns det ingen möjlighet att i efterhand tala om vägen från fan till gud. Därför bör man för varje nytt ord skapa en liten post som innehåller ordet och en pekare till fadern. Om kön är gjord för lagring av typen Object går detta bra.

Breddenförstsökning ger alltid den kortaste lösningen. Ofta är det den man är ute efter. Några andra problemexempel är följande.

Flygresa från Stockholm till Windhoek

Stockholm är stamfar, destinationer med direktflyg från Stockholm blir söner och så vidare. Breddenförstsökning ger en resa med så få mellanlandningar som möjligt.

Lönsam valutaväxling

Finns det någon lönsam växlingskedja av typen 1.00 SEK -> 0.14 USD -> ... -> 1.02 SEK ? Vi vill ha en algoritm som kan besvara den frågan.

Vi antar att alla växlingskurser är kända, t ex 1.00 SEK -> 0.14 USD och 1.00 USD -> 7.05 SEK. En valutanod är ett belopp i en viss valuta. Vi utgår från valutanoden 1.00 SEK och låter den vara stamfar i ett problemträd. Stamfaderns söner är alla valutanoder som kan åstadkommas med en växling, till exempel 0.14 USD och 16.5 JPY. Sonen 0.14 USD har i sin tur söner, däribland 0.987 SEK. Just den är en så kallad dumson och kan lugnt glömmas bort, eftersom den är sämre än en tidigare valutanod.

Om man går igenom problemträdet nivå för nivå, dvs generation efter generation, kanske man till sist stöter på noden 1.05 SEK. Därmed har man funnit en lönsam växlingskedja och det är bara att sätta igång och växla så fort som möjligt innan kurserna ändras. Om man har en abstrakt kö med metoderna put(), get() och isEmpty() kan breddenförstsökningen programmeras ungefär så här.

// Problemträdspost
class Node { 
    double amount; // Belopp
    int currency;  // Valutanummer, SEK = 1, USD = 2,...
    Node father;   // Faderspekare

    // Konstruktor för att underlätta skapandet av en node
    Node(double a, int c, Node f) {
	amount = a;
	currency = c;
	father = f;
    }
}

public class Exchange {
    static double[] kurser;

    // Inläsning av växlingskurserna

    // Metod som skapar söner utifrån en far och kontrollerar om 
    // en lösning är funnen.
    public static void makeSons(Node far) throws Exception {
	// Om en nyskapad son är en lösning görs ett undantag 
	// "exception".
	// Varje (vettig) son läggs sist i kön.
    }
    // Huvudprogrammet, main()
    public static void main(String[] args) {
	Queue q = new Queue();

	try {
	    // Skapa stamfarsnod (1.00 kr, SEK, ingen far) 
	    Node stamfar = new Node(1.00, 1, null);
	    q.put(stamfar);

	    // Så länge som en far finns i kön...
	    while (!q.isEmpty())
		// Plocka ut farsan och låt han skapa söner...
		// (Lösning kan hittas och ge upphov till undtantag)
		makeSons((Node)q.get());

	    // Kommer vi hit har alla möjliga växlingar kollats
	    System.out.println("Ingen lönsam växling");
	}
	catch(Exception e) {
	    // Lösning fanns!
	    System.out.println("Växla fort!");
	}
    } // main()
}

Metoden makeSons() skapar alla söner och lägger dem sist i kön. Om man vill bli av med dumsönerna kan man ha en global vektor best med hittills högsta belopp av varje valuta.

Rekursiv djupetförstsökning

En problemklassiker är åttadamersproblemet som innebär att man ska placera åtta damer på ett schackbräde så att ingen dam står på samma vågräta, lodräta eller diagonala linje som någon annan. Breddenförstsökning med ett tomt bräde som stamfar, endamsställningar som söner, tvådamsställningar som sonsöner etc fungerar i princip, men blir onödigt minneskrävande. Här finns en rekursiv tanke att ta till.
class Queens {
    private static boolean[][] queen;
    
    public static void main(String[] args) {
	// Create a board with no queens
	queen = new boolean[8][8];
	for (int r = 0; r < queen.length; ++r)
	    for (int c = 0; c < queen[0].length; ++c) 
		queen[r][c] = false;

	// Find solutions by placing the first queen on the first row.
	// Try all columns.
	for (int c = 0; c < queen[0].length; ++c)
	    place(0, c);
    }

    public static void place(int r, int c) {
	if (!ok(r, c))
	    return;

	queen[r][c] = true;

	if (r + 1 < queen.length)
	    for (int j = 0; j < queen[0].length; ++j)
		place(r + 1, j);
	else
	    write();

	queen[r][c] = false;
    } 

    static boolean ok(int r, int c) {
	// N direction
	for (int i = r - 1; i >= 0; --i)
	    if (queen[i][c])
		return false;
	// W direction
	for (int j = c - 1; j >= 0; --j)
	    if (queen[r][j])
		return false;
	// NW direction
	for (int n = 1; r - n >= 0 && c - n >= 0; ++n)
	    if (queen[r - n][c - n])
		return false;
	// NE direction
	for (int n = 1; r - n >= 0 && c + n < queen[0].length; ++n)
	    if (queen[r - n][c + n])
		return false;
	return true;
    } 

    public static void write() {
	System.out.println("---------------");
	for (int r = 0; r < queen.length; ++r) {
	    for (int c = 0; c < queen[0].length; ++c) {
		if (queen[r][c])
		    System.out.print("D ");
		else
		    System.out.print(". ");
	    } 
	    System.out.println();
	}
	Mio.getLine(); // Wait for return
    } 
}



Djupetförstsökning med stack

Hitta ut ur labyrint

Problemträdet har startpositionen som stamfar, alla positioner på ett stegs avstånd som söner och så vidare. En position som man varit på förut är en dumson.

En välkänd praktisk metod att utforska en labyrint, uppfunnen av den förhistoriska datalogen Ariadne, är att ha ett garnnystan med ena änden fastknuten i startpunkten. Man går så långt man kan, markerar med krita var man varit, går bara outforskade vägar framåt och backar en bit längs snöret när man kör fast.

Den här algoritmen är djupetförstsökning och den kan programmeras exakt likadant som breddenförstsökningen, med den lilla skillnaden att kön byts mot en stack. Den är sämre än breddenförstsökning i två avseenden:

Djupetförstsökning används när man nöjer sej med att hitta en lösning. Den kräver då ofta mindre minne än breddenförstsökning.

Luddes portkodssekvens

En teknolog som glömt sin fyrsiffriga portkod tryckte sej igenom alla tiotusen kombinationer så här.
000000010002000300040005000600070008000900100011...9999
Det kräver fyrtiotusen tryckningar. Men man kan klara sej med bara tiotusentre tryckningar om man har en supersmart sekvens där varje fyrsiffrigt tal förekommer någonstans. Hur ser sekvensen ut?

Problemträdets stamfar 0000 har tio söner 00000, 00001,..., 00009, varav den förste är dumson. Breddenförst eller djupetförst? Vi vet att trädet har djupet tiotusen och att alla lösningar är lika långa, därför går djupetförst bra. Men breddenförst skulle kräva biljoner poster!


^ Upp till kurssidan.


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