Witam, jak w temacie, chodzi o optymalne, statyczne drzewo bst, mam na wejściu n elementów, każdy z nich posiada jakąś wartość, muszę tak umieścić je w drzewie by ich późniejsze wyszukiwanie było optymalne (oprócz wartości elementów na wejściu dostaję prawdopodobieństwo polecenia wyszukania każdego z nich), nie wiem jak się za to zabrać. Próbowałem zacząć od umieszczenia w korzeniu elementu o największym prawdopodobieństwie ale chyba nie tędy droga. Ponadto muszę uwzględnić że użytkownik może chcieć wyszukać elementy których nie ma w drzewie. Z góry dzięki za wszelką pomoc. Pozdrawiam
0
1
Podejście z umieszczaniem "wyżej" w drzewie węzłów o wyższym prawdopodobieństwie jest dobrym pomysłem, ale nie wystarczy. Bo w efekcie możemy uzyskać listę, która na pewno nie będzie optymalną strukturą do wyszukiwania.
Sęk w tym że masz minimalizować sumę poziom_w_drzewie*prawdopodobieństwo dla wszystkich węzłów. Wydaje mi się że metoda na budowanie takie drzewa wymaga:
- wrzucania węzłów tak jak pisałeś, zgodnie z prawdopodobieństwem
- następnie testowania sumy o której pisałem dla uzyskanego drzewa i dla możliwych rotowań
Czyli to by było takie zmodyfikowane drzewo AVL, które nie dokonuje balansowania automatycznie na całej trasie od liścia do korzenia, a tylko sprawdza czy lepsza jest wersja naiwna czy wersja po rotacji w węźle do którego dodaliśmy nowego liścia.
Czyli dla danych:
1 -> 0.4
2 -> 0.3
3 -> 0.2
I przy dodawaniu w kolejności malejącego prawdopodobieństwa mamy:
W pierwszym kroku
1
suma = 0.4*1 = 0.4
W drugim kroku
1
\
2
suma = 0.4 + 0.3*2 = 1
W trzecim kroku
1
\
2
\
3
suma = 1 + 0.2*3 = 1.6
lub po rotacji
2
/ \
1 3
suma = 0.4*2 + 0.3 1 + 0.22 = 0.8+0.3+0.4 = 1.5
Więc zostawiamy takie drzewo
Oczywiście rotacje mają tutaj sens tylko jeśli przywracają balansowanie, tzn nie ma sensu testować konfiguracji
3
/
2
/
1
W związku z tym wyszedłbym od AVLa i zamiast dokonywać rotacji aż do korzenia póki nie ma zbalansowania, wykonywałbym rotacje tylko jeśli suma nam sie zmniejsza.
0
http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol016.php
Samego kodu już nie musisz budować.</del> Zły pomysł - czytaj niżej.
1
_13th_Dragon napisał(a):
http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol016.php
Samego kodu już nie musisz budować.
Huffman tutaj nie jest właściwy, bo nie zachowuje porządku leksykograficznego. Żeby zachować porządek leksykograficzny (czyli aby kody miały taki sam porządek jak odpowiadające im symbole wejściowe) trzeba użyć innego algorytmu. Podobno tej tutaj generuje optymalne kody bitowe, które zachowują porządek: http://encode.ru/threads/378-Ordered-bitcodes-experiments?p=7528&viewfull=1#post7528
Poniżej wklejam kod od razu (tzn ten z test2.cpp):
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>
// symbol counts for book1
static int symbols[82] = {
1, 16622, 1, 125551, 832, 2468, 1, 6470, 43, 40,
1, 691, 10296, 3955, 7170, 98, 240, 185, 184, 151,
96, 87, 85, 85, 82, 220, 762, 498, 5, 498,
759, 967, 1463, 580, 269, 444, 413, 575, 977, 2899,
253, 45, 413, 565, 502, 856, 693, 14, 245, 850,
1966, 103, 64, 753, 5, 416, 47836, 9132, 12685, 26623,
72431, 12237, 12303, 37561, 37007, 468, 4994, 23078, 14044, 40919,
44795, 9332, 520, 32889, 36788, 50027, 16031, 5382, 14071, 861,
11986, 264
};
static int matrix[82][82];
static int src[82][82];
static char* code[82];
int solve(int a, int b) {
if (a==b) return 0;
int minimum=(1<<30),sum=0,sum2=0,s=0;
for (int i=a;i<=b;i++) sum2+=symbols[i];
for (int i=a;i<b;i++) {
int c;
c=(matrix[a][i]) + (matrix[i+1][b]+sum2);
if (c<minimum) minimum=c,s=i;
}
src[a][b]=s;
return minimum;
}
void codesfor(int a, int b) {
if (a==b) return;
for (int i=a;i<=src[a][b];i++) code[i]=strcat(code[i],"0");
for (int i=src[a][b]+1;i<=b;i++) code[i]=strcat(code[i],"1");
codesfor(a,src[a][b]);
codesfor(src[a][b]+1,b);
}
int solveall(int size) {
for (int len=0;len<size;len++) {
for (int start=0;start+len<size;start++) {
int end=start+len;
matrix[start][end]=solve(start,end);
}
}
for (int i=0;i<size;i++) code[i]=new char[64];
for (int i=0;i<size;i++) code[i][0]=0;
codesfor(0,size-1);
printf("\n");
for (int i=0;i<size;i++) printf("code(%d)=%s\n",i,code[i]);
return matrix[0][size-1];
}
int main() {
int result = solveall(82);
printf("result: %d bits = %d bytes\n",result,(result+7)/8);
return 0;
}
Z otrzymanych kodów można zbudować drzewo, albo można (chociaż nie wiem czy to praktyczne, nie próbowałem) przerobić algorytm tak by generował drzewo od razu.
0
Witam,
Mam pytanie dotyczące takiego zadanka:
Dane są następujące klucze wraz z prawdopodobieństwami ich wyszukiwania: A (.20); B (.24); C(.16); D(.28); E(.04); F(.08). Narysuj dla tych kluczy optymalne drzewo poszukiwań binarnych. Problem jest podobny do tego, który przytoczono wyżej. Chcąc to wygenerować optymalne drzewo na podstawie danych na kartce papieru, problem przestaje się nim być, chcąc to zapisać kodem c++ już to nie jest tak trywialne.
http://www.ujk.edu.pl/~stefanek/zfj/AiSD_Wyklad8_dzienne2013_progr_dyn2.pdf