[問題] 聚會的討厭對象

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (帕索)時間14年前 (2011/09/12 13:40), 編輯推噓10(1008)
留言18則, 7人參與, 最新討論串1/1
這是幫某人代po的文章: 假設有1號到100號總共100個人, 每個人都有一些固定討厭的對象。 每個人討厭的人數都不一定,每個人都不討厭自己。 例如12號討厭3個人,18號討厭6個人之類的。 而每個被討厭的人也都一定討厭那個討厭他的人。 (也就是說,在這個題目裡面「討厭」這個關係是對於雙方都成立的。 若3號討厭8號跟16號,那麼8號跟16號討厭的人裡面也一定有包括3號。 若a討厭b.則b也一定討厭a) 我不屬於這100個人裡面,我知道所有人他們所討厭的人的名單。 現在我的目標是要邀請到最多人數的人來參加聚會。 邀請的對象是誰不重要,重點是「邀請到最多人數,這些人彼此都不討厭對方」。 有什麼好方法可以簡單找到能邀請到最多人數的群體嗎? -- ~帕索板四徵兆~ 戰略高手 遊戲, 數位, 程設 PlayingGame 遊戲 Σ遊戲 棋藝 橋牌 謎  ○ * \○/ (○ Puzzle 益智 ◎ ╦╦└□ " ○□═ □  □> ║║√√ ╦══╦ ∥  |\ 歡樂帕索板 上B愛解謎 睡著還惦記 解完好開心 卡解傷腦筋 歡迎你一起來玩ψmaplemiracle -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.43.107

09/12 13:43, , 1F
邀到的人群裡面要有什麼限制好像沒講欸...?
09/12 13:43, 1F

09/12 13:44, , 2F
是不互相討厭嗎?
09/12 13:44, 2F

09/12 13:56, , 3F
這個是計算機科學裡所謂的 maximum independent set problem
09/12 13:56, 3F

09/12 15:22, , 4F
我也重覆看了好幾次....結果發現我看不懂....囧
09/12 15:22, 4F

09/12 15:33, , 5F
如果是的話就是LPH66大說的那樣沒錯XDDD
09/12 15:33, 5F

09/12 18:23, , 6F
所以 L 大 那樣算回答了問題了嗎?
09/12 18:23, 6F

09/12 19:40, , 7F
那句話的潛台詞是「這問題目前沒有"有效"解法」...
09/12 19:40, 7F

09/12 19:42, , 8F
以電腦程式(或更廣義叫演算法)來計算的話
09/12 19:42, 8F

09/12 19:42, , 9F
所需時間會隨著人數增加而成指數成長
09/12 19:42, 9F

09/12 19:43, , 10F
每個人討厭的人的人數不固定 <-- 這句是什麼意思??
09/12 19:43, 10F

09/12 19:44, , 11F
討厭的人數會變動??
09/12 19:44, 11F

09/12 19:45, , 12F
我猜這只是指像某A討厭三個某B討厭四個這種數量不等的情形
09/12 19:45, 12F

09/12 19:52, , 13F
我來改好了....
09/12 19:52, 13F
※ 編輯: puzzlez 來自: 123.194.43.107 (09/12 20:10)

09/12 23:05, , 14F
貪婪法不是n平方?
09/12 23:05, 14F

09/13 07:41, , 15F
邀請的情況是找100減M.I.S.(找差集合)? MISP是NPC問題阿
09/13 07:41, 15F

09/13 07:47, , 16F
但還是再找剩下中的MIS直到沒有"討厭"情況存在為止
09/13 07:47, 16F

09/13 10:55, , 17F
所以說最佳解沒有有效解法 找近似解的有效算法比較可行
09/13 10:55, 17F

01/04 16:22, , 18F
應該是每個人所討厭人的人數都不一定"相同"
01/04 16:22, 18F
文章代碼(AID): #1ERPjNrA (puzzle)
文章代碼(AID): #1ERPjNrA (puzzle)