Menghasilkan input untuk algoritma grafik pengujian-acak?

Saat menguji algoritma, pendekatan yang umum adalah pengujian acak: menghasilkan sejumlah besar input sesuai dengan beberapa distribusi (biasanya seragam), jalankan algoritma pada mereka dan verifikasi kebenarannya. Kerangka pengujian modern dapat menghasilkan input secara otomatis mengingat tanda tangan algoritma, dengan beberapa batasan.

Jika input berupa angka, daftar atau string, buat input tersebut secara langsung. Pohon lebih sulit, tetapi masih mudah (menggunakan tata bahasa bebas konteks stokastik atau pendekatan serupa).

Bagaimana Anda bisa menghasilkan grafik acak (efisien)? Biasanya, memilih grafik secara acak secara acak bukanlah yang Anda inginkan: grafik harus terhubung, atau planar, atau bebas siklus, atau memenuhi properti lainnya. Sampling penolakan tampaknya suboptimal, karena serangkaian besar grafik yang tidak diinginkan.

Apa distribusi yang berguna untuk dilihat? Berguna di sini artinya

• grafik cenderung menguji algoritma yang ada dengan baik dan
• mereka dapat dihasilkan secara efektif dan efisien.

Saya tahu bahwa ada banyak model untuk grafik acak, jadi saya menghargai beberapa wawasan yang terbaik untuk pembuatan grafik dalam hal ini.

Jika "beberapa algoritma" terlalu umum, silakan gunakan algoritma pencarian jalur terpendek sebagai kelas konkret dari algoritma yang sedang diuji. Grafik untuk pengujian harus terhubung dan agak padat (dengan probabilitas tinggi, atau setidaknya dalam harapan). Untuk pengujian, solusi optimal adalah membuat grafik acak di sekitar jalur terpendek sehingga kami tahu hasil yang diinginkan (tanpa harus menggunakan algoritma lain).

Grafik acak dengan topologi dunia kecil

Dalam grafik dengan topologi dunia kecil , node sangat berkerumun namun panjang jalur di antara mereka kecil. Topologi seperti ini dapat membuat masalah pencarian menjadi sangat sulit, karena keputusan lokal cepat menyebar ke seluruh dunia. Dengan kata lain, pintasan dapat menyesatkan heuristik. Lebih lanjut telah ditunjukkan bahwa banyak masalah pencarian berbeda memiliki topologi dunia kecil.

$p$$p=0$$p=1$$0 < p < 1$$p=0$$p=1$

$n$$k$$n \gg k \gg \ln(n) \gg 1$$k \gg \ln(n)$

Model Watts dan Strogatz agak populer, tetapi memang memiliki kelemahan tertentu. Walsh [2] menyelidiki efek pengacakan dan memulai kembali strategi dalam grafik yang dihasilkan menggunakan model. Ada juga makalah oleh Virtanen [3], yang mencakup model-model lain yang dimotivasi oleh kebutuhan pemodelan realistis sistem kompleks.

Grafik planar acak acak

$n$$n$$g_n$$g_n$$1 \leq n \leq 9$$1,2,8,64,1023,32071,1823707,163947848$$20402420291$$g_n$

$\rightarrow$$\rightarrow$$\rightarrow$$\rightarrow$

$n$$x^n$$x$

Untuk pengantar yang ringan, lihat presentasi oleh Fusy .

[1] DJ Watts dan SH Strogatz. Dinamika kolektif jaringan 'dunia kecil'. Alam, 393: 440-442, 1998 .

[2] Toby Walsh. Cari di dunia kecil. Prosiding Konferensi Bersama Internasional ke-16 tentang Kecerdasan Buatan (IJCAI-99-Vol2), halaman 1172-1177, 1999 .

[3] Satu Virtanen. Properti model grafik acak tidak seragam. Laporan Penelitian A77, Universitas Teknologi Helsinki, Laboratorium untuk Ilmu Komputer Teoretis, 2003 .

[4] O. Giménez dan M. Noy. Enumerasi asimptotik dan batas hukum grafik planar, arXiv math.CO/0501269. Abstrak yang diperluas telah muncul dalam Matematika Diskrit dan Ilmu Komputer Teoritis AD (2005), 147-156 .

[5] E. Fusy. Grafik waktu planar kuadratik dan linier, Matematika Diskrit, dan Ilmu Komputer Teoritis (2005), 125-138 .

[6] P. Duchon, P. Flajolet, G. Louchard, dan G. Schaeffer. Boltzmann sampler untuk pembuatan acak struktur kombinatorial. Combinatorics, Probability and Computing, 13 (4-5): 577-625, 2004 .