[Algorytm] Usuwanie dubletów z drzewa

malosolny
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 23 lut 2012, o 12:26
Płeć: Mężczyzna
Lokalizacja: Białystok
Podziękował: 1 raz

[Algorytm] Usuwanie dubletów z drzewa

Post autor: malosolny »

Witam,

dostałem do rozpatrzenia następujący problem dot. drzew binarnych.

Moim zadaniem jest, po otrzymaniu danego drzewa, usunąć z niego
powtarzające się poddrzewa tak, aby każde z nich miało tylko jednego reprezentanta.

Można to oczywiście napisać ze złożonością wykładniczą bez większego wysiłku,
porównując na siłę każde 2 poddrzewa, patrząc najpierw, które z nich są izomorficzne.

Wiadomo jednak, że taki sposób będzie baaaardzo daleki od optymalnego.

Czy ktoś ma pomysł, w jaki sposób zoptymalizować algorytm tak, aby miał sensowną złożoność?
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytm] Usuwanie dubletów z drzewa

Post autor: adambak »

wykładniczą ze względu na co? jeśli ze względu na wysokość drzewa to chyba jeszcze nie ma tragedii.. ciężko mi sobie wyobrazić aż takiego bruta jak wykładniczo ze względu na liczbę węzłów.. z resztą często bruty są trudniejsze niż by się mogło wydawać..

póki co jedyne co mi przychodzi do głowy to kwadratówka.. przechodząc drzewo preorder (lewo-prawo) w poszukiwaniu dubletów sprawdzamy czy poddrzewo o korzeniu w aktualnie odwiedzanym węźle ma swój oryginał (który jeśli istnieje, to jest na lewo od danego poddrzewa).. wobec tego odpalamy poszukiwanie oryginału od korzenia (tego prawdziwego) drzewa też w porządku preorder.. rekurencję ucinamy jeśli dojdziemy do węzła dla którego rozpoczęliśmy szukanie, bądź znaleźliśmy oryginał.. można dodać jedno usprawnienie - pamiętać w każdym węźle rozmiar drzewa o korzeniu w danym węźle, aby nie odpalać porównywania drzew w tej rekurencji dla drzew istotnie się różniących - wielkością..

wydaje mi się, że nie jest to aż tak fatalne.. napewno da się to zrobić lepiej i sam jestem ciekaw jak, narazie nie wymyśliłem niczego lepszego..

nie najgorszym jest też trop taki, że przy wypisywaniu wierzchołków np postorder widać powtarzające się segmenty.. nie wiem jednak czy to gdzieś zaprowadzi..-- 1 mar 2012, o 14:09 --zaproponowany przeze mnie algorytm jest chyba jednak niestety sześcienny(z małą stałą)..
wobec tego myślę, że kwadratowy będzie już przyzwoity (mimo, że liniówka jest możliwa, ale korzysta z nieelementarnych metod)..
ODPOWIEDZ