› 看板 puzzle 關於我們 聯絡資訊
作者puzzlez (帕索)
看板puzzle
標題[問題] 聚會的討厭對象
時間Mon Sep 12 13:40:35 2011
這是幫某人代po的文章： 假設有1號到100號總共100個人， 每個人都有一些固定討厭的對象。 每個人討厭的人數都不一定，每個人都不討厭自己。 例如12號討厭3個人，18號討厭6個人之類的。 而每個被討厭的人也都一定討厭那個討厭他的人。 （也就是說，在這個題目裡面「討厭」這個關係是對於雙方都成立的。 若3號討厭8號跟16號，那麼8號跟16號討厭的人裡面也一定有包括3號。 若a討厭b.則b也一定討厭a） 我不屬於這100個人裡面，我知道所有人他們所討厭的人的名單。 現在我的目標是要邀請到最多人數的人來參加聚會。 邀請的對象是誰不重要，重點是「邀請到最多人數，這些人彼此都不討厭對方」。 有什麼好方法可以簡單找到能邀請到最多人數的群體嗎？ -- ~帕索板四徵兆~ 戰略高手 遊戲, 數位, 程設 PlayingGame 遊戲 Σ遊戲 棋藝 橋牌 謎 　○ ！ * \○/ ★ (○ ？ Puzzle 益智 ◎ ╦╦└□ " ○□═ □ 　□> ║║√√ ╦══╦ ∥ 　|\ 歡樂帕索板 上Ｂ愛解謎 睡著還惦記 解完好開心 卡解傷腦筋 歡迎你一起來玩ψmaplemiracle -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.43.107
推 arthurduh1:邀到的人群裡面要有什麼限制好像沒講欸...? 09/12 13:43
→ arthurduh1:是不互相討厭嗎? 09/12 13:44
推 LPH66:這個是計算機科學裡所謂的 maximum independent set problem 09/12 13:56
→ puzzlez:我也重覆看了好幾次....結果發現我看不懂....囧 09/12 15:22
推 arthurduh1:如果是的話就是LPH66大說的那樣沒錯XDDD 09/12 15:33
→ puzzlez:所以 L 大 那樣算回答了問題了嗎？ 09/12 18:23
推 LPH66:那句話的潛台詞是「這問題目前沒有"有效"解法」... 09/12 19:40
→ LPH66:以電腦程式(或更廣義叫演算法)來計算的話 09/12 19:42
→ LPH66:所需時間會隨著人數增加而成指數成長 09/12 19:42
→ caago123:每個人討厭的人的人數不固定 <-- 這句是什麼意思?? 09/12 19:43
→ caago123:討厭的人數會變動?? 09/12 19:44
推 LPH66:我猜這只是指像某A討厭三個某B討厭四個這種數量不等的情形 09/12 19:45
→ puzzlez:我來改好了.... 09/12 19:52
※ 編輯: puzzlez 來自: 123.194.43.107 (09/12 20:10)
推 joeyeh:貪婪法不是n平方? 09/12 23:05
推 joeyeh:邀請的情況是找100減M.I.S.(找差集合)? MISP是NPC問題阿 09/13 07:41
推 joeyeh:但還是再找剩下中的MIS直到沒有"討厭"情況存在為止 09/13 07:47
推 walkwall:所以說最佳解沒有有效解法 找近似解的有效算法比較可行 09/13 10:55
推 e7410akgb:應該是每個人所討厭人的人數都不一定"相同" 01/04 16:22