Où trouver des graphiques pour tester mes algorithmes de recherche?

29

J'implémente un ensemble d'algorithmes de recherche de chemin tels que Dijkstra, Depth First, etc.

Au début, j'ai utilisé quelques graphiques faits maison, mais maintenant j'aimerais relever le défi un peu plus et donc je cherche soit

  1. graphiques utilisés dans les repères;
  2. des graphiques de villes du monde réel (ou un moyen de télécharger ce type d'informations sur google maps, ou tout autre type de source, si possible).

J'aimerais que ces sources aient ou me permettent de créer facilement des frontières afin que je puisse essayer mes algorithmes pour des ensembles de graphiques de différentes tailles, si possible.

Je recherche des solutions simples, car je préférerais ne pas être détourné de l'objectif principal (comparer un ensemble d'algorithmes différents), donc j'aurais besoin d'un moyen rapide pour convertir ces données graphiques dans mon propre format (en gros, un ensemble de (x, y)points connectés ).

Pour être plus concret, ce que je recherche, ce sont des graphes cycliques 2D. Si ces graphiques reflètent les rues des villes du monde réel (en tenant compte des rues à sens unique, des rues à double sens, etc., mieux encore!).

algorithms graphs data-sets benchmarking Elysium dévoré
la source
1
Il y a l'archive graphique ouverte: graph-archive.org/doku.php?id=start et un article expliquant le projet: arxiv.org/abs/1109.1465
Joe
1
@Raphael Les graphiques aléatoires ne constituent souvent pas des cas de test représentatifs pour les graphiques du monde réel: ceux-ci ont tendance à être des réseaux complexes .
Gilles 'SO- arrête d'être méchant'
2
@joe / Pratik - pourquoi ne pas poster comme réponse?
Ran G.
3
@A sonné. Une réponse ne doit pas être simplement un lien .
Gilles 'SO- arrête d'être méchant'
1
@ Gilles, je ne voulais pas publier les commentaires tels quels, mais plutôt (en utilisant votre lien :) "Un lien vers une solution potentielle est toujours le bienvenu, mais veuillez ajouter du contexte autour du lien". Actuellement, il n'y a pas d'option pour commenter ces liens et voter sur eux. Je suis sûr que certains de ces liens sont très utiles et répondent à la question posée, mais personne ne peut voter pour les bons (de manière significative).
Ran G.

Réponses:

17

Recherchez sur les sites Web.

SNAP est un ensemble de réseaux hébergés par un prof de Stanford. Plusieurs exemples du monde réel dans une variété de paramètres.

Net Wiki est hébergé par un professeur de mathématiques UNC, encore une fois plusieurs liens vers des ensembles de données réels ainsi que des liens vers d'autres ressources de données.

OpenFlights Dispose d'aéroports et de routes entre eux (réseau spatial).

Réseau de routes édité par les utilisateurs d' OpenStreetMap pour la plupart du monde. Vous pouvez également télécharger des sous-ensembles (par exemple, uniquement des routes dans l'Ohio ou simplement des autoroutes en Amérique du Nord). Le format est en xml, pas super facile à analyser, mais c'est un réseau cyclique réel ~ 2d.

Il existe également plusieurs autres ressources, il vous suffira de creuser un peu.

Entaille
la source
2

J'ai visité tous les liens fournis par Nick. Ils sont vraiment magnifiques et j'ai ajouté tous ces sites à mes favoris. J'espère que le lien suivant spécialement conçu pour tester les algorithmes de recherche répond également à vos besoins:

Repères de repérage par Nathan Sturtevant. Il contient diverses cartes de différents jeux vidéo et également d'autres benchmakrs artificiels tels que des labyrinthes et des graphiques avec des obstacles aléatoires.

Si vous êtes, en particulier, intéressé par ce type de domaines, alors vous voudrez peut-être participer au concours de planification de chemin basé sur une grille l'année prochaine (les résultats de la première édition du concours sont disponibles au GPPC 2012 )

À votre santé,

Carlos Linares López
la source