資源描述：
《貪心算法論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、貪心算法論文姓名：高翔班級：706指導(dǎo)老師：范江文一概念；貪心，貪心顧名思義即不顧一切地追求目標(biāo)。在FreePascal中貪心算法可以解釋為：從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達到某算法中的某一步不能再繼續(xù)。前進時，算法停止。這時就得到了問題的一個解，但不能保證求得的最后解是最優(yōu)的。在改進算法中，貪心算法演化為爬山法。注意：貪心算法并不能保證求得的解是最優(yōu)的，一定要三思而后行??！二特點及使用范圍貪心算法的優(yōu)點在于時間復(fù)雜度極低。而貪心算法與其他最優(yōu)化算法的區(qū)別在于：它具有不可后撤性，可以有后效性，一般情況下不滿足最優(yōu)化原理。貪心算法的特
2、點就決定了它的適用范圍，它一般不適用于解決可行性問題，僅適用于較容易得到可行解的最優(yōu)性問題。這里較容易得到可行解的概念是：當(dāng)前的策略選擇后，不會或極少使后面出現(xiàn)無解的情況。另外，對于近年來出現(xiàn)的交互性題目，貪心算法是一個較好的選擇。這是因為，在題目中，一個策略的結(jié)果是隨題目的進行而逐漸給出的，我們無法預(yù)先知道所選策略的結(jié)果，這與貪心算法不考慮策略的結(jié)果和其具有后效性的特點是不謀而合的。當(dāng)然，貪心算法還可以為搜索算法提供較優(yōu)的初始界值。三經(jīng)典例題?例一背包問題有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。???要求盡可能讓裝入背包中的物品總價值最大，但
3、不能超過總?cè)萘俊???物品ABCDEFG???重量35306050401025???價值10403050354030???分析：???目標(biāo)函數(shù)：∑pi最大???約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150)???（1）根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？???（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？???（3）每次選取單位重量價值最大的物品，成為解本題的策略。???值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。???貪心算法還是很常見的算法之一，這是由于它簡單
4、易行，構(gòu)造貪心策略不是很困難。???可惜的是，它需要證明后才能真正運用到題目的算法中。???一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。???對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：???（1）貪心策略：選取價值最大者。反例：???W=30???物品：ABC???重量：281212???價值：302020???根據(jù)策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。???（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。???（3）貪心策略：選取單位重量價值最大的物品。
5、反例：???W=30???物品：ABC???重量：282010???價值：282010根據(jù)策略，三種物品單位重量價值一樣，程序無法依據(jù)現(xiàn)有策略做出判斷，如果選擇A，則答案錯誤。注意：此題用貪心算法解的確不錯，但不是最優(yōu)解。解此題思路⒈建立數(shù)學(xué)模型來描述問題。⒉把求解的問題分成若干個子問題。⒊對每一子問題求解，得到子問題的局部最優(yōu)解。⒋把子問題的解局部最優(yōu)解合成原來解問題的一個解。實現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進一步do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。二貪心算法之汽車加油問題問題描述???一輛汽車加滿油后可以行
6、駛N千米。旅途中有若干個加油站。指出若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站?？考佑?。???給出N，并以數(shù)組的形式給出加油站的個數(shù)及相鄰距離，指出若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站停靠加油。要求：算法執(zhí)行的速度越快越好。??問題分析（前提行駛前車里加滿油）???對于這個問題我們有以下幾種情況：設(shè)加油次數(shù)為k，每個加油站間距離為a[i]；i=0，1，2，3……n???1.始點到終點的距離小于Ｎ，則加油次數(shù)k=0；???2.始點到終點的距離大于N，???A?加油站間的距離相等，即ａ[i]=a[j]=L=N，則加油次數(shù)最少k=
7、n；???B?加油站間的距離相等，即ａ[i]=a[j]=L>N，則不可能到達終點；???C?加油站間的距離相等，即ａ[i]=a[j]=L
