Untuk metode branch-and-cut, penting untuk mengetahui banyak sisi dari poltop yang dihasilkan oleh masalah. Namun, saat ini merupakan salah satu masalah yang paling sulit untuk benar-benar menghitung semua segi polytopes karena mereka dengan cepat tumbuh dalam ukuran. Untuk masalah optimasi...
Kepuasan umum (dengan beberapa pengecualian seperti Klausa Tanduk) tidak diyakini memiliki solusi algoritmik. Namun, algoritma berikut tampaknya menjadi solusi untuk kepuasan umum. Apa sebenarnya cacat dengan algoritma berikut? Membiarkan WWW menjadi set kosong yang akan berisi semua variabel...
Sumber pertanyaan ini berasal dari program sarjana yang saya ikuti, yang mencakup pengantar analisis algoritma. Ini bukan untuk pekerjaan rumah, melainkan pertanyaan yang diajukan di CLRS. Anda memiliki mesin yang berjalan lambat xxx MIPS, dan mesin cepat berjalan di yyyMIPS. Anda juga memiliki...
Diberikan grafik terarah dan dua simpul S dan T yang berbeda, adakah algoritma waktu polinomial yang menemukan setiap simpul yang berada pada setidaknya satu jalur sederhana dari S ke T? Tidak sulit untuk menemukan semua simpul yang merupakan penerus S dan pendahulu T tetapi ini hanya superset...
Saya memiliki hutan, yaitu node dengan tepi terarah dan tanpa siklus (terarah atau tidak terarah). Saya mendefinisikan ketinggian suatu simpulvvv sebagai 0 jika tidak memiliki tepi masuk, atau jumlah tepi maksimum untuk dilalui secara terbalik untuk mencapai puncak ketinggian 0. Saya juga tahu...
Saya sudah mencoba menerapkan algoritma Brzozowski tetapi saya baru saja menemukan bahwa itu menciptakan automata suboptimal untuk kelas input tertentu, memiliki satu keadaan lebih dari apa yang benar-benar diperlukan dalam hasilnya. Saya bisa menunjukkannya pada robot yang sepele: a b a b a b a...
Katakanlah saya menemukan algoritma 2-aproksimasi untuk masalah tertentu dan saya ingin menunjukkan bahwa analisisnya ketat. Apakah saya sekarang perlu untuk datang dengan sebuah contoh ukuran generik atau tidak cukup untuk menunjukkan bahwa saya memiliki contoh ukuran yang algoritma menghasilkan...
Dari, pembuktian dengan metode probabilistik sering dikatakan tidak konstruktif. Namun, bukti dengan metode probabilistik memang merancang algoritma acak dan menggunakannya untuk membuktikan keberadaan. Dikutip dari p103 Randomized Algorithms Oleh Rajeev Motwani, Prabhakar Raghavan : Kita bisa...
Dalam teori algoritma terdistribusi, ada masalah dengan batas bawah, seperti Ω (n2)Ω(n2)\Omega(n^2), itu "besar" (maksud saya, lebih besar dari Ω ( n logn )Ω(nlogn)\Omega(n\log n)), dan nontrivial. Saya bertanya-tanya apakah ada masalah dengan ikatan yang serupa dalam teori algoritma serial,...
Diberikan grafik , di mana . Apa yang dimaksud dengan algoritma cepat untuk menghasilkan koleksi semua daftar lingkungan 2-hop dari semua node di .G=(V,E)G=(V,E)G = (V,E)|V|=n|V|=n|V| = nVVV Secara naif, Anda dapat melakukannya di . Dengan kekuatan matriks, Anda dapat melakukannya dengan...
XOR bukan nama yang tepat, tetapi saya mencari semacam perilaku eksklusif. Saat ini saya sedang memecahkan serangkaian masalah (penugasan) yang berbeda dengan memodelkan jaringan aliran dan menjalankan algoritma min-cost-max-flow. Jaringan aliran sangat berguna karena banyak masalah dapat...
Diberikan array integer (ukuran maksimum 50000), saya harus menemukan minimum dan maksimum sehingga untuk beberapa , dengan .XXXX=ap⊕ap+1⊕⋯⊕aqX=ap⊕ap+1⊕⋯⊕aqX = a_p \oplus a_{p+1} \oplus \dots \oplus a_qpppqqqp≤qp≤qp \leq q Saya telah mencoba proses ini: untuk semua . Saya pra-menghitungnya dalam...
Saya benar-benar ingin bantuan Anda dengan membuktikan atau menyangkal klaim berikut: . Dalam teori kompleksitas komputasi, BPP, yang berarti waktu polinom probabilitas terbatasi-kesalahan adalah kelas masalah keputusan yang dipecahkan oleh mesin Turing probabilistik dalam waktu polinomial, dengan...
Pertimbangkan masalah berikut: Biarkan roda didefinisikan sebagai daftar bilangan bulat diindeks secara melingkar . Sebagai contoh…kkkkkk {3, 4, 9, -1, 6} … Adalah roda 5 dengan 3 di posisi 0, 4 di posisi 1, dan seterusnya. Roda mendukung operasi rotasi, sehingga rotasi satu langkah...
Input: Satu set array (angka). Elemen-elemen dalam setiap array berada dalam urutan, tetapi set array tidak perlu diurutkan. Array tidak harus berukuran sama. Jumlah elemen adalah n .ℓℓ\ellAiAiA_innn Output: The kkk th elemen terkecil dari semua elemen dalam input. Apa algoritma yang paling...
Saya mengalami beberapa kesulitan dalam memahami algoritma terdistribusi untuk pohon 6 - pewarnaan di O(log∗n)O(log∗n)O(\log^*n) waktu. Deskripsi lengkap dapat ditemukan di makalah berikut: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon . Singkatnya, idenya adalah...
Saya telah membaca tentang algoritma untuk menemukan komponen yang sangat terhubung dalam grafik yang diarahkan G=(V,E)G=(V,E)G=(V,E). Ini mempertimbangkan dua DFS mencari dan langkah kedua adalah transposing grafik asli .GTGTG^T Algoritma adalah sebagai berikut: Jalankan DFS pada (mulai dari...
Diberikan satu set n pekerjaan dengan [waktu mulai, waktu selesai, biaya] menemukan subset sehingga tidak ada 2 pekerjaan yang tumpang tindih dan biaya maksimum. Sekarang saya tidak yakin apakah algoritma serakah akan melakukan trik. Yaitu, urutkan berdasarkan biaya dan selalu mengambil...
Pertimbangkan masalah ini: Diberikan grafik tidak terarah G=(V,E)G=(V,E)G = (V, E), Temukan G′=(V′,E′)G′=(V′,E′)G' = (V', E') seperti yang: G′G′G' adalah subgraph yang diinduksi dari GGG G′G′G' tidak memiliki 3-klik |V′||V′||V'| maksimal Jadi jumlah simpul paling sedikit harus...
Dari grafik isomorfisme, kita tahu bahwa dua grafik A dan B adalah isomorfik jika ada matriks permutasi P sehingga A = P× B ×P- 1SEBUAH=P×B×P-1A = P \times B \times P^{-1} Jadi, untuk menyelesaikan masalah, jika dua grafik isomorfis, kita perlu menemukan matriks permutasi P. Masalahnya diyakini...