貪心算法解決活動(dòng)安排問(wèn)題PPT課件

1、11問(wèn)題描述 內(nèi)容提要23實(shí)驗(yàn)及結(jié)果4實(shí)驗(yàn)總結(jié)算法思想及分析第1頁(yè)/共10頁(yè)2問(wèn)題描述問(wèn)題描述 設(shè)有n n個(gè)活動(dòng)的集合E=1,2E=1,2，nn，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i i都有一個(gè)要求使用該資源的起始時(shí)間sisi和一個(gè)結(jié)束時(shí)間fifi，且sifisi=fjsi=fj或者sj=fisj=fi時(shí)，活動(dòng)i i與活動(dòng)j j相容。活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合。 問(wèn)題描述返回第2頁(yè)/共10頁(yè)3貪心算法算法思想及分析算法思想及分析 活動(dòng)安排運(yùn)用貪心算法的思路為，盡可能多的使更多的事件得到資源的安排。按

2、這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。實(shí)現(xiàn)方法是在滿足相容的條件下，使結(jié)束時(shí)間靠前的活動(dòng)得到資源，這樣就為后續(xù)時(shí)間留下更多的安排時(shí)間，以使更多的活動(dòng)得到安排。 貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。 第3頁(yè)/共10頁(yè)4算法思想及分析算法思想及分析 由于貪心算法解決安排問(wèn)題要考慮么個(gè)活動(dòng)的結(jié)束由于貪心算法解決安排問(wèn)題要考慮么個(gè)活動(dòng)的結(jié)束時(shí)間，所以先時(shí)間，所以先將活動(dòng)按照結(jié)

3、束時(shí)間長(zhǎng)短進(jìn)行遞增排序?qū)⒒顒?dòng)按照結(jié)束時(shí)間長(zhǎng)短進(jìn)行遞增排序。本。本貪心算法在處理非減序排列活動(dòng)隊(duì)列時(shí)可以達(dá)到極高的效貪心算法在處理非減序排列活動(dòng)隊(duì)列時(shí)可以達(dá)到極高的效率。率。 待安排的待安排的1111個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：的非減序排列如下： 貪心算法實(shí)現(xiàn)表表1 1 安排活動(dòng)非減序時(shí)間表安排活動(dòng)非減序時(shí)間表第4頁(yè)/共10頁(yè)5算法思想及分析算法思想及分析 貪心算法的計(jì)貪心算法的計(jì)算過(guò)程如下圖所示。算過(guò)程如下圖所示。圖中圖中每行相應(yīng)于算每行相應(yīng)于算法的一次迭代法的一次迭代。陰陰影長(zhǎng)條表示的活動(dòng)影長(zhǎng)條表示的活動(dòng)是已選入集合是已選入集合A

4、 A的活的活動(dòng)動(dòng)，而空白長(zhǎng)條表而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正示的活動(dòng)是當(dāng)前正在檢查相容性的活在檢查相容性的活動(dòng)動(dòng)。 貪心算法實(shí)現(xiàn) 若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。圖圖-1 -1 貪心算法的計(jì)算過(guò)程圖貪心算法的計(jì)算過(guò)程圖 第5頁(yè)/共10頁(yè)6 實(shí)驗(yàn)仿真過(guò)程實(shí)驗(yàn)及其結(jié)果實(shí)驗(yàn)及其結(jié)果 在VC 6.0環(huán)境下測(cè)試貪心算法的性能 。實(shí)驗(yàn)過(guò)程如下： 表-2 實(shí)驗(yàn)輸入輸出參數(shù)設(shè)置圖-2 運(yùn)行結(jié)果 第6頁(yè)/共10頁(yè)7 比較項(xiàng)比較項(xiàng)算法名稱算法名稱時(shí)間復(fù)雜度時(shí)間復(fù)雜度末減序排列算法末減序排列算法O(n2)減序算法減序算法O(nlogn)貪心算法貪心算法O(n) 實(shí)驗(yàn)結(jié)果分析第7頁(yè)/共10頁(yè)8小組任務(wù)分工小組任務(wù)分工1. 算法： 李文治2. PPT： 制作：陳平，謝華欣