Ada metode sepele untuk mensimulasikan jalan acak melalui grafik dengan mengekspektasi matriks kedekatan stokastik, tetapi masalahnya menjadi lebih sulit jika Anda meminta jalan acak untuk menghindari diri sendiri. Dengan kata lain, proses harus melintasi grafik menggunakan jalur, seperti infeksi atau sesuatu.
Jika probabilitas tepi besar, ada algoritma Monte Carlo sederhana: Di setiap percobaan, Anda cukup menghapus setiap tepi dengan probabilitas , menghitung komponen terhubung grafik baru, dan menambahkan matriks penghitungan dengan matriks 1s untuk setiap kontak. komponen. Anda membaginya dengan jumlah percobaan di akhir.
Adakah yang tahu algoritma untuk melakukan perhitungan ini ketika probabilitasnya cukup kecil?
Jika grafik tidak terlalu terhubung, Anda dapat menemukan beberapa set potongan minimum, dan melakukan penghitungan inklusi-pengecualian pada mereka, tetapi pendekatan seperti itu eksponensial ganda dalam ukuran set cut. Ada berbagai optimisasi untuk kasus-kasus spesifik konektivitas tinggi juga, seperti memperlakukan semua subgraf klik secara terpisah melalui perhitungan yang jelas. Ada ide yang lebih umum?
sumber
Jawaban:
Saya tidak yakin apakah saya menafsirkan pertanyaan Anda dengan benar, tetapi bagi saya Anda bertanya bukan tentang mensimulasikan jalan acak yang menghindari diri sendiri, tetapi tentang menghitung jalan acak yang menghindari diri sendiri. Saya mengatakan ini karena Anda berbicara tentang eksponensial matriks adjacency, yang akan memberi Anda enumerasi (berbobot) jalan acak.
Saya tidak yakin apakah ada banyak literatur tentang penghitungan jalan penghindaran diri dalam grafik umum; Saya percaya bahwa sebagian besar perhatian telah difokuskan pada jalan menghindari diri dalam kisi-kisi di ruang Euclidean, dan itulah dasar dari komentar saya di bawah ini. Saya menduga bahwa banyak ide akan dibawa ke grafik umum.
Alat klasik untuk mengurangi tenaga kerja yang terlibat dalam penghitungan jalan penghindaran diri secara tepat adalah ekspansi renda. Anda harus dapat menemukan literatur yang relevan dengan mudah dengan kata kunci itu. Namun, untuk grafik yang sangat terhubung, dugaan saya adalah bahwa ide renda-ekspansi tidak akan banyak membantu (tapi mungkin tidak ada yang akan banyak membantu dalam kasus itu).
Jika Anda puas dengan perkiraan penghitungan maka ada beberapa opsi. Lihat makalah EJJ van Rensburg 2009 tentang "Perkiraan penghitungan berjalan kaki yang menghindari diri sendiri" untuk survei. Lihat juga "Algoritma pengujian diri untuk berjalan kaki yang menghindari diri sendiri" oleh Randall dan Sinclair (2000).
sumber