Случайные карты/графики и OSM

Question

просто интересно, есть ли у вас какие-либо предложения здесь. Мне нужно много образцов карт/графиков для проверки моего кратчайшего пути поиска (мне сказали, что у меня должно быть> 100 из них). Мой код должен работать в симуляторе, который использует карты OpenStreetMap городских условий, ограничивая общее количество соединений несколькими тысячами. проблема в том, что в симуляторе имеется только две или три карты. Как я это вижу, у меня есть несколько вариантов:

1. Напишите мой собственный генератор случайных графов. Возможно, много работы (как вы думаете? - Я никогда не делал этого раньше) и изобретать колесо.
2. Используйте готовое решение. Я не знаю, что могло бы генерировать мне графические карты (ну, по крайней мере, я не нашел его в JUNG :-))
3. В некоторых автоматизированных способах захватить их из OSM. Я действительно не намерен сам идти и выбирать более 100 городских карт, которые удовлетворяли бы требованиям < 15000 узлов. Я не думаю, что это было бы легко автоматизировать.

Я бы предположил, что 3 будет непросто сделать. Любые советы по некоторым готовым решениям? или комментарии о написании моих собственных? Я не опытный программист в какой-то мере, но на несколько дней.

Answer 1

Первая мысль:

У вас есть известная проблема, и вы должны проверить его решение. Создайте множество тестовых данных, найдите правильные решения с проверенным алгоритмом, затем запустите свой алгоритм против сгенерированного набора данных и сравните результаты. (Или просто загрузить проверить реализацию алгоритма Дейкстров, я считаю, что реализация этого алгоритма ваша задача)

Вторая мысль:

Случайного сгенерированным набор данных не лучший способ проверить алгоритмы. Вам нужно подумать о случаях, когда ваш алгоритм может выйти из строя и создать соответствующие тесты. Например, график с 1 узлом, граф с циклами, линейный граф, т. Е. N1 --- N2 --- N3 -...- Nn, полный граф с максимальным числом узлов. Я думаю, что если вы создадите эти 4 теста и 2-3 небольших случайных теста, этого будет достаточно, чтобы убедиться, что ваш алгоритм реализован правильно.