Generieren von Eingaben für die Zufallsprüfung von Diagrammalgorithmen?

Ein gängiger Ansatz beim Testen von Algorithmen ist das Testen nach dem Zufallsprinzip: Generieren Sie eine signifikante Anzahl von Eingaben entsprechend einer (normalerweise einheitlichen) Verteilung, führen Sie den Algorithmus auf diesen aus und überprüfen Sie die Richtigkeit. Moderne Test-Frameworks können mit einigen Einschränkungen Eingaben anhand der Algorithmus-Signatur automatisch generieren.

Wenn es sich bei den Eingaben um Zahlen, Listen oder Zeichenfolgen handelt, werden solche Eingaben direkt generiert. Bäume sind schwieriger, aber dennoch einfach (mit stochastischen kontextfreien Grammatiken oder ähnlichen Ansätzen).

Wie können Sie Zufallsgraphen (effizient) erzeugen? In der Regel ist es nicht erwünscht, Diagramme gleichmäßig nach dem Zufallsprinzip auszuwählen: Sie sollten verbunden, planar oder zyklenfrei sein oder eine andere Eigenschaft erfüllen. Die Rückweisungsabtastung erscheint aufgrund der potenziell großen Anzahl unerwünschter Diagramme suboptimal.

Was sind nützliche Distributionen? Nützlich bedeutet hier, dass

• Die Grafiken werden den vorliegenden Algorithmus wahrscheinlich gut testen und
• Sie können effektiv und effizient erzeugt werden.

Ich weiß, dass es viele Modelle für Zufallsgraphen gibt, daher würde ich mich über einen Einblick in die Modelle freuen, die sich in dieser Hinsicht am besten für die Erstellung von Graphen eignen.

Wenn "ein Algorithmus" zu allgemein ist, verwenden Sie bitte Algorithmen für die Suche nach kürzesten Wegen als konkrete Klasse der zu testenden Algorithmen. Diagramme zum Testen sollten verbunden und ziemlich dicht sein (mit hoher Wahrscheinlichkeit oder zumindest in Erwartung). Für die Prüfung wäre die optimale Lösung sein Zufallsgraphen um einen kürzesten Weg zu schaffen , damit wir wissen , um das gewünschte Ergebnis (ohne einen anderen Algorithmus verwenden zu müssen).

Zufällige Diagramme mit kleiner Welttopologie

In Diagrammen mit kleiner Welttopologie sind Knoten stark gruppiert, die Pfadlänge zwischen ihnen ist jedoch gering. Eine solche Topologie kann Suchprobleme sehr erschweren, da sich lokale Entscheidungen schnell global verbreiten. Mit anderen Worten, Verknüpfungen können Heuristiken in die Irre führen. Weiterhin hat sich gezeigt, dass viele verschiedene Suchprobleme eine kleine Welttopologie haben.

$p$$p=0$$p=1$$0 < p < 1$$p=0$$p=1$

$n$$k$$n \gg k \gg \ln(n) \gg 1$$k \gg \ln(n)$

Das Modell von Watts and Strogatz ist etwas populär, hat aber gewisse Nachteile. Walsh [2] untersucht die Auswirkungen von Randomisierungs- und Neustartstrategien in anhand des Modells erstellten Diagrammen. Es gibt auch einen Artikel von Virtanen [3], der sich mit anderen Modellen befasst, die durch die Notwendigkeit einer realistischen Modellierung komplexer Systeme motiviert sind.

Zufällige einfache ebene Graphen

Das Erzeugen von zufälligen einfachen planaren Graphen auf Ecken, die gleichmäßig zufällig sind, kann effizient durchgeführt werden. Die Anzahl der planaren Graphen mit n . Da die Zahlen zu kompliziert sind, ist nicht zu erwarten, dass man eine geschlossene Formel für sie findet. Giménez und Noy [4] geben eine genaue asymptotische Abschätzung für das Wachstum von g n : $n$$n$$g_n$$g_n$$1 \leq n \leq 9$$1,2,8,64,1023,32071,1823707,163947848$$20402420291$$g_n$

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

$n$$x^n$$x$

Eine kurze Einführung finden Sie in einer Präsentation von Fusy .

[1] DJ Watts und SH Strogatz. Kollektive Dynamik von Netzwerken der "kleinen Welt". Nature, 393: 440 & ndash; 442, 1998 .

[2] Toby Walsh. Suche in einer kleinen Welt. Tagungsband der 16. Internationalen Konferenz für künstliche Intelligenz (IJCAI-99-Vol2), Seiten 1172-1177, 1999 .

[3] Satu Virtanen. Eigenschaften von ungleichmäßigen Zufallsgraphenmodellen. Forschungsbericht A77, Technische Universität Helsinki, Labor für Theoretische Informatik, 2003 .

[4] O. Giménez und M. Noy. Asymptotische Aufzählung und Grenzgesetze planarer Graphen, arXiv math.CO/0501269. Eine erweiterte Zusammenfassung ist in Discrete Mathematics and Theoretical Computer Science AD ​​(2005), 147-156, erschienen .

[5] E. Fusy. Quadratische und lineare Zeitgenerierung planarer Graphen, Diskrete Mathematik und Theoretische Informatik AD (2005), 125-138 .

[6] P. Duchon, P. Flajolet, G. Louchard und G. Schaeffer. Boltzmann-Sampler zur zufälligen Erzeugung kombinatorischer Strukturen. Combinatorics, Probability and Computing, 13 (4-5): 577-625, 2004 .