Generujesz dane wejściowe dla algorytmów graficznych do testowania losowego?

Podczas testowania algorytmów powszechnym podejściem jest testowanie losowe: generuj znaczną liczbę danych wejściowych zgodnie z pewnym rozkładem (zwykle jednolitym), uruchom na nich algorytm i sprawdź poprawność. Nowoczesne ramy testowania mogą generować dane wejściowe automatycznie na podstawie podpisu algorytmów, z pewnymi ograniczeniami.

Jeśli dane wejściowe są liczbami, listami lub łańcuchami, generowanie takich danych wejściowych jest proste. Drzewa są twardsze, ale wciąż łatwe (przy użyciu stochastycznych gramatyk bezkontekstowych lub podobnych podejść).

Jak można generować losowe wykresy (efektywnie)? Zwykle losowe wybieranie wykresów równomiernie nie jest tym, czego chcesz: powinny być połączone, planarne, wolne od cyklu lub spełniać dowolną inną właściwość. Próbkowanie przy odrzuceniu wydaje się nieoptymalne ze względu na potencjalnie ogromny zestaw niepożądanych wykresów.

Jakie są przydatne dystrybucje do obejrzenia? Przydatne tutaj oznacza, że

• wykresy prawdopodobnie dobrze sprawdzą algorytm i
• mogą być generowane skutecznie i wydajnie.

Wiem, że istnieje wiele modeli losowych wykresów, dlatego doceniłbym wgląd w to, które z nich najlepiej nadają się do generowania wykresów.

Jeśli „jakiś algorytm” jest zbyt ogólny, użyj algorytmów wyszukiwania najkrótszej ścieżki jako konkretnej klasy testowanych algorytmów. Wykresy do testowania powinny być połączone i raczej gęste (z dużym prawdopodobieństwem lub przynajmniej w oczekiwaniu). Do testowania optymalnym rozwiązaniem byłoby utworzenie losowych wykresów wokół najkrótszej ścieżki, abyśmy znali pożądany wynik (bez konieczności stosowania innego algorytmu).

Losowe wykresy z topologią małego świata

Na wykresach z topologią małego świata węzły są wysoce zgrupowane, ale długość ścieżki między nimi jest niewielka. Taka topologia może bardzo utrudniać wyszukiwanie, ponieważ lokalne decyzje szybko rozprzestrzeniają się na cały świat. Innymi słowy, skróty mogą wprowadzać w błąd heurystykę. Ponadto wykazano, że wiele różnych problemów wyszukiwania ma małą topologię świata.

Watts i Strogatz [1] proponują model dla małych wykresów światowych . Najpierw zaczynamy od zwykłego wykresu. Zaburzenie wprowadza się do wykresu przez losowe przewinięcie każdej krawędzi z prawdopodobieństwem . Jeśli p = 0 , wykres jest całkowicie regularny i uporządkowany. Jeśli p = 1 , wykres jest całkowicie losowy i nieuporządkowany. Wartości 0 < p < 1 dają wykresy, które nie są ani całkowicie regularne, ani całkowicie nieuporządkowane. Wykresy nie mają niewielką topologię światowego p = 0 i P = 1 .$p$$p=0$$p=1$$0 < p < 1$$p=0$$p=1$

Watts i Strogatz zaczynają się od sieci pierścieniowej z węzłów i k najbliższych sąsiadów. Węzeł jest wybierany z sieci równomiernie losowo, a nawinięta krawędź jest ponownie do niego podłączana. Jeśli ponowna instalacja utworzy duplikat, pozostanie nietknięta. W przypadku dużych, rzadkich wykresów wymagają one n ≫ k ≫ ln ( n ) ≫ 1 , gdzie k ≫ ln ( n ) zapewnia, że ​​wykres pozostaje połączony.$n$$k$$n \gg k \gg \ln(n) \gg 1$$k \gg \ln(n)$

Model Watts i Strogatz jest dość popularny, ale ma pewne wady. Walsh [2] bada skutki strategii randomizacji i restartu na wykresach generowanych przy użyciu modelu. Jest też artykuł Virtanena [3], który obejmuje inne modele motywowane potrzebą realistycznego modelowania złożonych systemów.

Losowe proste wykresy płaskie

$n$$n$$g_n$$g_n$$1 \leq n \leq 9$$1,2,8,64,1023,32071,1823707,163947848$$20402420291$$g_n$

$$g_n \sim g \cdot n^{-7/2} \gamma^n n!,$$ $g$$\gamma$$g \approx 0.42609$$\gamma \approx 27.22687$

$\rightarrow$$\rightarrow$$\rightarrow$$\rightarrow$

$n$$x^n$$x$

Aby zapoznać się z lekkim wprowadzeniem, zobacz prezentację Fusy .

---

[1] DJ Watts i SH Strogatz. Dynamika zbiorowa sieci „małego świata”. Nature, 393: 440-442, 1998 .

[2] Toby Walsh. Szukaj w małym świecie. Materiały z 16. Międzynarodowej Wspólnej Konferencji na temat Sztucznej Inteligencji (IJCAI-99-Vol2), strony 1172-1177, 1999 .

[3] Satu Virtanen. Właściwości niejednorodnych modeli wykresów losowych. Raport z badań A77, Politechnika Helsińska, Laboratorium Informatyki Teoretycznej, 2003 .

[4] O. Giménez i M. Noy. Wyliczanie asymptotyczne i prawa granic grafów płaskich, arXiv matematyka.CO/0501269. Rozszerzone streszczenie pojawiło się w Discrete Mathematics and Theoretical Computer Science AD ​​(2005), 147-156 .

[5] E. Fusy. Kwadratowe i liniowe generowanie wykresów płaskich w czasie, matematyka dyskretna i informatyka teoretyczna AD (2005), 125–138 .

[6] P. Duchon, P. Flajolet, G. Louchard i G. Schaeffer. Próbnik Boltzmanna do losowego generowania struktur kombinatorycznych. Kombinatoryka, prawdopodobieństwo i obliczenia, 13 (4-5): 577-625, 2004 .