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

[問題] Graph mining

看板Prob_Solve (計算數學 Problem Solving)作者時間13年前 (2012/01/06 16:24), 編輯推噓3(3推 0噓 13→)
留言16則, 4人參與, 最新討論串1/1
假設今天給定一個graph G=(V,E) edge 與 node上面都有weighting 如果我今天要找k個點 讓這k個點之間的edge + node最大 有沒有什麼現有的演算法呢 謝謝 -- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.42.22
→
01/06 17:28, , 1F
請問之間的edge是指什麼? 至少其中一端點是這k個點的邊嗎?
01/06 17:28, 1F
推
01/07 11:12, , 2F
可以把node拆開成兩個,中間補上node的weight當成邊
01/07 11:12, 2F
→
01/07 11:13, , 3F
我想這個圖應該是DAG啦,如果是的話做DP最長路徑即可
01/07 11:13, 3F
→
01/07 11:14, , 4F
是說我也跟一樓有一樣的困惑....你點全部找的話不就醫定會
01/07 11:14, 4F
→
01/07 11:14, , 5F
大嗎?是不是你限制還是題意沒說清楚呀??
01/07 11:14, 5F
→
01/11 12:46, , 6F
edge的兩個端點都是k個點之中的 其實就是DkS的問題
01/11 12:46, 6F
→
01/11 12:46, , 7F
但是要加上node也有weighting
01/11 12:46, 7F
→
01/11 12:47, , 8F
flere大的問題 我想應該是我忘了說有n個node
01/11 12:47, 8F
→
01/11 12:48, , 9F
暴力法就是C(n,k) 但是不想用暴力QQ 謝謝
01/11 12:48, 9F
推
01/11 22:13, , 10F
我用谷割搜尋DkS problem　有找到投影片說這是NP-hard
01/11 22:13, 10F
→
01/11 22:14, , 11F
所以您需要的是近似演算法　還是特殊圖的演算法呢？
01/11 22:14, 11F
→
01/13 09:20, , 12F
謝謝熱心的D大 我想知道有沒有approximation
01/13 09:20, 12F
推
01/13 11:06, , 13F
有耶 我用谷歌搜尋DkS problem approximation 有一份投影片
01/13 11:06, 13F
→
01/13 11:07, , 14F
上面列的滿詳細的 不過我都看不懂就是了...
01/13 11:07, 14F
→
01/13 11:07, , 15F
01/13 11:07, 15F
→
02/21 22:15, , 16F
感謝!
02/21 22:15, 16F
‣ 更多 sayitagain 的文章
文章代碼(AID): #1F1g-v82 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sayitagain 的文章
文章代碼(AID): #1F1g-v82 (Prob_Solve)