[問題] covering problem 的變形
看板Prob_Solve (計算數學 Problem Solving)作者yoco315 (眠月)時間12年前 (2012/08/29 13:02)推噓3(3推 0噓 3→)留言6則, 3人參與討論串1/1
我知道 covering problem 是 NP-complete http://tinyurl.com/2aj7953OB
也知道 bipartite covering problem 是 P http://tinyurl.com/3wazas
我想問的是：給定一個 bipartite graph G(V1, V2, E)
V1, V2 是 bipartite 的兩個 vertex set，
如果我希望在 V1 裡面找到一組最小的 set 經過 E 來 cover V2，
請問這個問題有名字嗎？請前輩給小弟一些方向或是關鍵字，多謝 :)
我自己有粗想一下，一開始很直覺反應認為就是 covering problem，
但是因為看到 bipartite covering problem 是 P 以後，
有點好奇這個問題是不是也有機會不用到 NP-complete，
我有查到一個叫做 Constrainted Bipartite Covering Problem，
說限制在 V1 裡面最多取 k1，V2 裡面最多取 k2，這是 NP-Complete，
我的問題雖然可以轉成 CBCP，但又有點不一樣，目前還沒想法 :(
因為不要求一定要 exactly minimum，
如果沒有 P 的話，我就考慮使用 GA 去解了……
再次謝過 :)
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.71.72.108
推
08/29 19:20, , 1F
08/29 19:20, 1F
→
08/29 19:20, , 2F
08/29 19:20, 2F
→
08/29 19:20, , 3F
08/29 19:20, 3F
推
08/29 19:22, , 4F
08/29 19:22, 4F
推
08/29 19:25, , 5F
08/29 19:25, 5F
→
08/29 21:31, , 6F
08/29 21:31, 6F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
