Saya memiliki sekelompok set n yang saya butuhkan untuk menghitung semacam nilai "keunikan" atau "kesamaan". Saya telah menetapkan indeks Jaccard sebagai metrik yang cocok. Sayangnya, indeks Jaccard hanya beroperasi pada dua set sekaligus. Untuk menghitung kesamaan antara semua set , itu akan...
Ini muncul ketika saya mencoba untuk menjawab pertanyaan ini pada Minimalisasi Panjang Kabel . Saya akan menyebutnya masalah "perkawinan poligami", tetapi internet, jadi anak kucing. Yay! Misalkan kita memiliki anak kucing yang perlu diadopsi oleh N orang, M > N . Untuk setiap anak kucing, saya...
The algoritma Bellman-Ford menentukan jalur terpendek dari sumber untuk semua simpul lainnya. Awalnya jarak antara dan semua simpul lainnya diatur ke . Kemudian jalur terpendek dari ke setiap titik dihitung; ini berlaku untuk iterasi . Pertanyaan saya
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...
Misalkan kita diberi dua angka dan dan kita ingin menemukan untuk l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Algoritma naif hanya memeriksa semua pasangan yang mungkin; misalnya dalam ruby, kita akan memiliki: def max_xor(l, r) max = 0...
Apakah mungkin untuk menggunakan algoritma penyortiran dengan perbandingan non-transitif, dan jika ya, mengapa transitivitas terdaftar sebagai persyaratan untuk menyortir komparator? Latar Belakang: Algoritma pengurutan umumnya mengurutkan elemen daftar sesuai dengan fungsi komparator C (x, y),...
Saat melakukan kata kode kedua (yang meminta Anda untuk menerapkan algoritma pencarian biner lima kali, setiap kali dengan metode yang berbeda), saya telah menghasilkan solusi yang sedikit berbeda yang berfungsi sebagai berikut: Jika saya memiliki array yang disortir dengan panjang 100 dan saya...
Saya punya masalah: Tunjukkan bahwa ada bilangan real yang tidak ada program yang berjalan sangat lama dan menulis angka desimal angka itu. Saya kira itu bisa diselesaikan dengan menguranginya menjadi masalah Berhenti, tetapi saya tidak tahu bagaimana melakukannya. Saya juga akan menghargai...
Diberikan DAG tidak tertimbang (grafik asiklik langsung) D=(V,A)D=(V,A)D = (V,A) dan dua simpul sss dan ttt , apakah mungkin untuk menemukan jalur terpendek dan terpanjang dari sss ke ttt dalam waktu polinomial? Panjang jalur diukur dengan jumlah tepi. Saya tertarik menemukan kisaran panjang jalur...
Halaman wikipedia tentang algoritma perkalian menyebutkan yang menarik oleh Donald Knuth . Pada dasarnya, ini melibatkan penggabungan fourier-transform multiplication dengan tabel pra-komputasi dari perkalian berukuran logaritmik. Ini berjalan dalam waktu linier. Artikel tersebut bertindak seperti...
Saya seorang pemula (total pemula untuk teori kompleksitas komputasi) dan saya punya pertanyaan. Katakanlah kita memiliki 'Traveling Salesman Problem', akankah aplikasi Algoritma Dijkstra berikut ini menyelesaikannya? Dari titik awal kami menghitung jarak terpendek antara dua titik. Kami langsung...
Pemrograman dinamis dapat mengurangi waktu yang dibutuhkan untuk melakukan algoritma rekursif. Saya tahu bahwa pemrograman dinamis dapat membantu mengurangi kompleksitas waktu dari algoritma. Apakah kondisi umum sedemikian rupa sehingga jika puas dengan algoritma rekursif akan menyiratkan bahwa...
Saya telah menerapkan jenis topologi berdasarkan artikel Wikipedia yang saya gunakan untuk resolusi dependensi, tetapi mengembalikan daftar linier. Algoritma apa yang dapat saya gunakan untuk menemukan jalur
Dari apa yang saya baca di preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Ini adalah Definisi PTAS : Skema aproksimasi waktu polinomial ( PTAS ) untuk masalah adalah...
Saya mencari algoritma O (V + E) untuk menemukan reduksi transitif yang diberikan DAG. Yaitu menghapus sebanyak mungkin tepi sehingga jika Anda dapat mencapai v dari Anda, untuk v dan Anda sewenang-wenang, Anda masih dapat mencapai setelah menghilangkan tepi. Jika ini adalah masalah standar,...
Diberikan dua string bagaimana Anda bisa memeriksa apakah mereka permutasi satu sama lain menggunakan ruang O (1)? Memodifikasi string tidak diizinkan dengan cara apa pun. Catatan: O (1) spasi dalam kaitannya dengan panjang string DAN ukuran
Biarkan bahasa L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* menjadi reguler. Faktorisasi LL\mathcal{L} adalah pasangan maksimal (X,Y)(X,Y)(X,Y) dari kumpulan kata dengan X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , dimana X⋅Y={xyX⋅Y={xyX \cdot Y = \{xy |...
Ketika melakukan kalkulus mental, seseorang dapat melakukannya: Dengan bilangan bulat k, jumlahkan semua digit (pada basis 10), dan jika hasilnya kelipatan 3, maka k adalah kelipatan 3. Apakah Anda tahu ada algoritma yang bekerja sama tetapi beroperasi pada digit angka biner (bit)? Pada...
Jadi penggabungan sort adalah algoritma divide and conquer. Ketika saya melihat diagram di atas, saya berpikir apakah mungkin untuk mem-bypass semua langkah pembagian. Jika Anda mengulangi lebih dari array asli sambil melompat dua, Anda bisa mendapatkan elemen di at i dan i +1 dan menempatkan...
Misalkan saya memiliki grafik dengan M ( G ) yang (tidak diketahui) set matching sempurna G . Misalkan set ini tidak kosong, lalu seberapa sulitkah untuk mengambil sampel secara acak dari M ( G ) ? Bagaimana jika saya baik-baik saja dengan distribusi yang dekat dengan seragam, tetapi tidak cukup...