參考《算法導論第二版P222頁)
算法導論 原書第2版 高清PDF及答案 下載見 http://www.linuxidc.com/Linux/2015-05/117756.htm
一,如何把現實的問題轉變成數學問題?即數學建模的思路?
1,問題描述:現有一組相互競爭的活動,如何調度能夠找出一組最大的活動(活動數目最多)使得它們相互兼容?
2,問題轉化:
首先,按活動的結束時間單調遞增進行排序。那麼,為什麼要按結束時間排序呢?這個問題留到後面解釋。
其次,定義合適的問題子空間,即定義集合S(i,j)。問題子空間描述的是現實生活中的問題,而集合S(i,j)則是數學概念,通過某種方式定義一個合適的集合將問題子空間的解轉化為集合的解(即求出集合中符合某種條件的所有元素)。
3,那麼問題來了,怎樣才能讓定義的這個集合問題能夠描述現實問題呢?----
a,將S(i,j)中元素表示成與活動a(i)、a(j)兼容的活動
b,將活動a(1)、a(2)……a(i)、a(i+1)、……a(j)、a(j+1)……a(n) 按照結束時間單調遞增排序!每個集合元素有一個特征:有開始時間和結束時間。
這就是為什麼要按結束時間單調遞增排序的原因,因為只有這樣,才能夠成功的建模,將現實問題轉化成數學問題。
當定義的集合中的元素(活動)滿足了這兩個因素之後,就可以將子問題空間(從a(1)、a(2)……a(i)、a(i+1)、……a(j)、a(j+1)……a(n)活動中選出最大兼容活動集合)
轉化成
數學上的集合問題(求解集合S(i,j)的元素中滿足開始時間和結束時間不相互沖突的最多的元素個數)
4,如何證明子問題S(i,j)的解是最優的?
剪貼技術 即 反證法。建模出來的集合的性質,它可以將S(i,j)的最優解分成S(i,k)S(k,j)的最優解!
5,如何根據子問題的解構造出原問題的解?
構造虛構的活動 a(0)和a(n+1)。那麼,S(0,n+1)就表示原問題的解!
6,寫出問題的解的數學表達式
數學表達式見 《算法導論第二版》P244 上。
二,活動選擇的貪心策略及證明此貪心策略的正確性
1,貪心策略:先將活動按結束時間單調遞增進行排序,並且優先選擇結束時間最早的活動。具體操作如下:
a,設已排好序的各個活動構成的集合為S(0,n+1),最大兼容活動集合為A,A初始為空
b,在S(0,n+1)中選擇結束時間第一早(最早)的活動,記為a1,A = A U {a1}
c,繼續選擇下一個活動,該活動滿足兩個條件:與先前已選擇的活動兼容;是未選擇的活動中結束時間最早的活動
d,重復上一步直到沒有活動可以選擇,此時得到的A為最大兼容活動集合
2,證明此貪心策略的正確性
a,S(i,j)表示成與活動a(i)、a(j)兼容的活動,求S(0,n+1)的最大兼容活動集合,即為求原實際問題的解。
b,《算法導論》中定理16.1 (1)證明了活動a(m)是S(i,j)的某個最大兼容活動集合的一個元素,而元素 a(m) 正是根據上述貪心策略選擇出來的。這說明,按照上述貪心策略的選擇,可以選出最大兼容活動集合中的元素。
c,再由定理16.1(2),當選擇了a(m)後,求解S(i,j)的最大兼容活動集合變成求解S(m,j)的最大兼容活動集合,它將問題空間縮小了。而根據 b,求S(m,j)的最大兼容活動集合就是從S(m,j)中選擇最早結束的活動!
d,因此,由 b , c 可知:根據上述貪心策略能成功地選取出S(i,j)的一個最大兼容活動集合。
--------------------------------------------------------------------------
《算法導論》介紹了很多算法分析的方法:從某個現實生活中的問題入手,然後將之一步步地轉化成數學問題,再運用一些分析技術(動態規劃、貪心、隨機化、概率分析、分治……)將之表示成偽代碼,最後就可以用編程語言將這些偽代碼實現!