Apakah NP-keras ini? Saya tidak bisa membuktikannya.

11

Saya punya masalah dan saya kira itu NP-hard, tapi saya tidak bisa membuktikannya.

Berikut ini adalah grafik lapisan, di mana lapisan 0 adalah lapisan paling tebal dan lapisan L terendah.

ada beberapa tepi diarahkan antara lapisan, di mana tepi (A, B) menunjukkan bahwa simpul A dapat [menutupi] simpul B. Dan ketika A dapat menutupi B, setiap simpul di jalur mana pun dari A ke B dapat menutupi B, B dapat menutupi diri.

Akhirnya di sini datang satu set simpul S. Saya perlu memilih satu set simpul ANS, dan memastikan bahwa untuk setiap simpul q di S, ada simpul p di ANS dan p meliputi q.

Untuk setiap node ada biaya, dan saya perlu membuat total biaya set ANS minimal.

Apakah ini masalah NP-hard? Saya pikir begitu tetapi saya tidak bisa membuktikannya.

Bisakah kamu membantuku?

Terima kasih banyak.

graphs np qin.sun
sumber
biaya simpul dari lapisan atas lebih mahal di setiap jalur dalam grafik.
Ya memang sepertinya NP sulit. Lihatlah masalah penutup minimal yang serupa. en.wikipedia.org/wiki/Set_cover_problem
Apakah ada batasan di tepi terarah, seperti tepi hanya menghubungkan sebuah simpul di lapisan yang lebih tinggi ke sebuah simpul di lapisan bawah? Bisakah saya mengklarifikasi bahwa tidak ada tepi antara node di lapisan yang sama?
justhalf
@ justhalf Tidak, tidak ada tepi antara node di lapisan yang sama. Terima kasih :)
qin.sun

Jawaban:

6

Ya masalah ini pasti sulit NP. Saya memposting jawaban ini karena Anda memerlukan bukti.

Jika Anda mengikuti tautan ini http://en.wikipedia.org/wiki/Set_cover_problem , dikatakan bahwa versi pengoptimalan masalah penutup minimal adalah NP-Hard.

Masalah dalam tautan:

Diberikan satu set elemen {1,2, ..., m} (disebut alam semesta) dan himpunan S of n himpunan yang persatuannya sama dengan jagat raya, masalah himpunan himpunan adalah untuk mengidentifikasi himpunan bagian terkecil S yang persatuannya sama dengan alam semesta. Sebagai contoh, perhatikan alam semesta U = {1, 2, 3, 4, 5} dan himpunan himpunan S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Jelas bahwa penyatuan S adalah U. Namun, kita dapat mencakup semua elemen dengan jumlah set berikut yang lebih kecil: {{1, 2, 3}, {4, 5}}

Anda dapat menghubungkan ini dengan masalah Anda sebagai berikut:

S adalah himpunan node yang mencakup setidaknya satu node di set input Anda. Ini dapat ditemukan dengan melakukan DFS pada node input set dengan arah tepi terbalik.

Sekarang masalah yang dijelaskan dalam tautan adalah kasus khusus dari masalah Anda, di mana biaya setiap node sama dan Anda hanya ingin meminimalkan jumlah node (set).

Karenanya masalah Anda bahkan lebih sulit untuk dipecahkan dalam kasus umum dan karenanya NP Hard.

Abhishek Bansal
sumber
Saya pikir ini benar dengan definisi OP, tetapi ia juga tidak pernah menentukan apakah Anda dapat "menutupi" sebuah simpul dengan tepi di lapisan yang sama dengan simpul itu. Jika itu masalahnya, maka masalahnya tampaknya sedikit berbeda. Jika tidak, jika Anda hanya dapat menutupi sebuah simpul melalui tepi dari lapisan yang lebih tinggi maka itu tampaknya setara dengan mengatur optimasi penutup
roliu
@roliu Bagaimana bedanya apakah layer node yang sama dapat ditutup atau tidak. Masalah yang saya mengerti adalah bahwa kita memiliki grafik yang diarahkan dengan jalur antara simpul A ke B berarti bahwa A mencakup B.
Hm, saya tidak yakin. Ini aneh karena saya tidak berpikir bahwa hampir semua informasi dalam OP sebenarnya berguna. Lapisan tampaknya tidak relevan dan transitivitas. Saya kebanyakan hanya menunggu OP untuk mengklarifikasi bahwa dia sebenarnya berarti sesuatu yang berbeda. Secara khusus, Anda dapat menunjukkan bahwa itu tidak hanya sekuat set penutup, tetapi sebenarnya setara. Karena setiap penutup minimal dalam masalah OP hanya akan berisi node tetangga set inputnya S. Mungkin ada biaya negatif atau sesuatu seperti itu ...
roliu