Генерация входных данных для алгоритмов случайного тестирования графа?

При тестировании алгоритмов общим подходом является случайное тестирование: генерировать значительное количество входных данных в соответствии с некоторым распределением (обычно равномерным), запускать алгоритм на них и проверять правильность. Современные инфраструктуры тестирования могут генерировать входные данные автоматически с учетом сигнатуры алгоритмов с некоторыми ограничениями.

Если входные данные являются числами, списками или строками, генерирование таких входных данных происходит напрямую. Деревья сложнее, но все же просты (используя стохастические контекстно-свободные грамматики или аналогичные подходы).

Как вы можете генерировать случайные графики (эффективно)? Как правило, выбор графов равномерно в случайном порядке - это не то, что вам нужно: они должны быть связаны, либо плоскими, либо свободными от циклов, либо выполнять любое другое свойство. Отклонение выборки кажется неоптимальным из-за потенциально огромного набора нежелательных графиков.

Какие полезные дистрибутивы посмотреть? Полезное здесь означает, что

• графики, скорее всего, хорошо протестируют алгоритм и
• они могут быть созданы эффективно и действенно.

Я знаю, что существует множество моделей для случайных графов, поэтому я был бы признателен за понимание того, какие из них лучше всего подходят для генерации графов в этом отношении.

Если «некоторый алгоритм» является слишком общим, пожалуйста, используйте алгоритмы поиска кратчайшего пути в качестве конкретного класса тестируемых алгоритмов. Графики для тестирования должны быть связными и достаточно плотными (с высокой вероятностью или, по крайней мере, в ожидании). Для тестирования оптимальным решением было бы создание случайных графов по кратчайшему пути, чтобы мы знали желаемый результат (без использования другого алгоритма).

Случайные графы с топологией малого мира

В графах с небольшой топологией мира узлы сильно кластеризованы, но длина пути между ними мала. Подобная топология может очень затруднить поиск, поскольку локальные решения быстро распространяются по всему миру. Другими словами, ярлыки могут ввести в заблуждение эвристику. Кроме того, было показано, что многие различные проблемы поиска имеют небольшую мировую топологию.

Уоттс и Строгатц [1] предлагают модель для небольших графов мира . Сначала мы начнем с регулярного графа. Беспорядок вводится в график путем случайного изменения каждого ребра с вероятностью . Если p = 0 , график является полностью регулярным и упорядоченным. Если p = 1 , график является полностью случайным и неупорядоченным. Значения 0 < p < 1 дают графики, которые не являются ни полностью регулярными, ни полностью неупорядоченными. Графы не имеют небольшой мировой топологии для p = 0 и p = 1 .$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)$

Модель Watts and Strogatz несколько популярна, но имеет определенные недостатки. Уолш [2] исследует влияние стратегий рандомизации и перезапуска на графы, созданные с использованием модели. Есть также статья Виртанена [3], в которой рассматриваются другие модели, мотивированные необходимостью реалистичного моделирования сложных систем.

Случайные простые плоские графы

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

Для облегченного введения, см. Презентацию Fusy .

---

[1] DJ Watts и SH Strogatz. Коллективная динамика сетей «малого мира». Nature, 393: 440-442, 1998 .

[2] Тоби Уолш. Поиск в маленьком мире. Материалы 16-й Международной объединенной конференции по искусственному интеллекту (IJCAI-99-Vol2), страницы 1172-1177, 1999 .

[3] Сату Виртанен. Свойства моделей неоднородных случайных графов. Отчет об исследовании A77, Хельсинкский технологический университет, Лаборатория теоретической информатики, 2003 .

[4] О. Хименес и М. Ной. Асимптотическое перечисление и предельные законы плоских графов, arXiv math.CO/0501269. Расширенная аннотация появилась в дискретной математике и теоретической информатике AD (2005), 147-156 .

[5] Э. Фуси. Квадратичная и линейная генерация времени плоских графов, Дискретная математика и теоретическая информатика AD (2005), 125-138 .

[6] П. Дюшон, П. Флажолет, Г. Лушар и Г. Шеффер. Пробоотборник Больцмана для случайной генерации комбинаторных структур. Комбинаторика, Вероятность и вычисления, 13 (4-5): 577-625, 2004 .