Bagaimana saya bisa menentukan jumlah jalur sederhana yang unik dalam grafik yang tidak diarahkan? Baik untuk panjang tertentu, atau rentang panjang yang dapat diterima.
Ingat bahwa jalur sederhana adalah jalur tanpa siklus, jadi saya berbicara tentang menghitung jumlah jalur tanpa siklus.
Jawaban:
Ada beberapa algoritma yang menghitung jalur sederhana panjang dalam waktu f ( k ) n k / 2 + O ( 1 ) , yang jauh lebih baik daripada waktu brute force ( O ( n k ) ). Lihat misalnya Vassilevska dan Williams, 2009 .k f(k)nk/2+O(1) O(nk)
sumber
Ini # P-complete (Valiant, 1979) sehingga Anda tidak mungkin melakukan jauh lebih baik daripada brute force, jika Anda menginginkan jawaban yang tepat. Perkiraan didiskusikan oleh Roberts dan Kroese (2007).
B. Roberts dan DP Kroese, " Memperkirakan jumlah jalur - t dalam grafiks t ". Jurnal Grafik Algoritma dan Aplikasi , 11 (1): 195-214, 2007.
LG Valiant, " Kompleksitas masalah enumerasi dan keandalan ". Jurnal SIAM tentang Komputasi 8 (3): 410-421, 1979.
sumber
Saya ingin menambahkan algoritma aproksimasi lain, yang parametrize: Untuk tetap > 0 (atau lebih tepatnya, δ = Ω ( 1δ>0 ), Anda dapat menghitungsebuah(1+δ)-approximation dari jumlah jalur sederhana, baik dalam grafik diarahkan atau diarahkan, panjangkdalam waktuO*(2O(k)).δ=Ω(1poly(k)) (1+δ) k O∗(2O(k))
sumber