Witam wszystkich.
Dostałem na zajęciach zadanie : mam do stworzenia algorytm który na podstawie kluczy z prawdopodobieństwem ich wyszukiwania utworzy optymalne drzewo poszukiwań binarnych. Mam do tego wykorzystać programowanie dynamiczne. Prosiłbym o nakierowanie mnie na materiały,literaturę gdzie mógłbym znaleźć informację jak podejść do tego tematu ( szukałem oczywiście w google ale jest to dla mnie w dalszym ciągu nie zrozumiałe dlatego też mile widziane materiały w j. Polskim )
Z góry dziękuje za pomoc.
0
0
Po polsku nie szukałem, ale oprócz artykułu na Wiki: http://en.wikipedia.org/wiki/Optimal_binary_search_tree możesz też przejrzeć kod: http://encode.ru/threads/378-Ordered-bitcodes-experiments?p=7527&viewfull=1#post7527
Podlinkowany program liczy coś na wzór kodów Huffmana, ale zachowujących kolejność leksykograficzną. A więc kody minimalizują długość całkowitą ciągu. Biorąc pod uwagę to, że jeden bit jest równoznaczny z jednym porównaniem, to minimalizacja ilości bitów jest równoznaczna z minimalizacją ilości porównań, a co za tym idzie - kody bitowe definiują optymalne drzewo poszukiwań binarnych.