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 . Dla każdego wierzchołka, długość ścieżki od do 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.
Odpowiedzi:
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.
źródło
Jeśli Twoim problemem jest równomierne próbkowanie drzewa opinającego z zestawuS , 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.
źródło
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.
źródło