Jak mogę losowo wygenerować drzewa o ograniczonej wysokości?

9

W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości.

Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją.

1) Zaczynając od minimalnego drzewa opinającego (Prim'a lub Kruskala), dodaję nieistniejącą krawędź i to tworzy cykl, wykrywam ten cykl i usuwam jedną z krawędzi tego cyklu, która daje mi nowe drzewo opinające i kontynuuję to drzewo rozpinające poprzez dodanie nowej krawędzi ...

2) Załóżmy, że istnieje specjalny wierzchołek vcenter. Dla każdego wierzchołkav, długość ścieżki od v do Vcenter powinno być mniej niż δ, gdzie δ jest danym parametrem.

Czy istnieje lepszy (sprytny) sposób na zrobienie tego?

PS Zapomniałem podać inne ograniczenie (mój błąd): stopień wierzchołków również powinien być ograniczony.

Arman
źródło
Nie jestem pewien, czy dobrze to zrozumiałem. Czy w pierwszym kroku usuwasz krawędź losowo, czy też, aby wysokość drzewa była (ewentualnie) zmniejszona?
Sacha,
Losowo dodaję i usuwam krawędzie.
Arman,
Czy możesz zamiast tego spróbować losowo najkrótszej ścieżki łączącej drzewa? Upraszcza to
Jarosław Bułatow
czy masz jakieś koszty na krawędziach? szukasz drzewa opinającego o wysokościδi minimalny koszt? Jak napisał @pboothe, możesz używać BFS i to wszystko. Jedynym problemem jest to, że BFS zużywa zbyt dużo pamięci. Jeśli zależy Ci na kosztach, możesz wypróbować algorytm w wikipedii dla euklidesowych drzew minimalnych ( en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree ). Ma czas działania wynoszącyO(nlogn) z O(n)przestrzeni.
Marcos Villagra,
Więc twój problem ma trzy ograniczone wielkości: wysokość drzewa, stopień każdego wierzchołka i odległość od v_center, prawda? Samo ograniczenie stopnia stopnia sprawia, że ​​problem NP jest trudny, ale przypuszczam, że szukasz metody, która prawdopodobnie stworzy rozwiązanie szybko, a nie dokładny algorytm.
Jagadish

Odpowiedzi:

7

Kilka lat temu pracowałem nad drzewami rozpinającymi o ograniczonej głębokości, są naprawdę interesujące. Niektórzy z moich kolegów wymyślili algorytmy przekazywania wiadomości, które wykonały świetną robotę, ale nie mogę znaleźć żadnego z ich kodu. Napisaliśmy to w stylu fizyki tutaj: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Powiedzieli mi, że to również działa z granicami stopni, chociaż nie znalazło się to w gazecie.

Proponowane przez ciebie podejście, które nazwałbym Markov Chain Monte Carlo, często stanowi konkurencję dla podejścia polegającego na przekazywaniu wiadomości. Jeśli chcesz pobierać próbki w przybliżeniu równomiernie losowo z zestawu drzew rozpinających o ograniczonym stopniu i ograniczonej głębokości na danym wykresie, sugeruję zmianę podejścia do korzystania z „miękkich” granic. Tj. Zamiast odrzucać zamianę krawędzi, która powoduje, że drzewo narusza ograniczenie głębokości, zaakceptuj je, ale z mniejszym prawdopodobieństwem niż zamiana, która nie narusza ograniczenia. Jeśli masz parametr kontrolujący, o ile niższe jest to prawdopodobieństwo, możesz sprawić, że ograniczenie naruszające konfiguracje będzie coraz mniej prawdopodobne, dopóki nie dojdziesz do wykonalnego rozwiązania, które jest prawie równomiernie losowe.

Najważniejsze pytanie brzmi: jak długo trzeba uruchomić łańcuch. Ponieważ drzewo opinające o stopniu co najwyżej 2 jest ścieżką hamiltonowską, należy się spodziewać, że każdy rodzaj ogólny będzie miał wykładniczy rozmiar wykresu. Ale może wykresy, które Cię interesują, są w jakiś sposób wyjątkowe.

Abraham Flaxman
źródło
2
Więcej szczegółów plus film: zdrowe algorytmy.wordpress.com/2010/12/23/...
Abraham Flaxman
3

Jeśli Twoim problemem jest równomierne próbkowanie drzewa opinającego z zestawu S, gdzie S jest zbiorem wszystkich łączących drzew wysokości h, dla niektórych danych wejściowych h, wtedy twoja strategia działa (np. próbkuj losowe drzewo opinające i sprawdź, czy jego wysokość jest co najwyżej h).

Nie jestem jednak pewien, czy opisany algorytm wygeneruje losowe drzewo opinające. Zamiast tego poleciłbym spojrzenie na standardowe algorytmy. Istnieją dwa algorytmy: algorytm Wilsona i algorytm Aldousa-Brodera. Możesz zajrzeć tutaj . Istnieje nowszy algorytm (przybliżenie) , ale jest on dość skomplikowany.

Ponadto może istnieć sposób na bezpośrednie wygenerowanie tego drzewa opinającego z ograniczoną wysokością. Ale nigdy nie słyszałem o takich algorytmach.

Danu
źródło
1

Skorzystaj z szerokiego wyszukiwania! Wykonaj BFS z każdego wierzchołka na wykresie, wybierz drzewo wynikowe o najmniejszej wysokości. BFS zawsze znajduje ścieżkę od katalogu głównego do każdego innego wierzchołka z najmniejszą liczbą przeskoków.

Peter Boothe
źródło
Masz zdecydowanie rację. Zaczęliśmy robić z BFS, ale to nie działało z powodu ograniczenia stopnia na wierzchołkach. Zapomniałem wspomnieć o tym ograniczeniu (mój błąd): stopień wierzchołków w wygenerowanym drzewie powinien być również ograniczony. Twoja odpowiedź jest poprawna w przypadku bieżącego pytania, ale myślę, że powinienem edytować moje pytanie.
Arman,
Zatem twoim problemem jest prawie na pewno NPC poprzez redukcję z drzewa ograniczającego stopień - en.wikipedia.org/wiki/Degree-constrained_spanning_tree
Peter Boothe