Bagaimana saya dapat secara acak menghasilkan pohon yang merentang tinggi?

Untuk proyek yang sedang saya kerjakan, saya harus membuat pohon spanning acak dengan tinggi terikat.

Pada dasarnya saya melakukan hal berikut: 1) Menghasilkan spanning tree 2) Periksa kelayakan, jika layak simpan.

1) Mulai dari pohon spanning minimum (Prim atau Kruskal) Saya menambahkan tepi yang tidak ada dan ini menciptakan siklus, saya mendeteksi siklus ini dan menghapus salah satu ujung siklus ini yang memberi saya pohon spanning baru dan saya melanjutkan dengan spanning tree ini dengan menambahkan tepi baru ...

2) Misalkan ada titik khusus . Untuk setiap simpul v , panjang lintasan dari v ke V c e n t e r harus kurang dari δ , di mana δ adalah parameter yang diberikan.$v_{center}$$v$$v$$V_{center}$$\delta$$\delta$

Apakah ada cara yang lebih baik (pintar) untuk melakukan ini?

PS Saya lupa menentukan batasan lain (kesalahan saya): tingkat simpul juga harus dibatasi.

Saya sedang mengerjakan pohon merentang dengan kedalaman terbatas beberapa tahun yang lalu, mereka sangat menarik. Beberapa kolega saya datang dengan algoritma message passing yang bekerja dengan baik, tetapi saya tidak dapat menemukan kode mereka yang tersedia. Kami menulisnya dalam gaya fisika di sini: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Mereka mengatakan kepada saya bahwa itu juga bekerja dengan batas-batas derajat, meskipun itu tidak membuatnya menjadi makalah.

Pendekatan yang Anda usulkan, yang saya sebut Markov Chain Monte Carlo, seringkali merupakan pesaing dari pendekatan passing pesan. Jika Anda tertarik dalam pengambilan sampel yang kira-kira seragam secara acak dari kumpulan pohon rentang-terikat, kedalaman-terikat dari grafik tertentu, saya sarankan untuk mengubah pendekatan Anda untuk menggunakan batas "lunak". Yaitu alih-alih menolak pertukaran tepi yang membuat pohon melanggar batas terikat, menerimanya, tetapi dengan probabilitas lebih rendah dari pertukaran yang tidak melanggar batas. Jika Anda memiliki parameter yang mengontrol seberapa rendah probabilitas ini, Anda dapat membuat kendala yang melanggar konfigurasi semakin tidak mungkin sampai Anda tiba pada solusi yang layak yang hampir seragam acak.

Pertanyaan besarnya adalah berapa lama Anda perlu menjalankan rantai. Karena spanning tree dengan derajat paling banyak 2 adalah jalur Hamiltonian, Anda harus mengharapkan ikatan generik untuk menjadi eksponensial dalam ukuran grafik. Tapi mungkin grafik yang Anda minati spesial dalam beberapa hal.

Jika masalah Anda adalah mengambil sampel pohon spanning secara seragam dari himpunan , di mana S adalah himpunan semua pohon spanning hight paling banyak h , untuk beberapa input h , maka strategi Anda berfungsi (yaitu, sampel pohon spanning acak dan periksa apakah paling tinggi paling tinggi h ).$S$$S$$h$$h$$h$

Namun, saya tidak yakin apakah algoritma yang Anda jelaskan akan menghasilkan pohon spanning acak. Saya akan merekomendasikan melihat algoritma standar sebagai gantinya. Ada dua algoritma: algoritma Wilson dan algoritma Aldous-Broder. Anda dapat melihatnya di sini . Ada algoritma yang lebih baru (aproksimasi) tetapi cukup rumit.

Juga, mungkin ada cara untuk menghasilkan spanning tree ini dengan hight terikat langsung. Tapi saya belum pernah mendengar tentang algoritma seperti itu.

Gunakan pencarian luas pertama! Lakukan BFS dari setiap simpul dalam grafik, pilih pohon yang dihasilkan dari ketinggian terkecil. BFS selalu menemukan jalur dari root ke setiap simpul lain dengan hop paling sedikit.