這是計算機算法課結(jié)課作業(yè)的一部分，因為比較有意思，所以放了上來。希望自己以后也可以在需要用到的時候想起還有這么一回事。這里的文字大抵也談不上證明，僅僅只算是自己的思考過程吧。
在實現(xiàn)貪心算法來解決活動安排問題之前，我們先證明一下為什么貪心算法可以在活動安排問題中一定可以獲得最優(yōu)解。
首先我們先來看看活動安排問題的定義，在一系列開始和結(jié)束時間不同的活動中選擇出最大的相容活動子集合。
(資料圖片僅供參考)
以下是比較細節(jié)的定義：
問題描述設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si <fi。如果選擇了活動i，則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交,則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。
利用我們的數(shù)學(xué)歸納法：
當(dāng)問題的n=1時，及按照貪心算法的選擇，自然只會選擇唯一的那一個活動。而又因為集合最大為1，因此此時貪心算法一定為最優(yōu)解。
接下來，我們需要證明：假設(shè)n=k時貪心算法能獲得最優(yōu)解(集合容量=a)，那么n=k+1能獲得最優(yōu)解(及集合容量為a/a+1)。
對于n=k+1組成的活動集合A，我們先去掉結(jié)束時間s最小的元素。
此時，n=k，那么根據(jù)我們的假設(shè)，根據(jù)貪心法獲得的最大子集B，為此時最優(yōu)解。
此時再加入b1:
若不沖突，直接加入，保持最優(yōu)解性質(zhì)。
若沖突，此時b1一定在新的最優(yōu)解集合中。那么我們?nèi)サ舸藭r在原最優(yōu)解集合中的第一個元素，及那個與b1沖突的元素，此時n=k，一定獲得最優(yōu)解。(假設(shè)在最優(yōu)解中，我們選擇了與 A1 沖突的另一個活動 Ak（k > 1）。那么我們可以將 Ak 替換為 A1，得到一個新的解，該解與最優(yōu)解的活動數(shù)量相同或更多，并且滿足互不沖突的條件。)
保持原性質(zhì)，證畢。
因此，得證n=k+1時可獲得最優(yōu)解。
然而，這真的結(jié)束了嗎。其實不然。第二天再次回顧，發(fā)現(xiàn)了一處邏輯的不完整：我沒有證明當(dāng)活動按照結(jié)束時間s從小到大排序時，此時最優(yōu)解中一定可以包含b1。(即某個最優(yōu)解不一定會包含b1，但是全部最優(yōu)解集合中一定存在包含b1的最優(yōu)解集合).
那么接下來我們可以證明這件事：
我們假設(shè)按照結(jié)束時間從小到大排序的活動集合E={1,2,…,n}存在一個最優(yōu)解A，且A中也按照結(jié)束時間從小到大排序。設(shè)A的第一個活動為K1.那么有
若K1=1，此時證畢。
若K1≠1，那么此時由于1的結(jié)束時間一定小于K1，因此當(dāng)我們將該集合中的K1替換為1時，由于A為最優(yōu)解，其最大相容子集合的元素數(shù)量在E中就是該集合的最大相容子集合的元素數(shù)量。因此，由于數(shù)量不改變，此時的集合仍然為最大相容子集合，證畢。
不得不承認，我的語言比較不嚴(yán)謹，但是我認為所有的邏輯應(yīng)當(dāng)已經(jīng)不存在謬誤。
如發(fā)現(xiàn)邏輯謬誤，請隨意指出。
下一篇：祝融殿
責(zé)任編輯：
