[理工] 資工 101清大

[tkurockman (洛克人)]

http://imgur.com/DlW5NsF

我的想法是把它union 過的element標

記起來  因為一個set 只有2個element

如果union的set兩個element都是被標

記過的 就不取 直到所有宇集element都

被標記為止    但這樣好像不會是optimal

煩請解惑

--
Sent from my Android

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.128.105
→ kiki86151:這是NPC問題 跟vertex cover很像 可用近似演算法來解
推 FRAXIS:這應該是Edge cover吧.. 用maximum flow解
→ kiki86151:不是吧http://ppt.cc/2D20 也可參考Cormen 1117頁跟
→ kiki86151:vertex cover很像 你去看code就知道了 它放在近似演算
→ kiki86151:法那章 前面剛好就是講vertex cover
→ tkurockman:謝謝!
推 FRAXIS:當每個subset只有兩個時候是個特例  就變成edge cover..