創新實訓個人記錄：approximation factor, maximum matching&&vertex cover

• approximation factor（近似比）
• maximum matching&&minimum vertex cover
• • maximum matching（最大匹配）
  • vertex cover（點覆蓋）
• approximate algorithm on vertex cover（點覆蓋問題的近似算法）
• • approximate algorithm（近似算法）
  • • 先找OPT下界：極大匹配提供了點覆蓋問題的下界
    • 近似算法
  • approximate factor（近似因子）

approximation factor（近似比）

近似比是近似算法所得的近似解與最優解OPT的比值。我們想用近似算法找到NP問題的近似解，需要通過近似比來論證近似算法的優秀。但是，對于NP問題，我們找不到OPT，又如何得到近似比呢？
這里涉及到近似算法中求近似比的通用原則，讓我們不知道OPT也可以求近似比，即先求OPT的下界，再找到一個近似算法，要求這個算法能求得與下界成常數倍關系的近似解。比如，OPT≥a，c·OPT≥c·a；那么我們需要找到一個近似算法求得近似解c·a，此時有c·a/OPT≤c·OPT/OPT=c，我們稱近似比為c。

maximum matching&&minimum vertex cover

maximum matching（最大匹配）

matching：匹配。給定一個圖H =(U,F)，一個邊集M ? F，如果M中沒有兩條邊共享一個端點，即M中任意兩條邊都不交于一個點，那么M被稱為是一個匹配。
maximum matching：最大匹配。最大基數匹配，即這樣的匹配可以找到的匹配邊數是最多的。

maximal matching：極大匹配。我們不能再找到圖H中的任何一條邊，添加到匹配中仍滿足匹配條件。

vertex cover（點覆蓋）

給定一個無向圖G=(V,E), 有一個成本函數：V→ Q+，找到最小成本點覆蓋，即一個集合V’? V，對于V’，G中每條邊至少有一個端點在V’中，這樣的V’就是一個點覆蓋，我們要找到最小的點集V’，即最小成本點覆蓋。在所有點都是單位成本的情況下，我們稱點覆蓋問題為基數點覆蓋問題。（這本書定義的“點覆蓋”直接是最小成本點覆蓋，這個問題還沒有被證明是NP問題。）

approximate algorithm on vertex cover（點覆蓋問題的近似算法）

approximate algorithm（近似算法）

先找OPT下界：極大匹配提供了點覆蓋問題的下界

極大匹配：如果再加任意一條邊到匹配中，那么一定會有至少一條邊與新加入的邊交于一個點。
下界：任何的點覆蓋都不得不至少選擇每個極大匹配邊的一個端點。

• 我們按照極大匹配把一個圖分成匹配邊和未匹配邊，那么任意一個點覆蓋必定包含匹配邊的一個端點，不然這個點覆蓋就無法覆蓋這個匹配邊，那么就不是一個點覆蓋。
• 如果不是所有匹配邊和未匹配邊都交于一個點的話，點覆蓋還需要包含未匹配邊的端點，那么點覆蓋的點集的點的數目必定是大于等于極大匹配的邊集的邊的數目。（如下圖，即不是匹配邊和未匹配邊都交于一個點。）
  
• 理所當然地，也大于等于非極大匹配的邊集的邊的數目。所以，我們有：所有的匹配對應的邊集中邊的數目總是小于等于所有的點覆蓋對應的點集中點的數目，匹配的邊集的邊數是點覆蓋的點集的點數的下界。更緊地，極大匹配的邊集的邊數是最小點覆蓋的點集的點數的下界。

近似算法

找到圖G中的一個極大匹配，輸出極大匹配的點集。

approximate factor（近似因子）

近似比為2。 也就是說，該近似算法所得出的解是個可行解，而且這個可行解的成本一定在這個問題的最優解的成本的2倍之內，也就是我們要證極大匹配的點集（極大匹配邊的左右端點），一定在最小基數點覆蓋的點集的2倍內。

證明：

• 如果是極大匹配的點集，那么一定是覆蓋了所有邊的至少一個端點，否則的話，可以再加一條沒有被覆蓋的邊進入匹配中成為更大的匹配。我們現在讓M作為極大匹配所選擇的邊集。
• 之前我們已推出 |M|≤OPT，即所有的匹配對應的邊集中邊的數目總是小于等于所有的點覆蓋對應的點集中點的數目，最大的匹配中邊的數目≤最小點覆蓋中點的數目。K?nig’s theorem: 在二分圖中，最大的匹配的邊集中邊的數目等于最小點覆蓋的點集中點的數目）
• 我們觀察得，這種算法選擇的覆蓋，由于匹配的邊為|M|,每條邊左右兩個端點，那么對應的覆蓋點數為2|M|,因為|M|≤OPT，所以2|M|≤2·OPT，即依靠下界方案得到的最大的匹配的點集（匹配邊的左右端點）≤最小點覆蓋的點集的2倍/最優解的2倍，最大的匹配的點集/最小點覆蓋的點集≤2。

總結

以上是生活随笔為你收集整理的创新实训个人记录：approximation factor, maximum matchingvertex cover的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。