[請益] 演算法作業的問題 (max weight subgraph)

看板Prob_Solve作者 (我是大帥哥)時間11年前 (2013/05/30 20:21), 編輯推噓1(1推 0噓 20→)
留言21則, 3人參與, 最新討論串1/1
因為期末要交project, 但題目看很久不知道該怎麼從哪下手, google很久 只看到說可以轉成prize-collecting Steiner tree 所以想請教大大們,可不可以給我一些提示 感謝 附題目ppt: https://www.asuswebstorage.com/navigate/s/53DE46AEC6CD41C99D3A3CDAC7318B49Y 在網路上找到相關內容的ppt: https://www.asuswebstorage.com/navigate/s/34D9CE30384C48759D2E8A3713C1F3ADY -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.122.217.24
推
05/30 20:54, , 1F
搜尋 Maximum-Weight Connected Graph Problem
05/30 20:54, 1F
→
05/30 20:54, , 2F
應該是NP-Complete問題 所以就只好找些Heuristic方法了
05/30 20:54, 2F
→
05/30 22:07, , 3F
不好意思 我只有看到幾篇論文 我平常很少碰論文 不知從
05/30 22:07, 3F
→
05/30 22:07, , 4F
何看起
05/30 22:07, 4F
→
05/31 10:55, , 5F
這是一個NPC問題 可是你觀察一下他給的那張圖的樣子
05/31 10:55, 5F
→
05/31 10:56, , 6F
他是一個長得有點像某個東西的圖 然後就可以有一個多項
05/31 10:56, 6F
→
05/31 10:57, , 7F
式時間複雜度的演算法
05/31 10:57, 7F
→
05/31 18:51, , 8F
請問c2251393大大 你說的是MST 還是tree 可以再講詳細
05/31 18:51, 8F
→
05/31 18:52, , 9F
一點嗎? 感謝
05/31 18:52, 9F
→
06/01 17:49, , 10F
他那個圖長得很像是一個二維矩陣 每個點連到周圍四個點
06/01 17:49, 10F
→
06/01 17:52, , 11F
然後角落再插上一個點 但這不重要
06/01 17:52, 11F
→
06/01 17:54, , 12F
然後你可以得到一個類似flood fill的演算法
06/01 17:54, 12F
→
06/01 17:55, , 13F
就是你枚舉一個點 然後開始擴展 每次找與你這個子圖相鄰
06/01 17:55, 13F
→
06/01 17:56, , 14F
最好的點 加入子圖中
06/01 17:56, 14F
→
06/01 17:59, , 15F
詳細的作法可以參考 JOI '08-'09 本選 認証レベル 這一題
06/01 17:59, 15F
→
06/01 18:00, , 16F
只不過這題是有兩個矩陣 然後各找一個連通子圖使得權值總
06/01 18:00, 16F
→
06/01 18:01, , 17F
和最大 官方題解(日文) : http://tinyurl.com/mwpvkxu
06/01 18:01, 17F
→
06/02 01:18, , 18F
c2251393大大 不曉得我的想法是不是跟你想得差不多 我
06/02 01:18, 18F
→
06/02 01:20, , 19F
想說用BFS一層到某點所相連的其他點 之後再從BFS到的
06/02 01:20, 19F
→
06/02 01:20, , 20F
的點 在做DFS找該被加入的點 然後遞迴的做(這應該是DP)
06/02 01:20, 20F
→
06/02 01:21, , 21F
我演算法學得不是很好= =
06/02 01:21, 21F
‣ 更多 soheadsome 的文章
文章代碼(AID): #1HfqHBSo (Prob_Solve)