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