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

[問題] 一個關於演算法的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (Ben)時間13年前 (2011/06/08 23:55), 編輯推噓3(3推 0噓 6→)
留言9則, 2人參與, 最新討論串1/1
大家好, 最近在解一個有關圖學理論的問題, 描述如下: 問題描述如下: 給一圖G(V,E) V為帶有一個整數權重的點, E為空集合. 要增加E, 有以下限制: 1. 每條路徑的長度必為2條edges, 且不形成circle 2. 每個Vertex只可交會0,1,2條edges 3. 每條路徑上的3個Vertices的權重合必>=0 求一組擁有最多條路徑的路徑分佈情形 簡單的說就是求一個有最多條路徑的路徑分布, 限制為每條路徑通 通都是三個vertices和兩條edges, 然後路徑上的vertices權重和要>=0 我找了一些graph theory的演算法, 像Matching, coloring, 但似乎解 決不了(或許可以, 我這方面知識較缺乏). 想請教大家有沒有推薦的 解決方向或是可以對應到一個已知的解決方法, 謝謝大家. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.5.201
推
06/09 00:14, , 1F
就算沒有 weight, 這是所謂的 max. P_3 packing problem,
06/09 00:14, 1F
→
06/09 00:15, , 2F
即使在平面圖上都是 NP-complete. 你的圖有特殊性質嗎?
06/09 00:15, 2F
推
06/09 00:19, , 3F
用 local search 可以有 1/2-eps 的近似演算法.
06/09 00:19, 3F
→
06/09 00:20, , 4F
可參考 "On Local Search for Weighted k -Set Packing",
06/09 00:20, 4F
→
06/09 00:20, , 5F
by Esther M. Arkin and Refael Hassin.
06/09 00:20, 5F
推
06/09 00:26, , 6F
另外, 可以注意到就算是亂挑也會是個 1/3 近似演算法,
06/09 00:26, 6F
→
06/09 00:27, , 7F
因為每一條 path 最多破壞另外三條 paths.
06/09 00:27, 7F
→
06/09 00:29, , 8F
太強大了!! 感謝樓上的資訊!! 拜讀提供的那篇Paper中
06/09 00:29, 8F
→
06/09 01:12, , 9F
感謝h大提供資料, 剛剛被我煩還耐心解答, 真是謝謝了.
06/09 01:12, 9F
‣ 更多 bin90909 的文章
文章代碼(AID): #1Dxvj--v (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bin90909 的文章
文章代碼(AID): #1Dxvj--v (Prob_Solve)