Banyak algoritma aliran max yang biasa saya lihat diimplementasikan, algoritma Dinic, push relabel, dan lainnya, dapat meningkatkan biaya waktu asimptotik melalui penggunaan pohon dinamis (juga dikenal sebagai pohon tautan-potong). Relabel dorong berjalan di atau O ( V 3 ) atau O ( V 2 √O (...
Misalkan kita memiliki grafik diarahkan dan dua node dan . Saya ingin tahu apakah sudah ada algoritma untuk menghitung masalah keputusan berikut:G=(V,E)G=(V,E)G=(V,E)AAABBB Apakah setidaknya ada dua jalur antara dan dengan panjang yang sama?AAABBB Bagaimana dengan kerumitannya? Bisakah saya...
Saat menguji algoritma, pendekatan yang umum adalah pengujian acak: menghasilkan sejumlah besar input sesuai dengan beberapa distribusi (biasanya seragam), jalankan algoritma pada mereka dan verifikasi kebenarannya. Kerangka pengujian modern dapat menghasilkan input secara otomatis mengingat tanda...
Grafik unipathic adalah grafik terarah sedemikian sehingga ada paling banyak satu jalur sederhana dari satu titik ke titik lainnya. Grafik unipathic dapat memiliki siklus. Misalnya, daftar yang ditautkan dua kali lipat (bukan yang melingkar!) Adalah grafik unipathic; jika daftar memiliki elemen,...
Jadi saya pikir pertanyaan (meskipun agak mendasar) ini ada di sini: Katakanlah saya memiliki grafik ukuran 100 node yang tersusun dalam pola 10x10 (pikirkan papan catur). Grafik tidak diarahkan, dan tidak berbobot. Bergerak melalui grafik melibatkan bergerak tiga ruang ke depan dan satu ruang ke...
Ingin memperbaiki pos ini? Berikan jawaban terinci untuk pertanyaan ini, termasuk kutipan dan penjelasan mengapa jawaban Anda benar. Jawaban tanpa detail yang cukup dapat diedit atau dihapus. Kami telah membaca tentang algoritma untuk MST, konektivitas yang kuat,
Dalam banyak implementasi pencarian kedalaman-pertama yang saya lihat (misalnya: di sini ), kode membedakan antara simpul abu-abu (ditemukan, tetapi tidak semua tetangganya dikunjungi) dan simpul hitam (ditemukan dan semua tetangganya dikunjungi) . Apa tujuan dari perbedaan ini? Tampaknya algoritma...
Saya telah memperhatikan bahwa struktur data yang berbeda digunakan ketika kita menerapkan algoritma pencarian. Sebagai contoh, kami menggunakan antrian untuk melaksanakan luasnya pertama pencarian, tumpukan untuk melaksanakan pencarian mendalam-pertama dan min-tumpukan untuk menerapkan A *...
Kita tahu bahwa menghitung aliran arus maksimum. potongan minimum jaringan dengan kapasitas setara; lih. yang max-flow min-cut teorema . Kami memiliki (kurang lebih efisien) algoritma untuk menghitung aliran maksimum, dan menghitung potongan minimum mengingat aliran maksimum juga tidak sulit atau...
Saya mencoba untuk menemukan metode yang efisien untuk mendeteksi apakah suatu grafik G memiliki dua pohon spanning minimal yang berbeda. Saya juga mencoba menemukan metode untuk memeriksa apakah ia memiliki 3 pohon spanning minimal yang berbeda. Solusi naif yang pernah saya pikirkan tentang...
Kami memiliki DAG. Kami memiliki fungsi pada node F: V→ NF:V→NF\colon V\to \mathbb N (secara longgar, kami beri nomor pada node). Kami ingin membuat grafik terarah baru dengan aturan ini: Hanya node dengan nomor yang sama dapat dikontrak ke node baru yang sama. F( x ) ≠ F( y) ⇒ x′≠...
Saya sangat akrab dengan Dijkstra dan saya memiliki pertanyaan spesifik tentang algoritme. Jika saya memiliki grafik yang sangat besar, misalnya 3,5 miliar node (semua data OpenStreetMap) maka saya jelas tidak akan dapat memiliki grafik dalam memori, sehingga grafik disimpan pada disk di dalam...
Saya mengajukan pertanyaan ini di stackoverflow generik dan saya diarahkan di sini. Akan sangat bagus jika seseorang dapat menjelaskan cara mendekati masalah grafik parsial atau dinamis penuh secara umum. Sebagai contoh: Temukan Jalur Terpendek antara dua simpul dalam grafik tertimbang yang...
Saya diberitahu bahwa kami akan menggunakan daftar jika grafik jarang dan matriks jika grafik padat . Bagi saya, itu hanya definisi mentah. Saya tidak melihat banyak hal di luarnya. Bisakah Anda mengklarifikasi kapan akan menjadi pilihan alami? Terima kasih
Saya punya pohon (dalam arti teori grafik), seperti contoh berikut: Ini adalah pohon terarah dengan satu simpul mulai (root) dan banyak simpul akhir (daun). Masing-masing ujung memiliki panjang yang ditetapkan untuk itu. Pertanyaan saya adalah, bagaimana cara menemukan jalan terpanjang mulai...
Masalah ini, bagi saya, terlihat sangat menarik. Itu akan menemukan siklus sederhana (yaitu siklus di mana node tidak berulang) dalam grafik diarahkan. Solusi saya akan seperti ini, yaitu, grafik ini adalah masalah kasus: Saya tahu bahwa ada siklus dalam grafik, ketika Anda dapat menemukan "tepi...
Saya membaca tentang Masalah Aliran Maksimum di sini . Saya tidak dapat memahami intuisi di balik Grafik Residual. Mengapa kita mempertimbangkan tepi belakang saat menghitung aliran? Adakah yang bisa membantu saya memahami konsep Grafik Sisa? Bagaimana perubahan Algoritma pada Grafik Tidak...
Algoritme apa yang akan Anda gunakan untuk menemukan jalur terpendek dari grafik, yang tertanam dalam bidang euclidean, sehingga jalur tersebut tidak boleh mengandung persimpangan-sendiri (dalam penyematan)? Misalnya, dalam grafik di bawah ini, Anda ingin beralih dari . Biasanya, algoritma seperti...
Saya mencoba untuk memecahkan masalah grafik (ini bukan untuk pekerjaan rumah, hanya untuk melatih keterampilan saya). DAG diberikan, di mana V adalah himpunan simpul dan E tepi. Grafik diwakili sebagai daftar adjacency, jadi A v adalah himpunan yang berisi semua koneksi v . Tugas saya adalah untuk...
Jika grafik GGG terhubung dan tidak memiliki jalan dengan lebih panjang daripada , membuktikan bahwa setiap dua jalur di panjang memiliki setidaknya satu titik kesamaan. G kkkkGGGkkk Saya berpikir bahwa simpul umum harus di tengah-tengah kedua jalur. Karena jika ini tidak terjadi maka kita dapat...