Introduktion til Decision Tree Applet

Mark Greve, 2009

Introduktion til problemstilling

I denne applet arbejder man med beslutningstræer til sortering. Det vil sige, at det handler om sortering via et beslutningstræ. Et beslutningstræ er her et binært træ, hvor hver intern knude har to indekser tilknyttet. I vores tilfælde sorterer vi n bogstaver alfabetisk. Man sorterer en permutation af n bogstaver på følgende måde. Man starter i roden af træet og sammenligner de to bogstaver på de to indekser i og j tilknyttet roden. Hvis bogstavet på position i er mindre end bogstavet på position j, fortsætter man til rodens venstre barn, og ellers fortsætter man til rodens højre barn. Man laver så en tilsvarende sammenligning for knuden, man nu er nået til og fortsætter på samme måde indtil man når et blad. Under hvert blad udskriver appletten alle de permutationer, der startende i roden ender i det blad.

Det handler om at konstruere et beslutningstræ, der kan sortere korrekt. Dette er tilfældet, når alle permutationer af n bogstaver ender i hver deres blad i træet. Hvis to eller flere permutationer ender i det samme blad, betyder det, at de sammenligninger, vi har udført stadig ikke er nok til at beslutningstræet ved præcis, hvad vores input er. Dette betyder, at vi endnu ikke kan sortere inputtet.

Det kan måske være lidt vanskeligt at forstå i første omgang, men det forhåbentligt blive klarere efter, man har arbejdet lidt med appletten. Et sekundært mål er at lave et korrekt beslutningstræ med så lav dybde som muligt, dvs. den længste vej til et blad skal have så få sammenligninger som muligt.

Figur 1: Beslutningstræ med n=2 bogstaver.
Image fign2

På figur 1 ses et beslutningstræ for sortering af to bogstaver. Her er det naturligvis blot nødvendigt at lave en sammenligning for at afgøre den sorterede rækkefølge. Tallene i roden betyder, at vi sammenligner elementerne på position 1 og 2, og hvis input f.eks. er a,b, så går vi mod venstre fra roden, idet a<b er sand. Nu ved vi, at input er a,b. Hvis input derimod var b,a, så er b<a falsk og vi går mod højre. Nu ved vi, at det andet element er størst, og der skal byttes om på de to for at sortere listen. Dette beslutningstræ har dybde 1 og laver højst (altid) 1 sammenligning for at sortere n=2 elementer.

Figur 2: Partielt beslutningstræ for n=3 bogstaver.
Image fign3

På figur 2 ses endnu et beslutningstræ (med dybde 3). Denne gang sorterer vi n=3 bogstaver, men vi har endnu ikke bygget et korrekt beslutningstræ til sortering. Vi kan se, at hvis vi sorterer a,b,c, så finder roden og dens venstre barn ud af, at a<b og b<c, så hermed ved vi, at input allerede er sorteret. For input a,c,b og b,c,a er vi gået til venstre i roden, da a<c og b<c. I rodens venstre barn sammenligner vi bogstav 2 op mod 3 og finder ud af, at c>b og c>a. Vi ved endnu ikke, om det er bogstavet på position 1 eller 3, der er mindst. Hvis vi ser på permutationerne a,c,b og b,c,a, kan vi også se direkte, at det er bogstaverne på position 1 og 3, der endnu ikke er afgjort. I den første permutation er det a og b og i den anden er det b og a. På denne måde kan man se, hvilke sammenligninger, der vil hjælpe på at få bygget et korrekt beslutningstræ.

Man kan altså tænke på det, der står i bladene således. Hvis man var gået fra roden til et blad, så kan input være alle de mulige permutationer, der står under bladet. Derved er det også klart, at hvis der er mere end en permutation, så ved vi endnu præcis ikke, hvad den sorterede rækkefølge er.

Forklaring af brugergrænseflade

Figur 3: Brugergrænseflade
Image startup

På figur 3 kan man se, hvordan brugergrænsefladen ser ud ved sortering af n=4 elementer. I starten er der kun et blad. Man kan så klikke på bladet, og indtaste to indekser, hvis elementer man gerne vil have sammenlignet. Inputformatet for at sammenligne bogstaverne på indeks i og j er i,j.

Figur 4: Efter en sammenligning
Image onecomparison

På figur 4 kan man se, hvordan det ser ud efter, at man har indtastet, at roden skal sammenligne bogstaverne på indekserne 1 og 2. Alle 4! permutationer bliver nu vist under det blad, de vil ende ved, når de starter i roden og kører igennem træet. Man kan se, at alle permutationer, hvor bogstavet på indeks 1 er mindre end bogstavet på indeks 2 er forsat til rodens venstre barn, og resten er fortsat til rodens højre barn. Ved siden af hver knude (eller blad) kan man se, hvor mange permutationer, der kommer igennem den knude (eller blad) i træet.

Bemærk, at man altid har mulighed for at ændre sammenligningerne for en knude ved at klikke på den og indtaste to indekser.

Starte forfra

Hvis man klikker på Clear tree, bliver beslutningstræet slettet og man starter igen ud med et træ indeholdende et enkelt blad.

Korrekt beslutningstræ til sortering

I højre hjørne af appleten kan man se, hvad dybden af beslutningstræet er. Dybden er det højeste antal af sammenligninger, man udfører for at nå et blad fra roden. For at finde ud hvorvidt man har lavet et korrekt beslutningstræ til sortering trykkes på knappen Verify. Denne checker blot, at alle blade højst har en permutation tilknyttet.

Upload

For at man indbyrdes kan sammenligne hvor god en løsning man har fundet til problemet er der mulighed for at uploade resultatet til en high score liste. Denne high score-liste indeholder kun korrekte beslutningstræer til sortering.

Links til applet

Følg følgende links for at starte appletten: