Misalkan menjadi grafik terhubung yang tidak teratur yang derajatnya dibatasi. Misalkan setiap node berisi token unik.
Saya ingin secara acak mengocok token di antara grafik hanya menggunakan swap lokal (yaitu pertukaran token antara dua node yang berdekatan)? Apakah ada batas bawah yang diketahui untuk masalah ini?
Satu-satunya ide yang saya miliki adalah menggunakan hasil jalan acak, kemudian untuk melihat berapa banyak swap yang saya perlukan untuk "mensimulasikan" efek jalan acak yang mengangkut token pada grafik.
ds.algorithms
random-walks
dc.distributed-comp
Sylvain Peyronnet
sumber
sumber
Jawaban:
Misalkan grafik Anda adalah sebuah jalur. Saya pikir kemudian masalah ini menjadi setara dengan menyortir urutan angka acak dalam array dengan menukar entri yang berdekatan. Bahkan dari semua node sadar topologi, Anda mendapatkan ^ 2 batas bawah pada jumlah swap (tidak bisa melakukan lebih baik daripada bubble sort yang n ^ 2 bahkan pada input acak).
sumber
Saya ingin menunjukkan hubungan antara masalah ini dan menyortir jaringan. Misalnya, jika grafik Anda adalah jalur, maka jaringan pengurutan trivial linear juga menunjukkan bahwa Anda dapat memperoleh permutasi dalam jumlah putaran linear. Selain itu, ini ketat, karena hanya menukar elemen di titik akhir jalan membutuhkan jumlah linier putaran.
Jaringan penyortiran AKS menunjukkan bahwa ada grafik di mana Anda dapat memperoleh permutasi dalam jumlah putaran logaritmik. Untuk kasus grafik kotak, lihat misalnya catatan kuliah ini .
(Tentu saja pengurutan dan pengacakan adalah masalah yang berbeda, tetapi banyak batas atas dan bawah terkait. Misalnya, pilih label acak dan urutkan berdasarkan label.)
sumber