Saya telah mengembangkan teknik derandomisasi baru yang ditujukan untuk algoritma acak rekursif (atau) algoritma acak yang lebih umum yang menggunakan tumpukan. Sayangnya, saya tidak dapat menemukan algoritma acak alami untuk menerapkan teknik saya. Rantai Markov rekursif dan tata bahasa Stochastic sangat dekat dengan apa yang saya cari. Apakah ada algoritma acak (lebih alami) lainnya yang membuat penggunaan stack "esensial"? Setiap bantuan sangat dihargai, karena saya terjebak dengan ini selama lebih dari enam bulan sekarang.
Untuk memberi Anda lebih banyak konteks, saya mencari daftar masalah yang mirip dengan yang ada di SivaKumar's Paper . Perhatikan bahwa SivaKumar menggunakan generator Pseudo-random Nisan untuk menghilangkan masalah-masalah ini.
sumber
Jawaban:
Seperti yang ditunjukkan Per Vognsen, dan lebih umum juga, ada banyak algoritma geometris yang beroperasi sebagai berikut: Pilih sampel acak, dan jalankan secara rekursif pada sampel dan pada struktur lain yang berasal darinya. Algoritma acak Clarkson untuk pemrograman linier, serta Seidel, dan memang seri Matousek-Sharir-Welzl yang disebutkan Per, semua beroperasi dengan cara ini, dan paradigma Clarkson meluas ke situasi lain di mana Anda membangun semacam pemotongan atau epsilon-net dan rekursi. .
Sayangnya, Anda tidak mungkin mendapatkan hasil baru dari ini, karena ada derandomisasi optimal dari algoritma ini, karena bekerja oleh Matousek, dan Chazelle. Makalah Chazelle adalah titik referensi yang baik untuk pekerjaan ini dan karya sebelumnya oleh Matousek. Tapi ini mungkin ujian yang bagus untuk metode Anda: sulit untuk membuat derandomisasi ini, dan jika metode Anda memberikan pendekatan kotak hitam dimulai dengan algoritma acak (lebih mudah), itu akan rapi.
id ini mungkin contoh yang paling membosankan, tetapi apakah metode Anda bekerja dengan quicksort, atau salah satu dari metode penemuan median acak?
sumber
Bagaimana dengan algoritma acak Welzl untuk ellipsoid yang tertutup minimal? Ia memiliki kedalaman rekursi O (d) di mana d adalah dimensi ruang.
Saya hampir tidak tahu apa-apa tentang derandomisasi, jadi ini mungkin bukan yang Anda cari. Jika contoh saya tidak memenuhi syarat (mungkin menurut definisi Anda itu hanya menggunakan rekursi yang tidak penting?), Mungkin Anda bisa menjelaskan mengapa itu terjadi. Itu akan meningkatkan peluang kualitas yang lebih tinggi, jawaban yang lebih relevan dari orang lain.
sumber
Versi algoritma min-cut yang lebih cepat memang sangat rekursif. Lihat gambar 2.5 di sini , atau buku teks algoritma acak standar.
sumber