PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[請益] The Maximum Independent Set Problem

看板Prob_Solve (計算數學 Problem Solving)作者 (十三)時間12年前 (2012/02/25 10:36), 編輯推噓6(6推 0噓 9→)
留言15則, 3人參與, 最新討論串1/2 (看更多)
參考 http://www.dharwadker.org/independent_set/ 並根據演算法實作自己的版本。 http://codepad.org/smRwl6MZ http://pastie.org/3451941 測試題目是SPOJ3196 http://www.spoj.pl/problems/DIVREL/ 目前仍是TLE。 想請教有沒有更快的演算法，謝謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.25.249.107
推
02/25 12:29, , 1F
你給的那個參考應該是錯的 目前還沒有P-time演算法
02/25 12:29, 1F
→
02/25 13:10, , 3F
這個不知行不行 最大獨立集/最大團是精典題型 資料滿好找
02/25 13:10, 3F
→
02/25 13:29, , 4F
02/25 13:29, 4F
→
02/25 13:51, , 5F
http://codepad.org/RnS4AGFJ 改blog程式丟上去還是TLE
02/25 13:51, 5F
→
02/25 13:52, , 6F
另外如果上面程式#define改0去跑參考的最後一個圖
02/25 13:52, 6F
→
02/25 13:52, , 7F
450個點，跑5分鐘還不會有結果。 不過還是很感謝。
02/25 13:52, 7F
推
02/25 14:06, , 8F
我回文在下面了~
02/25 14:06, 8F
→
02/25 14:07, , 9F
另外 maximal是局部最大(greedy method) maximum才是全域最大
02/25 14:07, 9F
→
02/25 14:08, , 10F
標題下的不太正確 因為這題是求maximum而非maximal
02/25 14:08, 10F
→
02/25 14:16, , 11F
我改一下。
02/25 14:16, 11F
推
02/28 01:15, , 12F
他給的參考沒說是P-time演算法，只說是目前最有希望達成
02/28 01:15, 12F
推
02/28 01:16, , 13F
在P-time解掉NPC的演算法 = =
02/28 01:16, 13F
推
02/28 01:19, , 14F
所以這參考應該是對的 XD
02/28 01:19, 14F
推
02/28 13:05, , 15F
唔 那就是我搞錯了 抱歉 orz
02/28 13:05, 15F
‣ 更多 bleed1979 的文章
文章代碼(AID): #1FI4a-g8 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bleed1979 的文章
文章代碼(AID): #1FI4a-g8 (Prob_Solve)