Woher bekomme ich Diagramme, mit denen ich meine Suchalgorithmen testen kann?

29

Ich implementiere eine Reihe von Pfadsuchalgorithmen wie Dijkstra's, Depth First, etc.

Anfangs habe ich ein paar selbst erstellte Grafiken verwendet, aber jetzt möchte ich die Herausforderung ein bisschen weiter gehen und suche daher auch nach einer

  1. Diagramme für Benchmarks;
  2. Diagramme von Städten der realen Welt (oder eine Möglichkeit, diese Art von Informationen von Google Maps oder einer anderen Art von Quelle herunterzuladen, falls möglich).

Ich möchte, dass diese Quellen entweder Grenzen haben oder es mir ermöglichen, diese einfach zu erstellen, so dass ich meine Algorithmen nach Möglichkeit für unterschiedlich große Sätze von Diagrammen ausprobieren kann.

Ich suche nach einfachen Lösungen, da ich es vorziehen würde, nicht vom Hauptziel abgelenkt zu werden (vergleiche eine Reihe verschiedener Algorithmen), und brauche daher eine schnelle Möglichkeit, diese Diagrammdaten in mein eigenes Format zu konvertieren (im Grunde genommen a Satz verbundener (x, y)Punkte).

Um genauer zu sein, suche ich nach zyklischen 2D-Diagrammen. Wenn diese Grafiken reale Stadtstraßen widerspiegeln (unter Berücksichtigung von Einbahnstraßen, Einbahnstraßen usw., noch besser!).

algorithms graphs data-sets benchmarking verschlungenes Elysium
quelle
1
Es gibt das Open-Graph-Archiv: graph-archive.org/doku.php?id=start und ein Papier, das das Projekt erklärt: arxiv.org/abs/1109.1465
Joe
1
@Raphael Zufallsgraphen sind oft keine repräsentativen Testfälle für reale Graphen: Diese sind in der Regel komplexe Netzwerke .
Gilles 'SO- hör auf böse zu sein'
2
@joe / Pratik - warum nicht als Antwort posten?
Ran G.
3
@RanG. Eine Antwort sollte nicht nur ein Link sein .
Gilles 'SO- hör auf böse zu sein'
1
@ Gilles, ich wollte die Kommentare nicht so veröffentlichen, wie sie sind, sondern (über Ihren Link :) "Ein Link zu einer möglichen Lösung ist immer willkommen, aber fügen Sie bitte einen Kontext um den Link hinzu." Derzeit gibt es keine Möglichkeit, diese Links zu kommentieren und darüber abzustimmen. Ich bin mir sicher, dass einige dieser Links sehr nützlich sind und die gestellte Frage beantworten, aber niemand kann die guten (auf sinnvolle Weise) positiv bewerten.
Ran G.

Antworten:

17

Durchsuchen Sie die Websites.

SNAP ist eine Reihe von Netzwerken, die von einem Professor an der Stanford University gehostet werden. Mehrere Beispiele aus der Praxis in verschiedenen Umgebungen.

Das Net Wiki wird von einem UNC-Mathematikprofi gehostet, wiederum mit mehreren Links zu realen Datensätzen sowie Links zu anderen Datenressourcen.

OpenFlights Hat Flughäfen und Routen zwischen ihnen (räumliches Netzwerk).

OpenStreetMap benutzerbearbeitetes Straßennetz für den größten Teil der Welt. Sie können auch Teilmengen herunterladen (z. B. nur Straßen in Ohio oder nur Autobahnen in Nordamerika). Das Format ist in XML, nicht sehr einfach zu analysieren, aber es ist ein echtes zyklisches Netzwerk.

Es gibt noch einige andere Ressourcen, Sie müssen nur ein wenig graben.

Nick
quelle
2

Ich habe alle von Nick bereitgestellten Links besucht. Sie sehen in der Tat wunderbar aus und ich habe all diese Websites zu meinen Lesezeichen hinzugefügt. Wir hoffen, dass der folgende Link, der speziell zum Testen von Suchalgorithmen entwickelt wurde, auch Ihren Anforderungen entspricht:

Wegfindungs-Benchmarks von Nathan Sturtevant. Es enthält verschiedene Karten aus verschiedenen Videospielen und auch andere künstliche Benchmaker wie Labyrinthe und Grafiken mit zufälligen Hindernissen.

Wenn Sie sich insbesondere für diese Art von Domänen interessieren, möchten Sie möglicherweise nächstes Jahr am Wettbewerb für netzbasierte Pfadplanung teilnehmen (die Ergebnisse der ersten Ausgabe des Wettbewerbs sind auf der GPPC 2012 verfügbar ).

Prost,

Carlos Linares López
quelle