這是計算機算法課結課作業的一部分，因為比較有意思，所以放了上來。希望自己以后也可以在需要用到的時候想起還有這么一回事。這里的文字大抵也談不上證明，僅僅只算是自己的思考過程吧。

在實現貪心算法來解決活動安排問題之前，我們先證明一下為什么貪心算法可以在活動安排問題中一定可以獲得最優解。

首先我們先來看看活動安排問題的定義，在一系列開始和結束時間不同的活動中選擇出最大的相容活動子集合。

(資料圖片僅供參考)

以下是比較細節的定義：

問題描述設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si <fi。如果選擇了活動i，則它在半開時間區間[si, fi)內占用資源。若區間[si, fi)與區間[sj, fj)不相交,則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

利用我們的數學歸納法：

當問題的n=1時，及按照貪心算法的選擇，自然只會選擇唯一的那一個活動。而又因為集合最大為1，因此此時貪心算法一定為最優解。

接下來，我們需要證明：假設n=k時貪心算法能獲得最優解(集合容量=a)，那么n=k+1能獲得最優解(及集合容量為a/a+1)。

對于n=k+1組成的活動集合A，我們先去掉結束時間s最小的元素。

此時，n=k，那么根據我們的假設，根據貪心法獲得的最大子集B，為此時最優解。

此時再加入b1:

若不沖突，直接加入，保持最優解性質。

若沖突，此時b1一定在新的最優解集合中。那么我們去掉此時在原最優解集合中的第一個元素，及那個與b1沖突的元素，此時n=k，一定獲得最優解。(假設在最優解中，我們選擇了與 A1 沖突的另一個活動 Ak（k > 1）。那么我們可以將 Ak 替換為 A1，得到一個新的解，該解與最優解的活動數量相同或更多，并且滿足互不沖突的條件。)

保持原性質，證畢。

因此，得證n=k+1時可獲得最優解。

然而，這真的結束了嗎。其實不然。第二天再次回顧，發現了一處邏輯的不完整：我沒有證明當活動按照結束時間s從小到大排序時，此時最優解中一定可以包含b1。(即某個最優解不一定會包含b1，但是全部最優解集合中一定存在包含b1的最優解集合).

那么接下來我們可以證明這件事：

我們假設按照結束時間從小到大排序的活動集合E={1,2,…,n}存在一個最優解A，且A中也按照結束時間從小到大排序。設A的第一個活動為K1.那么有

若K1=1，此時證畢。

若K1≠1，那么此時由于1的結束時間一定小于K1，因此當我們將該集合中的K1替換為1時，由于A為最優解，其最大相容子集合的元素數量在E中就是該集合的最大相容子集合的元素數量。因此，由于數量不改變，此時的集合仍然為最大相容子集合，證畢。

不得不承認，我的語言比較不嚴謹，但是我認為所有的邏輯應當已經不存在謬誤。

如發現邏輯謬誤，請隨意指出。

上一篇：多方協作，123米的龐然大物順利起運

下一篇：祝融殿