Cartes/graphiques aléatoires et OSM

Question

Je me demandais simplement si vous aviez des suggestions ici. J'ai besoin de beaucoup d'exemples de cartes/graphiques pour tester ma solution de recherche de chemin le plus court (on m'a dit que je devrais en avoir plus de 100). Mon code est censé fonctionner dans un simulateur, qui utilise des cartes OpenStreetMap de paramètres urbains, en limitant le nombre total de jonctions à quelques milliers. le problème est qu'il n'y a que deux ou trois cartes fournies avec le simulateur. La façon dont je le vois, j'ai quelques choix ici:

1. Écrivez mon propre générateur de graphe aléatoire. Peut-être beaucoup de travail (pensez-vous? - Je ne l'ai jamais fait auparavant) et réinventer la roue.
2. Utiliser une solution prête à l'emploi. Je n'en connais pas qui pourraient me générer des graphes de type carte (bon, au moins je ne l'ai pas trouvé dans JUNG :-))
3. De manière automatisée, récupérez-les depuis OSM. Je n'ai pas vraiment l'intention de moi-même aller chercher un 100+ cartes urbaines qui satisferaient l'exigence de 15000 nœuds. Je ne pense pas que ce serait facile à automatiser non plus.

Je suppose que 3 serait difficile à faire. Des conseils sur une solution prête à l'emploi? ou des commentaires sur l'écriture de mon propre? Je ne suis pas un programmeur expérimenté par n'importe quelle mesure, mais donné quelques jours.

Answer 1

La première pensée:

Vous avez un problème connu et vous avez besoin de tester sa solution. Générez beaucoup de données de test, trouvez des solutions correctes avec un algorithme vérifié, puis exécutez votre algorithme par rapport à l'ensemble de données généré et comparez les résultats. (Ou tout simplement télécharger l'application vérifié algorithme de Dijkstra, je crois que la mise en œuvre de cet algorithme est votre tâche)

La seconde pensée:

ensemble de données aléatoires générées ne sont pas la meilleure façon de tester des algorithmes. Vous devez penser aux cas où votre algorithme peut échouer et créer des tests correspondants. Par exemple, graphe avec 1 noeud, graphe avec cycles, graphe linéaire, c'est-à-dire N1 --- N2 --- N3 -...- Nn, graphe complet avec nombre maximum de noeuds. Je pense que si vous créez ces 4 tests et 2-3 petits tests aléatoires, il suffira de vous assurer que votre algorithme est correctement implémenté.