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

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 $v_{center}$. Dla każdego wierzchołka$v$, długość ścieżki od $v$ do $V_{center}$ powinno być mniej niż $\delta$, gdzie $\delta$ 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.

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.

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.

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.