Optimaler Suchbaum Eigenschaften prüfen?
Hallo, ich habe folgende Aufgabe:
Gegeben sei der folgende Suchbaum, in dem die Elemente A;B;C;D;E
lexikographisch geordnet sind. Beweisen oder widerlegen Sie:
Der Baum kann ein optimaler Suchbaum mit 2,1 erwarteten Vergleichen sein.
Da kommen ich und viele andere nicht weiter, die meisten neigen zur Meinung, dass die Aussage falsch ist. Wir haben dazu sehr viele Gleichungen aufgestellt, die aber kompliziert zu lösen scheinen: (a bis e sind die jew. Zugriffswahrscheinlichkeiten)
a+b+c+d+e=1
a+2b+4c+3d+4e=2,1
Durch die e_ij Tabellen (erwartete Anzahl Vergleiche im Unterbaum von i bis j):
b<=a, e<=d<=c
Aber ich stecke jetzt fest wie ich hier wirklich weiterkomme. Muss ich etwa noch mehr Ungleichungen/Gleichungen aufstellen?
Vielen Dank im Voraus!
1 Antwort
Wenn die Verteilung nicht vorgegeben ist, und Dein Ziel eine Verteilung ist, die E=2,1 erzeugt, dann könnte man das so machen:
Es sei v(k) die Anzahl der Vergleich für den Schlüssel k, also für k=A ist v(k)=1. Ferner sei |k| die Anzahl der verschiedenen Schlüssel.
Ferner sei:
mit k aus {A,B,C,D,E}
So ergibt sich ein Erwartungswert von 2,1 Vergleichen.
p.robability - Also die Wahrscheinlichkeit.
Ja genau. Für die Konstruktion habe ich die Ws so festgelegt, daß das Produkt mit der Vergleichszahl 1 gibt, durch die Gesamtzahl der Elemente geteilt als Normierung und mit dem Wunsch-Erwartungswert multipliziert.
Versteh ich richtig dass |k| = 5 immer? Dann kommt bei mir 2,1/5 + 2,1/10 + 2,1/15 + 4,2/20 = 0,98 raus.
Da sollten 4,2/40 sein, aber das macht es auch nicht besser - das ist in der Tat ein Problem, ich habe nur darauf geachtet, daß der benötigte Erwartungswert erreicht wird.
Die ursprüngliche Idee bei der ich gestartet war ist folgende:
Wenn ich eine Gleichverteilung hätte, dann wäre der Erwartungswert die Summe der Vergleich je Schlüssel mal 1/|k| also 14/5=2,8.
Um das zu drücken, muß ich im Wesentlichen dafür sorgen, daß Schlüssel für die es weniger Vergleiche braucht eine höhere Wahrscheinlichkeit hat, als für jene, die weiter unten im Baum sind.
Die erste Idee war sowas wie A=1/2, B=1/4 D=1/8 E=1/16 F=1/16.
Und dann habe ich halt überlegt, wie ich zum exakten Wunscherwartungswert komme, aber übersehen, daß die Summe des Ws immernoch 1 ergeben muß.
Für die oben genannten Ws ergäbe sich dann für den Erwartungswert:
8/16+8/16+6/16+4/16+4/16=30/16 < 2
Leider war die Idee für die generische Konstruktion nicht ganz so prickelnd - Im Kern hast Du das Problem 5 Ws festlegen zu müssen, aber eben nicht entsprechend viele Gleichungen zu haben.
Klar ist hat nur, daß Du von der Gleichverteilung weg mußt und die Wahrscheinlicheit mit der Tiefe abnehmen muüßt, aber wie man nun genau die Gewichte konstruieren kann, dazu habe ich gerade keine weitere Idee.
Aber die Zugriffswahrscheinlichkeiten sollen zusammen 1 ergeben. Was genau soll p sein?