推 FRAXIS:你一開始舉的例子的Cover是指cover edge 08/29 19:20
→ FRAXIS:但是你真的要問的問題是cover vertex 08/29 19:20
→ FRAXIS:可以搜尋一下Dominating Set 08/29 19:20
推 DJWS:這問題根本就是set cover problem 請愛用GA 08/29 19:25
→ yoco315:收到! 感謝以上兩位! 原來我觀念這麼不清楚 @@ 08/29 21:31
我知道 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