貪心算法的分析與實際應(yīng)用

貪心算法的分析與實際應(yīng)用用時可以刪除天津師范大學(xué)計算機與信息工程學(xué)院算法設(shè)計與分析結(jié)課論文專業(yè)計算機科學(xué)與技術(shù)班級1402班 學(xué)號56姓名王悅寧 而且說給而且說給出的算法一般比動態(tài)規(guī)劃算法更加簡法概述ithm優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。本文主要介紹了貪心ThegreedyalgorithmanalysisandpracticalapplicationAbstract：Greedyalgorithmrefersto,inthesolutionoftheproblem,alwaysmakeinthecurrentviewisthebestchoice.Thatistosay,nottobeconsideredasawhole,hemadeonlyinasenseofthelocaloptimalsolution.Thegreedyalgorithmisnotabletoobtaintheglobaloptimalsolutionforallproblems,butforawiderangeofproblems,hecanproducetheglobaloptimalsolutionortheapproximatesolutionoftheglobaloptimalsolution.Thispapermainlyintroducesthecoreofthegreedyalgorithm,thecharacteristicsandtheexistingproblemsofthealgorithmitself..Keywords：greedyalgorithm;optimalsolution;knapsackproblem;0引言，為了解決各種實際問題，計算機算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一紛運用到計算機算法學(xué)中，產(chǎn)個好的算求解算法更像是一門藝術(shù)而不是像技術(shù)，但仍存在一些行之有效的、能夠用于解決許質(zhì)和貪心選擇性質(zhì)時，貪心算法通常給出一個簡單，直觀和高效的解法。貪心算法通過一系列的選擇來得到一且每次貪心選擇都能將問題化簡為一個更小的與許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)方法。其核心后將這多個輸所要求的順序，按這種順序當(dāng)前已構(gòu)成在解加在一起不能產(chǎn)生部分解中。這下最優(yōu)解的分級處理方，往往可能有好幾種量度標(biāo)準(zhǔn)似乎都是可取不是問題的擇能產(chǎn)生問題最并不是一件最優(yōu)量度標(biāo)準(zhǔn)效。最優(yōu)解可以通貪心選擇來達(dá)到，根這個選擇后產(chǎn)生子問題，最終可得到問本思想始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個算法中的某一步不能再繼續(xù)前進(jìn)。貪心算法的思想本質(zhì)就是分治，就是每次都處理處一個最好的方案。的核心貪心算法的核心問題是選擇能生產(chǎn)最優(yōu)解的貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的便可看出，貪心策略總是做出在當(dāng)前看來是最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題的自身的特性決定論該問題法特性貪心算法可解決的問題通常大部分都有如下有一個候選的對象的集合:比包含已經(jīng)被考慮過并被選出的候選對象，另。函數(shù)一樣，婪算法一步對象的集合函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。到集合里。每一次都。如果貪婪貪心算法的理論基礎(chǔ)-擬陣貪心策略是最接近人類認(rèn)知思維的一種解題“擬陣”理論是一種能夠確定貪心策略何時(S,I):(1)S是非空有限集；(2)I是S的一類具有遺傳性質(zhì)的獨立子集I滿足交換性質(zhì)，即若A∈I，B∈I，且引理(擬陣的貪心選擇性質(zhì))設(shè)M=(S,I)是引理(擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì))設(shè)x是求帶MSI的最優(yōu)子集的貪心算法Greedy化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問題。定理(帶權(quán)擬陣貪心算法的正確性)高M(jìn)=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法Greedy結(jié)的問題，即給定一個加權(quán)擬陣M=(S,I)，若能找題，只求解。擬陣一復(fù)雜優(yōu)缺點貪心算法是一種重要的算法設(shè)計策略而且其效率高。貪心算法并不從整體最優(yōu)考慮他所做出的選擇只是在某種意義上的局部最優(yōu)選擇，即在選擇導(dǎo)致最終結(jié)果是問題的一個最優(yōu)解。貪心算法具有良好的爬坡能力，一般情況下該算法都可當(dāng)算法不能在限定的時間內(nèi)給，找滿足問題要求的近似最優(yōu)解時，給出一個可行解及其計算誤差，作為決策參考。但隨著問題規(guī)模和復(fù)雜的不斷提升，單一的算法在其收斂性和求解速度等方面已經(jīng)表現(xiàn)出的局限性，即使貪心算法的效率很只適用于少量實例。貪心算法解決問題，也就是，以此類多少。以是一。題的(無法被證明)的，解釋如下：最大者。020最小。它的反例與第重量價值最大的物282010重量價值一樣，程分割為任意大小，那么策最大的物品這個策規(guī)