Di mana mendapatkan grafik untuk menguji algoritma pencarian saya?

29

Saya menerapkan serangkaian algoritma pencarian jalur seperti Dijkstra's, Depth First, dll.

Awalnya saya menggunakan beberapa grafik yang dibuat sendiri, tapi sekarang saya ingin mengambil tantangan sedikit lebih jauh dan dengan demikian saya mencari

  1. grafik yang digunakan dalam tolok ukur;
  2. grafik kota-kota dunia nyata (atau cara untuk mengunduh info semacam itu dari peta Google, atau jenis sumber lainnya, jika mungkin).

Saya ingin sumber-sumber itu memiliki atau memungkinkan saya untuk dengan mudah membuat batas sehingga saya dapat mencoba algoritma saya untuk set grafik ukuran yang berbeda, jika memungkinkan.

Saya mencari solusi sederhana, karena saya lebih suka untuk tidak dialihkan dari tujuan utama (bandingkan satu set algoritma yang berbeda), jadi saya perlu cara cepat untuk mengubah data grafik itu ke dalam format saya sendiri (pada dasarnya, sebuah set (x, y)poin yang terhubung ).

Agar lebih konkret, yang saya cari adalah grafik siklik 2D. Jika grafik tersebut mencerminkan jalan kota dunia nyata (dengan mempertimbangkan jalan satu arah, jalan dua arah, dll, lebih baik lagi!).

algorithms graphs data-sets benchmarking melahap elysium
sumber
1
Ada arsip grafik terbuka: graph-archive.org/doku.php?id=start dan sebuah makalah yang menjelaskan proyek: arxiv.org/abs/1109.1465
Joe
1
@Raphael Grafik acak sering tidak membuat kasus uji representatif untuk grafik dunia nyata: ini cenderung jaringan yang kompleks .
Gilles 'SO- stop being evil'
2
@ jo / Pratik - mengapa tidak memposting sebagai jawaban?
Ran G.
3
@RANG. Jawaban tidak boleh hanya berupa tautan .
Gilles 'SO- stop being evil'
1
@Gilles, saya tidak bermaksud memposting komentar apa adanya, melainkan (menggunakan tautan Anda :) "Tautan ke solusi potensial selalu diterima, tetapi tolong tambahkan konteks di sekitar tautan". Saat ini, tidak ada opsi untuk mengomentari tautan tersebut, dan memilihnya. Saya yakin beberapa tautan itu sangat berguna dan menjawab pertanyaan yang diajukan, tetapi tidak ada yang dapat memperbaiki yang baik (dengan cara yang berarti).
Ran G.

Jawaban:

17

Cari antar-web.

SNAP adalah seperangkat jaringan yang diselenggarakan oleh seorang prof di Stanford. Beberapa contoh dunia nyata dalam berbagai pengaturan.

Net Wiki di -host oleh pakar matematika UNC, lagi-lagi beberapa tautan ke rangkaian data nyata serta tautan ke sumber daya data lainnya.

OpenFlights Memiliki bandara dan rute di antara mereka (jaringan spasial).

Pengguna OpenStreetMap mengedit jaringan jalan untuk sebagian besar dunia. Anda juga dapat mengunduh subset (mis. Hanya jalan di Ohio, atau hanya jalan raya di Amerika Utara). Format dalam xml, tidak super mudah untuk diurai, tetapi itu adalah dunia nyata ~ jaringan siklik 2d.

Ada beberapa sumber daya lain juga, Anda hanya perlu menggali sedikit.

Nick
sumber
2

Saya telah mengunjungi semua tautan yang disediakan oleh Nick. Mereka memang terlihat luar biasa dan saya telah menambahkan semua situs itu ke bookmark saya. Semoga tautan berikut dirancang khusus untuk menguji algoritme pencarian yang sesuai dengan kebutuhan Anda juga:

Pathfinding Benchmarks oleh Nathan Sturtevant. Ini berisi berbagai peta dari berbagai video game dan juga benchmakr buatan lainnya seperti labirin dan grafik dengan rintangan acak.

Jika Anda, khususnya, tertarik pada domain semacam ini, maka Anda mungkin ingin mengambil bagian dalam Kompetisi Perencanaan Jalur Berbasis Grid tahun depan (hasil edisi pertama kompetisi tersedia di GPPC 2012 )

Tepuk tangan,

Carlos Linares López
sumber