Skąd wziąć wykresy do przetestowania moich algorytmów wyszukiwania?

29

Wdrażam zestaw algorytmów wyszukiwania ścieżek, takich jak Dijkstra's, Depth First itp.

Początkowo korzystałem z kilku samodzielnie wykonanych wykresów, ale teraz chciałbym podjąć wyzwanie nieco dalej, dlatego szukam jednego z nich

  1. wykresy stosowane w testach porównawczych;
  2. wykresy miast świata rzeczywistego (lub sposób pobrania tego rodzaju informacji z map Google lub innego źródła, jeśli to możliwe).

Chciałbym, aby te źródła miały lub umożliwiały mi łatwe tworzenie granic, dzięki czemu mogę wypróbować algorytmy dla zestawów wykresów o różnych rozmiarach, jeśli to możliwe.

Szukam prostych rozwiązań, ponieważ wolałbym nie odwracać uwagi od głównego celu (porównaj zestaw różnych algorytmów), więc potrzebowałbym szybkiego sposobu przekonwertowania danych tego wykresu na własny format (w zasadzie zestaw połączonych (x, y)punktów).

Aby być bardziej konkretnym, szukam cyklicznych wykresów 2D. Jeśli te wykresy odzwierciedlają rzeczywiste ulice miast (biorąc pod uwagę ulice jednokierunkowe, dwukierunkowe itp., Jeszcze lepiej!).

algorithms graphs data-sets benchmarking pochłonęło elysium
źródło
1
Istnieje otwarte archiwum grafów: graph-archive.org/doku.php?id=start oraz artykuł wyjaśniający projekt: arxiv.org/abs/1109.1465
Joe
1
@Raphael Losowe wykresy często nie tworzą reprezentatywnych przypadków testowych dla prawdziwych wykresów: są to zazwyczaj złożone sieci .
Gilles „SO- przestań być zły”
2
@joe / Pratik - dlaczego nie opublikować jako odpowiedzi?
Ran G.
3
@RanG. Odpowiedź nie powinna być tylko linkiem .
Gilles 'SO - przestań być zły'
1
@Gilles, nie miałem na myśli zamieszczania komentarzy takimi, jakimi są, ale raczej (używając linku :) „Link do potencjalnego rozwiązania jest zawsze mile widziany, ale proszę dodać kontekst wokół linku”. Obecnie nie ma możliwości komentowania tych linków i głosowania na nie. Jestem pewien, że niektóre z tych linków są bardzo przydatne i odpowiadają na zadane pytanie, ale nikt nie może głosować za tymi dobrymi (w sensowny sposób).
Ran G.

Odpowiedzi:

17

Przeszukaj strony internetowe.

SNAP to zestaw sieci obsługiwany przez profesora ze Stanford. Kilka przykładów ze świata rzeczywistego w różnych ustawieniach.

Net Wiki jest hostowany przez profesora matematyki UNC, ponownie kilka linków do prawdziwych zbiorów danych, a także linki do innych zasobów danych.

OpenFlights ma lotniska i trasy między nimi (sieć przestrzenna).

Sieć dróg edytowana przez użytkownika OpenStreetMap dla większości świata. Możesz także pobierać podzbiory (np. Tylko drogi w Ohio lub po prostu autostrady w Ameryce Północnej). Format jest w formacie XML, niezbyt łatwy do przeanalizowania, ale jest to rzeczywista cykliczna sieć ~ 2d.

Istnieje również kilka innych zasobów, po prostu trzeba trochę kopać.

Nacięcie
źródło
2

Odwiedziłem wszystkie linki dostarczone przez Nicka. Wyglądają naprawdę wspaniale i wszystkie te strony dodałem do moich zakładek. Mam nadzieję, że poniższy link specjalnie zaprojektowany do testowania algorytmów wyszukiwania odpowiada również Twoim potrzebom:

Pathfinding Benchmarks autorstwa Nathana Sturtevanta. Zawiera różne mapy z różnych gier wideo, a także inne sztuczne benchmakry, takie jak labirynty i wykresy z losowymi przeszkodami.

Jeśli szczególnie interesujesz się tego rodzaju domenami, możesz wziąć udział w konkursie planowania ścieżek opartym na siatce w przyszłym roku (wyniki pierwszej edycji konkursu są dostępne na GPPC 2012 )

Twoje zdrowie,

Carlos Linares López
źródło