Где взять графики для проверки моих алгоритмов поиска?

29

Я реализую набор алгоритмов поиска пути, таких как Dijkstra, Depth First и т. Д.

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

  1. графики, используемые в тестах;
  2. графики городов реального мира (или способ загрузки информации такого рода с карт Google или любого другого источника, если это возможно).

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

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

Чтобы быть более конкретным, я ищу двумерные циклические графы. Если эти графики отражают городские улицы реального мира (принимая во внимание улицы с односторонним движением, улицы с двусторонним движением и т. Д., Еще лучше!).

algorithms graphs data-sets benchmarking пожрал элизиум
источник
1
Есть открытый архив графиков: graph-archive.org/doku.php?id=start и документ с объяснением проекта: arxiv.org/abs/1109.1465
Джо,
1
@Raphael Случайные графы часто не создают репрезентативных тестовых случаев для графов реального мира: это, как правило, сложные сети .
Жиль "ТАК ... перестать быть злым"
2
@joe / Pratik - почему бы не опубликовать в ответ?
Ран Г.
3
@RanG. Ответ не должен быть просто ссылкой .
Жиль "ТАК - перестань быть злым"
1
@ Жиль, я не имел в виду публиковать комментарии как есть, а скорее (используя вашу ссылку :) «Ссылка на потенциальное решение всегда приветствуется, но, пожалуйста, добавьте контекст вокруг ссылки». В настоящее время нет возможности комментировать эти ссылки и голосовать за них. Я уверен, что некоторые из этих ссылок очень полезны и отвечают на заданный вопрос, но никто не может высказать хорошие (значимым образом).
Ран Г.

Ответы:

17

Поиск в сети.

SNAP - это сеть сетей, организованная профессором в Стэнфорде. Несколько примеров из реальной жизни в различных условиях.

Net Wiki ведет UNC математика проф., Опять же несколько ссылок на реальные наборы данных, а также ссылки на другие ресурсы данных.

OpenFlights Имеет аэропорты и маршруты между ними (пространственная сеть).

OpenStreetMap редактирует сеть автомобильных дорог для большинства стран мира. Вы также можете скачать подмножества (например, только дороги в Огайо или просто шоссе в Северной Америке). Формат в xml, не очень легко разобрать, но это реальный мир ~ 2d циклическая сеть.

Также есть несколько других ресурсов, вам просто нужно немного покопаться.

Ник
источник
2

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

Ориентиры поиска пути Натана Стертеванта. Он содержит различные карты из разных видеоигр, а также другие искусственные тесты, такие как лабиринты и графики со случайными препятствиями.

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

Ура,

Карлос Линарес Лопес
источник