npc問題與近似算法-資料下載頁
2025-10-08 23:47本頁面
【導讀】如果問題X滿足以下條件，那么X屬于NPC。CNF問題聯系起來？時擁有m臺機器。這是一個2倍近似算法。每次選擇一個未安排的工作中用時最多的，每次假設圖的radius，然后。給定一個無向圖G(V,E). 給定一組二元組T={,…
【正文】 ...11( ... 1 )1*iittSol ut i on W WXXXOPTn n X n X XOPTnnOPT Hn?? ? ?? ? ? ?? ? ? ?? ? ? ???Approximation Algorithm 例 5： Edge Disjoint Path(EDP) 問題描述： ?給定一個無向圖 G(V,E) ?給定一組二元組 T={(s1,t1),…( sk,tk)} ?目標：尋找盡可能多的不相交道路使得這些道路起終點為給定二元組。 Approximation Algorithm ?算法 網絡流？ 不行 ?網絡流無法保證 Si以 Ti為終點 ?尋找近似算法 Approximation Algorithm ?近似算法 repeat pick an index i . the shortest path Pi from si to ti is shortest delete Pi from the graph THM：這個算法是一個 近似算法 mApproximation Algorithm 例 5：背包問題 ?算法：對于給定的常數 c, k= ?在改變價值的情況下用 DP解決（ polytime），得到 Soltuion nc??????m a x? ii ppkp?????Approximation Algorithm ?在未改變的情況中選擇 Solution中的元素得到我們的近似解 ?THM：這是一個（ 1+c）近似算法 Thank you Approximation Algorithm 更多的問題： ?旅行商問題 ?最大割問題 ?斯特林樹問題
教學課件相關推薦
鄂ICP備17016276號-1