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 ).
Setiap simpul memiliki bobot bilangan bulat non-negatif yang terkait: w i .
Selain itu, Anda diberi bilangan bulat , sehingga 1 ≤ k ≤ n .
Berat dari satu set node S ⊆ { 1 , 2 , ... , n } adalah jumlah dari bobot dari node: Σ s ∈ S w s .
Diberikan input , w i dan k ,
Tugasnya adalah untuk menemukan sub-hutan berat minimum * , dari T , sehingga S memiliki simpul k yang tepat (yaitu | S | = > k ).
Dengan kata lain, untuk setiap sub hutan dari T , sedemikian rupa sehingga | S ′ | = k , kita harus memiliki W ( S ) ≤ W ( S ′ ) .
Jika jumlah anak dari setiap node dibatasi (misalnya pohon biner), maka ada algoritma waktu polinomial menggunakan pemrograman dinamis.
Saya punya perasaan bahwa ini NP-Hard untuk pohon umum, tetapi saya belum dapat menemukan referensi / bukti. Saya bahkan melihat ke sini , tetapi tidak dapat menemukan sesuatu yang dapat membantu. Saya merasa bahwa ini akan tetap NP-Hard bahkan jika Anda membatasi (dan ini mungkin lebih mudah untuk dibuktikan).
Ini sepertinya masalah yang harus dipelajari.
Apakah ada yang tahu jika ini adalah masalah NP-Hard / ada algoritma waktu P yang dikenal?
* Sub-hutan adalah subset S dari simpul pohon T , sehingga jika x ∈ S , maka semua anak-anak x berada di S juga. (Yaitu itu adalah penyatuan terpisah dari sub-pohon berakar T ).
PS: Maafkan saya kalau ternyata saya ketinggalan sesuatu yang jelas dan pertanyaannya benar-benar diluar topik.
Jawaban:
sumber