¿Dónde obtener gráficos para probar mis algoritmos de búsqueda?

29

Estoy implementando un conjunto de algoritmos de búsqueda de rutas como Dijkstra, Depth First, etc.

Al principio usé un par de gráficos hechos por mí mismo, pero ahora me gustaría llevar el desafío un poco más allá y, por lo tanto, estoy buscando

  1. gráficos utilizados en puntos de referencia;
  2. gráficos de ciudades del mundo real (o una forma de descargar ese tipo de información de Google Maps, o cualquier otro tipo de fuente, si es posible).

Me gustaría que esas fuentes tengan o me permitan crear fronteras fácilmente para que pueda probar mis algoritmos para conjuntos de gráficos de diferentes tamaños, si es posible.

Estoy buscando soluciones simples, ya que preferiría no desviarme del objetivo principal (comparar un conjunto de algoritmos diferentes), por lo que necesitaría una forma rápida de convertir los datos del gráfico en mi propio formato (básicamente, un conjunto de (x, y)puntos conectados ).

Para ser más concreto, lo que estoy buscando son gráficos cíclicos en 2D. Si esos gráficos reflejan las calles de la ciudad del mundo real (teniendo en cuenta las calles de un solo sentido, las calles de dos sentidos, etc., ¡mejor aún!).

elysium devorado
fuente
1
Existe el archivo gráfico abierto: graph-archive.org/doku.php?id=start y un documento que explica el proyecto: arxiv.org/abs/1109.1465
Joe
1
@Raphael Los gráficos aleatorios a menudo no son casos de prueba representativos para gráficos del mundo real: estos tienden a ser redes complejas .
Gilles 'SO- deja de ser malvado'
2
@joe / Pratik: ¿por qué no publicar como respuesta?
Ran G.
3
@Sonó. Una respuesta no debe ser solo un enlace .
Gilles 'SO- deja de ser malvado'
1
@Gilles, no quise publicar los comentarios tal como están, sino más bien (usando su enlace :) "Siempre es bienvenido un enlace a una solución potencial, pero agregue contexto alrededor del enlace". Actualmente, no hay opción para comentar esos enlaces y votarlos. Estoy seguro de que algunos de esos enlaces son muy útiles y responden la pregunta formulada, pero nadie puede votar los buenos (de manera significativa).
Ran G.

Respuestas:

17

Busca entre las webs.

SNAP es un conjunto de redes alojadas por un profesor en Stanford. Varios ejemplos del mundo real en una variedad de entornos.

Net Wiki está alojado por un profesor de matemáticas de UNC, nuevamente varios enlaces a conjuntos de datos reales, así como enlaces a otros recursos de datos.

OpenFlights tiene aeropuertos y rutas entre ellos (red espacial).

El usuario de OpenStreetMap editó la red de carreteras para la mayor parte del mundo. También puede descargar subconjuntos (por ejemplo, solo carreteras en Ohio, o solo carreteras en América del Norte). El formato está en xml, no es muy fácil de analizar, pero es una red cíclica en el mundo real ~ 2d.

También hay varios otros recursos, solo tendrás que cavar un poco.

Mella
fuente
2

He estado visitando todos los enlaces proporcionados por Nick. Realmente se ven maravillosos y he agregado todos esos sitios a mis marcadores. Espero que el siguiente enlace especialmente diseñado para probar algoritmos de búsqueda se adapte también a sus necesidades:

Puntos de referencia de Pathfinding por Nathan Sturtevant. Contiene varios mapas de diferentes videojuegos y también otros benchmakrs artificiales como laberintos y gráficos con obstáculos aleatorios.

Si, en particular, está interesado en este tipo de dominios, es posible que desee participar en la Competencia de planificación de rutas basada en la red el próximo año (los resultados de la primera edición de la competencia están disponibles en GPPC 2012 )

Aclamaciones,

Carlos Linares López
fuente