npc問題與近似算法-文庫吧資料
2024-10-25 23:47本頁面
【正文】 Clique p?Reducibility of NPCompleteness 令 為一個 k子句的 3CNF ，且 12 ... kC C C? ? ? ? ?1 2 3rrrrC l l l? ? ?我們如何構建一幅圖 G(V,E)將圖的團和 3CNF問題聯(lián)系起來？ Reducibility of NPCompleteness Reducibility of NPCompleteness 對于每個子句 ，我們在圖中添加 3個結點 ，如果結點 滿足以下兩個條件，就連邊： 1. 2. 1 2 3rrrrC l l l? ? ?1 2 3,rrrVVV ,rsijVVij?rsijll??Approximation Algorithm 例 1： Load Balancing Problem 問題描述： 1. 給定ｎ個工作，工作ｊ需要時間 tj，同時擁有 m臺機器。 VC IS Definition of NPCompleteness ?p? p?? Vertex Cover Set Cover SC: Given a set U of elements,a collection M of subset of U S1,S2… Sn,and a integer k,ask if Definition of NPCompleteness Example2： p?[ ] , amp。NPC問題與近似算法 林衍凱 ?定義 : 如果一個問題 Y可以通過調用問題 X且通過 polytime的時間轉化得到，我們稱： D
教學課件相關推薦
鄂ICP備17016276號-1