解最佳化问题的演算法.ppt

《解最佳化问题的演算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GreedyAlgorithmsGreedyMethods(描述1)解最佳化問題的演算法,其解題過程可看成是由一連串的決策步驟所組成,而每一步驟都有一組選擇要選定.一個greedymethod在每一決策步驟總是選定那目前看來最好的選擇.Greedymethods並不保證總是得到最佳解,但在有些問題卻可以得到最佳解.2GreedyAlgorithmsGreedyMethods(描述2)Greedy演算法經常是非常有效率且簡單的演算;但但較難證明其正確性(與DP演算法比較).很多heuristicalgorithms都採用greedymetho

2、ds的策略.3GreedyAlgorithms一個活動選擇問題(定義)假設有n個活動提出申請要使用一個場地,而這場地在同一時間點時最多只能讓一個活動使用.問題是：從這n個活動選一組數量最多,且可以在這場地舉辦的活動集.1234567891110時間軸假設活動i,其提出申請使用場地的時段為一半關半開的區間[si,fi),並以符號Ii代表.4GreedyAlgorithms一個活動選擇問題(設計1)LetP(A)denotetheproblemwithAasthegivensetofproposedactivitiesandSdenoteano

3、ptimalsolutionofP(A).ForanyactivityiinA,wehave1.iSSisanoptimalsolutionofP(A{i}).2.iSS{i}isanoptimalsolutionofP(AN[i])butnotnecessaryanoptimasolutionofP(A{i}).iN[i]:N[i]={jA:IjIi}5GreedyAlgorithms一個活動選擇問題(設計2)WhatkindofactivityiinAwillbecontainedinanoptimalsolut

4、ionofP(A):anactivitywith1.minimumfisior2.minimum

5、N[i]

6、or3.minimumfior4.minimumsi.Answer:.Proof:Letf1=min{fi}andSbeanoptimalsolutionofP(A).If1SthenthereisoneandonlyoneactivityinS,sayj,suchthatIjI1.ThenS{j}{1}isalsoanoptimalsolution.6GreedyAlgorithms一個活動選擇問題(程式+例子)Gre

7、edy-ASP(s,f,n){/*f[1]f[2]…f[n]*/Ans={1};for(i=2,j=1;in;i++)if(s[i]f[j]){Ans=Ans{i};j=i;}}1234567891110timeInput:isifi114235306457538659761088119812109131112147GreedyAlgorithmsGreedy演算法的要素Optimalsubstructure(aproblemexhibitsoptimalsubstructureifanoptimalsolutiontothep

8、roblemcontainswithinitoptimalsolutionstosubproblems)Greedy-choicepropertyPriorityqueueorsorting8GreedyAlgorithmsKnapsackProblem(Greedyvs.DP)Givennitems:weights:w1w2…wnvalues:v1v2…vnaknapsackofcapacityWFindthemostvaluableloadoftheitemsthatfitintotheknapsackExample:itemweigh

9、tvalueKnapsackcapacityW=1612$2025$30310$5045$109GreedyAlgorithmsKnapsackProblemGivennitems:weights:w1w2…wnvalues:v1v2…vnaknapsackofcapacityWT[i,j]:theoptimalsolutionusingitem1,...,iwithweightatmostj.Ifwi>jT[i,j]=T[i-1,j];otherwiseT[i,j]=max{T[i-1,j],wi+T[i-1,j-wi]}.Howgood

10、isthismethod?10GreedyAlgorithms0-1andFractionalKnapsackProblemConstraintsof2variantsofthe