作者soheadsome (我是大帥哥)
看板Prob_Solve
標題[請益] 演算法作業的問題 (max weight subgraph)
時間Thu May 30 20:21:28 2013
因為期末要交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
1F：推 FRAXIS:搜尋 Maximum-Weight Connected Graph Problem 05/30 20:54
2F：→ FRAXIS:應該是NP-Complete問題 所以就只好找些Heuristic方法了 05/30 20:54
3F：→ soheadsome:不好意思 我只有看到幾篇論文 我平常很少碰論文 不知從 05/30 22:07
4F：→ soheadsome:何看起 05/30 22:07
5F：→ c2251393:這是一個NPC問題 可是你觀察一下他給的那張圖的樣子 05/31 10:55
6F：→ c2251393:他是一個長得有點像某個東西的圖 然後就可以有一個多項 05/31 10:56
7F：→ c2251393:式時間複雜度的演算法 05/31 10:57
8F：→ soheadsome:請問c2251393大大 你說的是MST 還是tree 可以再講詳細 05/31 18:51
9F：→ soheadsome:一點嗎? 感謝 05/31 18:52
10F：→ c2251393:他那個圖長得很像是一個二維矩陣 每個點連到周圍四個點 06/01 17:49
11F：→ c2251393:然後角落再插上一個點 但這不重要 06/01 17:52
12F：→ c2251393:然後你可以得到一個類似flood fill的演算法 06/01 17:54
13F：→ c2251393:就是你枚舉一個點 然後開始擴展 每次找與你這個子圖相鄰 06/01 17:55
14F：→ c2251393:最好的點 加入子圖中 06/01 17:56
15F：→ c2251393:詳細的作法可以參考 JOI '08-'09 本選 認証レベル 這一題 06/01 17:59
16F：→ c2251393:只不過這題是有兩個矩陣 然後各找一個連通子圖使得權值總 06/01 18:00
18F：→ soheadsome:c2251393大大 不曉得我的想法是不是跟你想得差不多 我 06/02 01:18
19F：→ soheadsome:想說用BFS一層到某點所相連的其他點 之後再從BFS到的 06/02 01:20
20F：→ soheadsome:的點 在做DFS找該被加入的點 然後遞迴的做(這應該是DP) 06/02 01:20
21F：→ soheadsome:我演算法學得不是很好= = 06/02 01:21