貪心算法解決活動安排問題研究.doc

貪心算法解決活動安排問題研究摘要：利用貪心算法解決如何使用最少的資源安排一系列活動。并證明了貪心算法解決此問題的有效性，且進行了實例驗證，并進行了復(fù)雜度分析，此算法是解決資源組合規(guī)劃問題較好的方法。關(guān)鍵詞：貪心算法；java程序；復(fù)雜度分析；活動安排問題中圖分類號：tp312文獻標(biāo)識碼：a文章編號：16727800（2011）012004302基金項目：廣西研究生教育創(chuàng)新計劃（2011106020812m58）作者簡介：蘇方方（1986-），女，河南商丘人，廣西師范大學(xué)計算機科學(xué)與信息工程學(xué)院碩士研究生，研究方向為自然語言處理和算法；張金玲（1986-），女，山東菏澤人，廣西師范大學(xué)計算機科學(xué)與信息工程學(xué)院碩士研究生，研究方向為遠(yuǎn)程教育和算法。0引言假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。這里就需要選用合適的算法來解決類似的問題。雖然計算機的計算能力每年都在飛快增加，但是，需要處理的信息量更是呈指數(shù)級的增長?；ヂ?lián)網(wǎng)的信息流量在飛快進步，數(shù)據(jù)量更是達到了前所未有的程度。無論是三維圖形，海量數(shù)據(jù)處理等都需要極大的計算量。在網(wǎng)絡(luò)時代，越來越多的挑戰(zhàn)需要靠卓越的算法來解決。1貪心算法以及貪心算法的基本要素貪心算法是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解。貪心算法可以簡單描述為：對一組數(shù)據(jù)進行排序，找出最小值，進行處理，再找出最小值， 再處理。也就是說貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪心算法解題步驟：從問題的某個初始解出發(fā)；采用循環(huán)語句，就根據(jù)局部最優(yōu)策略，得到一個部分解，縮小問題的范圍或規(guī)模；將所有部分解綜合起來，得到問題的最終解。另外它也是一種某種度量意義下的最優(yōu)解的分級處理方法。對于一個具體的問題，怎么知道是否可用貪心算法來解決問題，以及能否得到問題的一個最優(yōu)解呢？從許多可以用貪心算法求解的問題中可以看到它們一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)；最優(yōu)子結(jié)構(gòu)性質(zhì)。另外，同一個問題可用不用算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。2用貪心算法描述問題貪心算法高效地解決了一系列活動爭用某一個公共資源的問題，本文主要研究的是n個活動全部安排所需要的最少資源數(shù)。面對資源的日益緊缺，如何有效合理地利用資源一直是專家學(xué)者研究的熱點問題。用貪心算法解決本題的思想是：資源足夠多，但要使用最少的資源安排全部活動，同時保證每個資源中安排的活動集在時間上不能發(fā)生沖突。如果第一個資源中盡可能安排最多的活動，則這個資源得到了充分的利用，而且剩下的活動越少，第二個資源也盡可能安排最多的活動，依次類推。以下我們證明該問題具有貪心算法的兩個性質(zhì)：（1）活動安排問題具有貪心選擇性質(zhì)證明：首先將活動安排問題數(shù)學(xué)化，設(shè)有n個活動的集合 e= 1 ，2 ，n ，每個活動 i 都有一個要求使用該資源的起始時問si 和一個結(jié)束時問fi 。即k是所需最少資源的個數(shù)。設(shè)活動已排序，( a1 , a2 , ,ak )是所需要的k個已安排了活動的資源。當(dāng)k = 1時，也就是所有的活動在一個資源里相容，a1 是滿足貪心選擇性質(zhì)的最優(yōu)解；當(dāng)k = 2時，取b1=a1,bk=ak (即bk是安排了m個活動的一個資源，(n-m)個活動都安排在b1 到bk-1個資源里)。就是（n-m）個活動安排需要（k -1）個資源。則(b1,b2 ,bk-1 )是（n - m）個活動可行解。另一方面，由( a1 ,a2,ak)-ak=(b1,b2,bk-1)知，(b1,b2,bk-1)也是滿足貪心選擇性質(zhì)的最優(yōu)解，所以，活動安排問題具有貪心選擇性質(zhì)。（2）活動安排問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)證明：( a1,a2, ,ak )是n個活動的集合e= 1，2 ，n 所需資源的最優(yōu)解。設(shè)a1中安排了m個相容的活動，那么也就是說（n-m）個活動完全安排需要k-1個資源。假設(shè)（n - m）個活動安排只需要k-2個資源或則更少的資源。也就是說n個活動安排只需要k-1個資源就可以安排完，則前后出現(xiàn)矛盾。一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3程序清單及復(fù)雜性分析算法的復(fù)雜性是算法運行所需要的計算機資源的量，需要時間資源的量稱為時間復(fù)雜性，需要空間資源的量稱為空間復(fù)雜性，由于計算機的快速發(fā)展，計算機的空間資源很少作為考慮的對象，目前最為關(guān)注的就是時間復(fù)雜性。利用數(shù)組解決活動安排問題。程序的思想：設(shè)有n個活動等待安排，這些活動的起始時間和結(jié)束時間分別存放在數(shù)組 start和 finish中，定義了一個整型變量flag用于標(biāo)記活動是否被分配了資源。要對活動的開始時間與已分配的資源里最后被添加進去的活動的結(jié)束時間進行比較，如果大于，則把該活動添加進此資源，否則繼續(xù)與其他資源的最后被添加的活動的結(jié)束時間進行比較，如果所有的已分配資源均安排不了，則分配一個新資源來安排此活動。程序清單如下：public class needsourcestatic int start =1,3,0,5,3,5,6,8,8,2,12;/活動開始時間數(shù)組；static int finish=4,5,6,7,8,9,10,11,12,13,14;/活動結(jié)束時間數(shù)組 public static void main(string args) int i,j,flag=0; int num=new int11;int m=new int100; /有足夠多的資源 int source=1; /初始化，n個活動至少需要一個資源 int n=start.length; /活動的個數(shù)(一共有多少個活動) num0=1; /numi=j;編號為i的活動安排在第j個資源里 m1=0; /資源1中最后被添加進來的活動編號是0；for(i=1;i=finishmj) /最后被添加進來的活動結(jié)束時間相比；numi=j;/把i活動安排在j資源里；mj=i; /記錄最后被添加到j(luò)中的i活動；flag=1; /標(biāo)記活動已被分配到了資源 ；h=j; /j的值是變化的。賦值h以記錄值；if(flag=1)/活動被安排了，則跳出循環(huán)；break; ；if(flag=1)else numi=h+1;/所有的資源都不能安排，則添加新資源 mh+1=i; /記錄最后添加到j(luò)+1中的活動isource+; flag=0; system.out.println(source); 結(jié)果及分析：程序?qū)崿F(xiàn)了在控制臺打印出所需要資源的個數(shù)。運行程序結(jié)果顯示5，與手工測算結(jié)果相同。復(fù)雜性分析：語句、是給數(shù)組賦值語句，是0操作；語句的循環(huán)控制變量i要從1增加到n，故它的頻度是n。語句的循環(huán)控制變量j是從1增加到source，但是source無論什么情況下都小于n，則語句最多循環(huán)了(1+2+3+n)=(n2)/2,而語句的循環(huán)體中語句因為每次都需要判斷，所以頻度也是0(n2)；語句、執(zhí)行的次數(shù)是一樣的。并且和語句else循環(huán)體中的執(zhí)行次數(shù)加起來正好是0(n2)；語句、執(zhí)行次數(shù)是0(n2)；語句最多執(zhí)行n次；語句的頻度n；該算法中所有語句的頻度之和(即算法的時間耗費)為： t(n)=0(1)+ 20(1)+0(n)+0(n2)+0(n2)+30(n2)+20(n2)+20(n)；所以時間復(fù)雜度是0(n2)；4結(jié)束語本文對初步資源規(guī)劃問題的思考，可以對多個資源組合規(guī)劃問題的基礎(chǔ)研究提供有效的參考作用。目前多個資源組合規(guī)劃問題在現(xiàn)實研究中仍有許多不盡人意的地方，如何設(shè)計實用的算法解決多個資源組合規(guī)劃問題，是值得我們不斷研究探討的課題。 參考文獻：1肖衡淺析貪心算法j辦公自動化雜志，2009（10）.2常又渠，肖貴元貪心算法的探討與研究j重慶電力高等專科學(xué)校學(xué)報，2008（2）.3王曉東計算機算法設(shè)計與分析m北京：電子工業(yè)出版社, 2007research on greedy algorithm to solve the activity arrangementabstract: to use the greedy algorithm solves how to arrange a series of activities with minimal resources. it proves that it is effective to solve this problem with greedy algorithm and a examp