Re: 算法問題 (從N個set選m個包含最少的元素)
※ 引述《yauhh (喲)》之銘言：
舉個一次只換一個非最好的例子
S1={1,2,3}, S2={2,3,4},S3={1,3,4}, S4={5,6}, S5={5,6}, S6={5,6}
: : M=3好了, 選S4,S5,S6 最好
但假設一開始選到 S1,S2,S3開始.. 用S4, S5, S6 一個代換時
集合都會變成四個元素, 最好的只要兩個元素
但每次考慮多個, 除非所有c(M,N)全部組合都考慮才保證最好, 這樣就非polynomial了
: 借你這個例子,忽略掉你所問的推文問題,我的粗淺想法是:
: 1. 取指定集合數M: 在此為3.
: 2. 隨便取第一個M sets, 做一個binding B, 對應到M sets包含的全部元素:
: 取 S0={0}, S1={1}, S2={2} ===> B = { {S0, S1, S2}, {0, 1, 2} }
: 3. 取下一個集合 S4 = {1, 2}.
: 4. 問 S4 替換掉 S0, S1, S2 之一, 會不會減少M sets元素數目:
: 4-1. { {S4, S1, S2}, {1, 2} } 減少了元素數目.
: 4-2. { {S0, S4, S2}, {0, 1, 2} } 沒有減少元素數目.
: 4-3. { {S0, S1, S4}, {0, 1, 2} } 沒有減少元素數目.
: 4-4. 經過以上核對, 取 {S1, S2, S4} 為M sets.
: 5. 如果有其餘集合, 回到3.
: --------- 這個解決辦法的另一種解釋 -------------
: 取(N,M)組合,例如(8,3)組合,依序求聯集,看有沒有出現元素量更少的聯集:
: S0 S1 S2 S3 S4 S5 S6 S7
: * * * {0,1,2}
: * * * {0,1,3}
: * * * {0,1,2}
: ......
: * * * {1,2,4}
: 其中要用到的基礎運算單元就是聯集運算和差集運算了.
--
Life is continuous
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.151.93.115
※ 編輯: sorryChen 來自: 207.151.93.115 (06/02 11:05)
推
06/04 10:15, , 1F
06/04 10:15, 1F
→
06/04 10:28, , 2F
06/04 10:28, 2F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 8 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
