摘 要：貪婪算法作為一種求最優(yōu)解問題的方法，具有簡便、迅捷的特點(diǎn)，然而貪婪算法因其基于局部求最優(yōu)解的特點(diǎn)，決定了其在很大程度上無法得到問題的最優(yōu)解。本文通過對[0-1背包問題]以及部件加工問題的分析，闡述了貪婪算法的應(yīng)用以及貪婪算法存在的局限性，進(jìn)而引出貪婪算法的優(yōu)化方案——k階優(yōu)化方法，進(jìn)一步對求最優(yōu)解問題進(jìn)行完善和歸納。

關(guān)鍵詞：貪婪算法；最優(yōu)解0-1背包問題；部件加工問題；k階優(yōu)化方法

中圖分類號：TP301.6

為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實(shí)際問題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪婪策略等一系列運(yùn)籌學(xué)模型紛紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)生了解決各種現(xiàn)實(shí)問題的有效算法。

貪婪算法（Greedy algorithm）是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計(jì)技術(shù)。用貪婪法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間，它采用自頂向下，以迭代的方法做出相繼的貪婪選擇，每做一次貪婪選擇就將所求問題簡化為一個(gè)規(guī)模更小的子問題，通過每一步貪婪選擇，可得到問題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。

貪婪算法可解決的問題通常大部分都有如下的特性：（1）有一個(gè)以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案，有一個(gè)候選的對象的集合：比如不同面值的硬幣；（2）隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過并被選出的候選對象，另一個(gè)包含已經(jīng)被考慮過但被丟棄的候選對象；（3）有一個(gè)函數(shù)來檢查一個(gè)候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)；（4）還有一個(gè)函數(shù)檢查是否一個(gè)候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性；（5）選擇函數(shù)可以指出哪一個(gè)剩余的候選對象最有希望構(gòu)成問題的解；（6）最后，目標(biāo)函數(shù)給出解的值。

1 問題回放與拓展

1.1 部件加工問題

（1）問題論述

（2）問題分析

本題求一個(gè)加工順序使得加工總時(shí)間最短，要使時(shí)間最短，則就是讓機(jī)器的空閑時(shí)間最短。一旦a工序開始加工，則a工序?qū)煌５倪M(jìn)行作業(yè)，關(guān)鍵是b工序在加工過程中，要等待a工序。很明顯第一個(gè)部件在a工序上加工時(shí)，b工序必須等待，最后一個(gè)部件在b工序上加工，a工序也在等待b工序的完工。

（1）方案原理

2.2 k階優(yōu)化方案總結(jié)

參考文獻(xiàn)：

[1]蘇德富，鐘誠.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2001.

[2]鄧宏濤，朱峋.0/1背包問題的貪心優(yōu)化解法[J].計(jì)算機(jī)與數(shù)字工程，2006.

[3]譚浩強(qiáng)C程序設(shè)計(jì)（第四版）[M].北京：清華大學(xué)出版社，2010.

作者簡介：馮光毅（1991-），男，浙江寧波人，本科在讀。

作者單位：浙江工商大學(xué) 信息與電子工程學(xué)院，杭州 310000