劉子韬
這裡主要是介紹一種證明貪心算法是最優的一種方法：Exchange Argument （不知道應該怎麼翻譯到中文，交換參數？感覺聽起來挺別扭的，不像是一個方法的名字~o(╯□╰)o）
Exchange Argument的主要的思想也就是 先假設 存在一個最優的算法和我們的貪心算法最接近，然後通過交換兩個算法裡的一個步驟(或元素)，得到一個新的最優的算法，同時這個算法比前一個最優算法更接近於我們的貪心算法，從而得到矛盾，原命題成立。
下面來看一個更為formal的解釋：
步驟：
Step0: 給出貪心算法A的描述
Step1: 假設O是和A最相似(假設O和A的前k個步驟都相同，第k+1個開始不同，通常這個臨界的元素最重要)的最優算法
Step2: [Key] 修改算法O(用Exchange Argument，交換A和O中的一個元素)，得到新的算法O’
Step3: 證明O’ 是feasible的，也就是O’是對的
Step4: 證明O’至少和O一樣，即O’也是最優的
Step5: 得到矛盾，因為O’ 比O 更和A 相似。
證畢。
當然上面的步驟還有一個變種，如下：
Step0: 給出貪心算法A的描述
Step1: 假設O是一個最優算法（隨便選，arbitrary）
Step2: 找出O和A中的一個不同。（當然這裡面的不同可以是一個元素在O不再A，或者是一個pair的順序在A的和在O的不一樣。這個要根據具體題目）
Step3：Exchange這個不同的東西，然後argue現在得到的算法O 不必O差。
Step4: Argue 這樣的不同一共有Polynomial個，然後我exchange Polynomial次就可以消除所有的不同，同時保證了算法的質量不比O差。這也就是說A 是as good as 一個O的。因為O是arbitrary選的，所以A是optimal的。
證畢
下面給幾個例子：
例 Maximum Cardinality Disjoint Interval Problem
問題描述：給一些時間片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一個元素個數最多的子集S，子集中的每個元素的時間片段沒有交叉。
Greedy Algorithm: 每次都選所有interval 中bi最小的那個，把（ai，bi）加入S，然後把（ai，bi）在T中刪除，同時把T中所有和（ai，bi）有交叉的interval刪除，然後再在T中找最小的bj，循環上面的操作，直到沒有可以在添加的。
證明上面說的Greedy Algorithm是最優的。
下面就用第一個證明的步驟來證。
我們的Greedy Algorithm記為A，假設A不是最優的，那麼就一定存在一個O，O是和A最相近的一個最優的算法，最相近是指和O和A的前K-1個選擇都相同，第K個是不同的。
假設對於A，A第k個選擇的是（ai，bi）；而O第K個選擇的是（aj，bj）。從A的定義我們可以直到，bi<=bj。
現在我們構造一個O，O = O-（aj，bj）+（ai，bi）。
1）很顯然，O是這個問題的一個解，也就是說O中的intervals沒有重疊的。
在O中，（ai，bi）前的intervals和A中的一樣，所以前一部分沒有重疊。在（ai，bi）後的intervals和O中的一樣，所以也沒有重疊，同時bi<=bj，所以（ai，bi）也不會和它相鄰的重疊，所以O中的所有intervals都沒有重疊。
2）O是一個最優解，因為他的intervals的個數和O一樣。
綜上，我們找到了一個最優解O，它和A具有的共同的intervals有K個，這和我們前提假設最多有k-1個相矛盾，所以，A是最優的。證畢。
例 Scheduling with Deadline
問題描述：有一系列的tasks{a1，a2，。。。，an}，每個task需要在cpu上跑{p1，p2，。。。，pn}個units的時間，cpu是非搶占式的，也就是task一旦獲得cpu，就運行直到他完成，{c1，c2，。。。，cn}是每個task的完成時間，我們現在要minimize的就是 （c1+c2+。。。+cn）/n。所有的task一起release。
Greedy Algorithm：每次選運行時間最小的那個task運行。
證明上面說的Greedy Algorithm是最優的。
同樣還是用第一個證明的步驟來證。
假設A不是最優的，那麼一定存在一個最優的O，和A最接近，他們選擇的前k-1個task是相同的。
如下：
No. 1 2 3 。。。 k 。。。。。。。。。
A 。。。。。。。。。。。 ai 。。aj 。。。。。
O 。。。。。。。。。。。 aj 。。。。ai 。。。
根據A的定義，我們知道，pi <= pj的。
現在我們就來構造O，當然，O就是把O中的ai和aj兩個元素交換一下，即
No. 1 2 3 。。。 k 。。。。。t。。。
A 。。。。。。。。。。。 ai 。。aj 。。。。。
O 。。。。。。。。。。。 aj 。。。。ai 。。。
O 。。。。。。。。。。。 ai 。。。。aj 。。。
對於整個的完成時間，我們可以給出計算公式的，假設b1，b2，。。。，bn是一個調度序列（bi是task的index，也就是{bi}是所有task的index的一個permutation），即task執行順序是a_{bi},a_{b2}, ..., a_{bn}。舉個例子如果只有5個task，a1,a2,a3,a4,a5。{bi} = {2,1, 3, 5, 4},那也就是task的執行序列為 a2,a1,a3,a5,a4。(博客裡面不能打數學公式就是不爽啊~)
還是用上面的5個例子算了，對於a2,a1,a3,a5,a4，我們知道總時間其實是5個a2的時間，即p2，4個a1的時間，即p1，依次類推，所以總時間是5*p2+4*p1+3*p3+2*p5+p4。
好，有了上面的計算總時間的概念，下面就來分別計算一下O和O的總時間，其實我們需要比較它們誰大誰小，通常只要比較一下他們的差就行了，即Time(O)-Time(O)。同時很顯然，他們的差只是由aj和ai引起的，其他的並沒有改變。我們知道在O中，aj是第k個選的，ai是第t個選的，而在O中，ai是第k個選的，aj是第t個選的，所以 Time(O)-Time(O) = (n-k+1)*pj + (n-t+1)*pi - (n-k+1)*pi - (n-t+1)*pj = k*(pj-pi) - t*(pj-pi) = (pi-pj)*(k-t)>=0,即我們得到Time(O) >= Time(O),這也就是說我們找到了一個O，他是最優的，同時O和A有K個common element，所以得出矛盾。證畢。
例 Kruskal Algorithm for Minimum Spanning Tree（最小生成樹）
問題描述：對於邊集合E，先按每個邊的cost排序，從小到大，然後按如下方法構造一個MST，每次選cost最小的那個邊，添加進我們的MST，如果一個邊使我們現有的MST出現環路，則把這條邊捨棄，然後重復上面的操作。（感覺現在表達越來越搓了，沒看明白怎麼回事的童鞋看這裡吧 http://en.wikipedia.org/wiki/Kruskals_algorithm）
下面我們就用第二種證明方法來證明Kruskal Algorithm算法是最優的。
假設我們的graph是G(V,E)，有一個optimal的算法O，它生成的MST是T1，Kruskal生成的樹是T2，這樣，因為T2！=T1（如果相等我們的Kruskal就最優了，就不用證了），所以至少有一條邊e，e在T1中，同時e不在T2中。這個與眾不同的e就是我們的切入點。可以想象，如果我們把e在T1中去掉，T1就變成了兩部分，即Ta和Tb，我們知道 {Ta中的點}V{Tb中的點} = V（就是Ta中的點並上Tb中的點就是我們G中的點集V），所以在T2中，一定有一條邊f（f！=e），f的一個點在{Ta中的點}，f的另一個點在{Tb中的點}。根據我們的Greedy算法Kruskal，我們沒有選e，是因為e在我們的圖中造成了回路。在進一步想，有回路是因為我們先選了f，這就說明cost(f) <= cost(e)。 （恩，這就是我們的重點啊，笑一個O(∩_∩)O~）
下面的也就很顯然了，我們考慮構造一棵新的樹，T3，對於T3 = E(T1) - e + f，也就是T3中的邊是T1中的所有邊除了e，同時加上邊f。
1）很顯然，我們知道T3是一棵spanning tree，f連通了由去掉e而分隔的兩部分。
2）很顯然，T3的cost是<= T1的cost的。 因為cost(f) <= cost(e)，且其他不變。即T3是MST。
所以同個上面的構造，我們就構造出了一棵樹，這個樹是MST，同時它比T1更接近於T2。（多了一條common的邊）
我們知道T1和T2對多有n條邊是不同的，通過上面的步驟，我們可以經過n次變換，得到T2，同時cost <=T1，所以，T2是MST。證畢。
