Générer des entrées pour les algorithmes de graphes de test aléatoire

Lors du test d'algorithmes, une approche courante est le test aléatoire: générer un nombre significatif d'entrées selon une distribution (généralement uniforme), exécuter l'algorithme sur ces derniers et vérifier l'exactitude. Les cadres de test modernes peuvent générer des entrées automatiquement compte tenu de la signature des algorithmes, avec certaines restrictions.

Si les entrées sont des nombres, des listes ou des chaînes, générer de telles entrées de manière simple. Les arbres sont plus difficiles, mais toujours faciles (en utilisant des grammaires stochastiques sans contexte ou des approches similaires).

Comment pouvez-vous générer des graphiques aléatoires (efficacement)? Habituellement, choisir des graphiques de manière uniforme et aléatoire n'est pas ce que vous voulez: ils doivent être connectés, planaires ou sans cycle, ou remplir toute autre propriété. L'échantillonnage de rejet semble sous-optimal, en raison de l'ensemble potentiellement énorme de graphiques indésirables.

Quelles sont les distributions utiles à regarder? Utile ici signifie que

les graphiques sont susceptibles de bien tester l'algorithme à portée de main et
ils peuvent être générés de manière efficace et efficiente.

Je sais qu'il existe de nombreux modèles de graphiques aléatoires, donc j'apprécierais un aperçu des meilleurs pour la génération de graphiques à cet égard.

Si "un algorithme" est trop général, veuillez utiliser des algorithmes de recherche de chemin le plus court comme classe concrète d'algorithmes testés. Les graphiques pour les tests doivent être connectés et plutôt denses (avec une probabilité élevée, ou du moins dans l'attente). Pour les tests, la solution optimale serait de créer des graphiques aléatoires autour d'un chemin le plus court afin que nous connaissions le résultat souhaité (sans avoir à utiliser un autre algorithme).

algorithms graphs randomness software-testing Raphael
la source

Cette question a été déclenchée par celle-là .

Raphael

Réponses:

Graphes aléatoires avec petite topologie mondiale

Dans les graphiques à petite topologie mondiale , les nœuds sont fortement regroupés mais la longueur de chemin entre eux est petite. Une topologie comme celle-ci peut rendre les problèmes de recherche très difficiles, car les décisions locales se propagent rapidement à l'échelle mondiale. En d'autres termes, les raccourcis peuvent induire en erreur l'heuristique. De plus, il a été démontré que de nombreux problèmes de recherche différents ont une topologie mondiale restreinte.

$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)$

Le modèle de Watts et Strogatz est quelque peu populaire, mais présente certains inconvénients. Walsh [2] étudie les effets des stratégies de randomisation et de redémarrage dans les graphiques générés à l'aide du modèle. Il existe également un article de Virtanen [3], qui couvre d'autres modèles motivés par le besoin d'une modélisation réaliste de systèmes complexes.

Graphiques planaires aléatoires simples

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