Pohon adalah jenis grafik khusus yang hanya memungkinkan serangkaian tepi hierarkis yang mirip dengan pohon. Secara matematis, ini sebenarnya sebuah arborescence. Pohon memiliki simpul akar dan simpul anak. Dalam istilah formal ini digambarkan sebagai grafik terhubung asiklik.
Beberapa masalah optimisasi yang dikenal sebagai NP-hard pada grafik umum sepele dipecahkan dalam waktu polinomial (beberapa bahkan dalam waktu linier) ketika grafik input adalah pohon. Contohnya termasuk penutup simpul minimum, set independen maksimum, isomorfisme subgraph. Sebutkan beberapa...
Saya memiliki beberapa pengalaman dalam komputasi ilmiah, dan telah banyak menggunakan pohon kd untuk aplikasi BSP (partisi ruang biner). Saya baru-baru ini menjadi lebih akrab dengan oktri, struktur data yang mirip untuk mempartisi ruang Euclidean 3-D, tetapi yang bekerja pada interval tetap yang...
Kami mendefinisikan bahasa pohon biasa seperti dalam buku TATA : Ini adalah kumpulan pohon yang diterima oleh otomat pohon terbatas non-deterministik (Bab 1) atau, setara, serangkaian pohon yang dihasilkan oleh tata bahasa pohon biasa (Bab 2). Kedua formalisme memiliki kemiripan yang erat dengan...
Seorang kolega yang bekerja pada pemrograman genetika menanyakan kepada saya pertanyaan berikut. Saya pertama kali mencoba menyelesaikannya berdasarkan pendekatan serakah, tetapi pada pemikiran kedua, saya menemukan contoh tandingan terhadap algoritma serakah. Jadi, saya pikir layak disebutkan di...
Saya baru-baru ini membaca ringkasan masalah yang terlibat dengan melakukan perbedaan di antara pohon-pohon dan itu membuat saya tertarik untuk belajar apa yang paling canggih untuk masalah ini. Juga, anggaplah bahwa di antara operasi edit yang diizinkan adalah simpul tambah / hapus tradisional,...
Saya mencari cara untuk mempertahankan pohon rentang yang relatif seimbang dari grafik, karena saya menambahkan node / tepi baru ke grafik. Saya memiliki grafik tidak terarah yang dimulai sebagai satu simpul, "root". Pada setiap langkah, saya menambahkan grafik baik simpul baru dan tepi yang...
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Saya mencari algoritme untuk menggabungkan dua pohon pencarian biner dengan ukuran dan jangkauan yang berubah-ubah. Cara yang jelas saya akan menerapkan ini adalah untuk menemukan seluruh sub pohon yang jangkauannya dapat masuk ke dalam simpul eksternal yang berubah-ubah di pohon lain. Namun, kasus...
Saya telah menanyakan pertanyaan ini pada Stack Overflow beberapa waktu lalu: Masalah: Penjualan Bob . Seseorang menyarankan untuk mengirim pertanyaan di sini juga. Seseorang telah mengajukan pertanyaan terkait dengan masalah ini di sini - Berat minimum hutan hujan dari kardinalitas yang diberikan...
Saya sedang membaca satu bab dalam LYAH yang tidak terlalu masuk akal bagi saya. Saya mengerti bahwa ritsleting dapat secara sewenang-wenang melintasi struktur seperti pohon, tetapi saya perlu klarifikasi. Juga, dapatkah resleting digeneralisasikan ke struktur data apa
Masalah pemeliharaan pesanan (atau "mempertahankan pesanan dalam daftar") adalah untuk mendukung operasi: singleton: membuat daftar dengan satu item, mengembalikan pointer ke sana insertAfter: diberi pointer ke item, memasukkan item baru setelahnya, mengembalikan pointer ke item baru delete:...
Ketika mencoba memperbaiki bug di perpustakaan, saya mencari makalah tentang menemukan subranges di pohon merah dan hitam tanpa hasil. Saya sedang mempertimbangkan solusi menggunakan ritsleting dan sesuatu yang mirip dengan operasi append yang biasa digunakan pada algoritma penghapusan untuk...
Pertanyaan ini terkait dengan salah satu pertanyaan saya sebelumnya, masalah NP-hard pada pohon . Saya mencari masalah yang P-lengkap di
Pertanyaan ini dimotivasi oleh pertanyaan yang diajukan pada stackoverflow . Misalkan Anda diberi rooted tree (yaitu ada root dan node punya anak dll) pada n node (berlabel 1 , 2 , … , n ).TTTnnn1,2,…,n1,2,…,n1, 2, \dots, n Setiap simpul memiliki bobot bilangan bulat non-negatif yang terkait: w i...
Blog ini berbicara tentang menghasilkan "labirin kecil berliku" menggunakan komputer dan menghitungnya. Pencacahan dapat dilakukan dengan menggunakan algoritma Wilson untuk mendapatkan UST , tapi saya tidak ingat rumus untuk berapa
Mencoba memungkinkan untuk penyimpanan efisien daftar elemen. Awalan dibagikan sehingga hemat ruang. Saya mencari cara yang sama untuk menyimpan pohon secara efisien. Saya ingin dapat memeriksa keanggotaan dan menambahkan elemen, mengetahui apakah pohon yang diberikan adalah subtree dari beberapa...
Saya telah membaca sedikit tentang struktur data berikut: Ideal Hash Tries dari Bagwell Tabel hash Dinamis Larson Pohon merah-hitam Pohon Patricia ... dan saya yakin ada banyak orang lain di luar sana. Saya telah melihat sangat sedikit di mana masing-masing lebih cocok untuk, atau mengapa saya...
Biarkan menjadi pohon biner yang di-root. Setiap jalur dari akar ke daun memiliki panjang . Setiap simpul selalu memiliki simpul anak kiri dan kanan tetapi ada kemungkinan bahwa keduanya sama (Jadi selalu ada jalur yang mungkin). Ukuran dibatasi oleh . Sebuah simpul dengan simpul anak yang berbeda...
Saya memiliki dataset pohon yang besar dan saya ingin mencarinya dengan menentukan treelet (subgraph yang terhubung). Kueri harus mengembalikan semua kemunculan treelet dalam dataset. Apakah ada algoritma yang efisien untuk melakukannya? Saya sedang memikirkan sesuatu seperti susunan sufiks,...
Saya mencari struktur data, yang pada dasarnya adalah pohon peta, di mana peta di setiap node berisi beberapa elemen baru, serta elemen-elemen di peta node induknya. Dengan peta di sini yang saya maksud adalah peta pemrograman dengan kunci dan nilai, seperti peta di STL atau dict dengan...