Nada

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.

class Node     { // problemträdspost
  double amount; // belopp
  int currency ; // valutanummer, SEK=1, USD=2,...
  Node father  ;}// faderspekare

class Change                                   {
  static double[][] kurs=...                   ;
//  - - - inläsning av växlingskurserna - - -  ;
//  - - - metoden makeSons(Node far)    - - -  ; 
  try                                          {
    stamfar=new Node()                         ;
    stamfar.amount=1.00                        ;
    stamfar.currency=1                         ;
    Queue.Put(stamfar)                         ;
    while(!q.isEmpty()) makeSons((Node)q.get());
    System.out.println("Ingen lönsam växling") ;}
  catch (Exception e)                          {
    System.out.println("Växla fort!")          ;}
Metoden makeSons skapar alla söner och lägger 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                                                          {
  static final int N=8                                                ;
  static boolean[][] dam=new boolean[N][N]                            ;

  static void Try(int r, int k)                                       {
    if(!OK(r,k)) return                                               ;
    dam[r][k]=true                                                    ;
    if(r+1<N) for(int j=0;j<N;j++) Try(r+1,j); else write()           ;
    dam[r][k]=false                                                   ;}

  static boolean OK(int r, int k)                                     {
    for(int i=0; i<r; i++) if(dam[i][k]) return false                 ;
    for(int j=0; j<k; j++) if(dam[r][j]) return false                 ;
    for(int n=1; r-n>=0 && k-n>=0; n++) if(dam[r-n][k-n]) return false;
    for(int n=1; r-n>=0 && k+n<N;  n++) if(dam[r-n][k+n]) return false;
    return true                                                       ;}

  static void write()                                                 {
    System.out.println("---------------")                             ;
    for(int i=0; i<N; i++)                                            {
      for (int j=0; j<N; j++)                                         {
	if(dam[i][j]) System.out.print("D ")                          ;
	else System.out.print(". ")                                   ;}
      System.out.println()                                            ;}}
    
  public static void main(String[] args)                              {
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) dam[i][j]=false     ;
    for(int k=0; k<N; k++) Try(0,k)                                   ;}}

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!


Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 17 februari 1999
Tekniskt stöd: <webmaster@nada.kth.se>