姚菊菊

(上海江南船舶管業(yè)有限公司， 上海 201302)

?

貪心算法的探討及其在船舶領(lǐng)域的應(yīng)用

姚菊菊

(上海江南船舶管業(yè)有限公司， 上海 201302)

摘要貪心算法是在求問(wèn)題的最優(yōu)解時(shí)，從最初的狀態(tài)，通過(guò)一系列在當(dāng)前環(huán)境下所能做出的最優(yōu)的選擇而得到整個(gè)問(wèn)題的最優(yōu)解，這便是貪心算法的基本思想。從中不難發(fā)現(xiàn)，貪心算法只能達(dá)到局部的最優(yōu)解，它對(duì)于當(dāng)前做出的選擇只依賴于以往做出的選擇，而不與未來(lái)做出的選擇相關(guān)，即不依賴子問(wèn)題的解。這也就決定了貪心算法在解決問(wèn)題時(shí)有一定的速度優(yōu)勢(shì)，由于此解決問(wèn)題的優(yōu)勢(shì)使得它成為最優(yōu)方案的備選方法之一。本文論述了貪心算法的實(shí)現(xiàn)思路和過(guò)程、核心思想、基本特性、特點(diǎn)以及存在的問(wèn)題，并詳細(xì)論述了其在船舶建設(shè)領(lǐng)域中的幾點(diǎn)應(yīng)用。

關(guān)鍵詞貪心算法哈弗曼算法單源最短路徑

0引言

當(dāng)今是信息化社會(huì)，計(jì)算機(jī)的算法通常被運(yùn)用于處理較大信息量的數(shù)據(jù)，以快速解決實(shí)際問(wèn)題。為了使算法針對(duì)實(shí)際問(wèn)題獲得更好的性能，需要對(duì)算法進(jìn)行改進(jìn)。

貪心算法的思想就是從問(wèn)題的初狀態(tài)出發(fā)，通過(guò)一系列的貪心選擇來(lái)得到解決問(wèn)題最優(yōu)解的一種解題方法。通過(guò)對(duì)當(dāng)前狀態(tài)下所作出最好的選擇來(lái)實(shí)現(xiàn)最優(yōu)解，它所適用的范圍是問(wèn)題具有最優(yōu)子結(jié)構(gòu)和貪心選擇，并運(yùn)用貪心選擇的策略給出簡(jiǎn)便和高效的解決方法。本文通過(guò)對(duì)貪心算法進(jìn)行深入研究，分析了其在船舶領(lǐng)域的實(shí)際應(yīng)用(船舶建設(shè)中倉(cāng)庫(kù)的分配優(yōu)化問(wèn)題)。總之，正是因?yàn)樨澬乃惴ê?jiǎn)單、高效、容易理解，所以其往往是解決問(wèn)題最好的備選方案之一，將其盡可能地應(yīng)用在船舶建設(shè)領(lǐng)域具有十分深遠(yuǎn)的意義。

1貪心算法的知識(shí)概述

1.1貪心算法的簡(jiǎn)單描述

所謂的貪心算法是在問(wèn)題的處理過(guò)程中，對(duì)于每一次做出的選擇都是在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而使得結(jié)果是最優(yōu)的算法[1]。即對(duì)于一組數(shù)據(jù)進(jìn)行排序，找出最小值，并進(jìn)行處理；接著再找出最小值，進(jìn)行處理，直到問(wèn)題解決。

貪心算法是對(duì)問(wèn)題在具有某種度量意義的情況下進(jìn)行分級(jí)處理的方法，它是通過(guò)一系列的選擇來(lái)得到問(wèn)題的解，而這些選擇是當(dāng)前能做出的最好選擇，具有貪心的意義，即貪心選擇。從而不難看出這種算法是通過(guò)局部最優(yōu)解來(lái)求解整體最優(yōu)解。這種方法很容易被人理解，經(jīng)常被人們所采用。它除了簡(jiǎn)單，高效，也有其弊端，不是所有的問(wèn)題采用貪心算法都能夠得到整體最優(yōu)解，有時(shí)得到的只是最優(yōu)解的相似值[2]。

1.2貪心算法的解題思路和過(guò)程

1.2.1貪心算法的解題思路

用貪心算法解題的整體思想就是以局部的方法最終求得全局解，即將問(wèn)題劃分成若干個(gè)子問(wèn)題，直到解決無(wú)法再劃分的問(wèn)題為止。貪心算法的基本思想就是各個(gè)解決，處理的子問(wèn)題的結(jié)果都是當(dāng)前看來(lái)最好的解。用貪心算法解題，需要考慮兩個(gè)問(wèn)題：

(1) 該問(wèn)題是否符合用貪心算法求解；

(2) 如何規(guī)范貪心算法的標(biāo)準(zhǔn)，得到最優(yōu)解[3]。

1.2.2貪心算法的解題過(guò)程

(1) 使用同樣的規(guī)則，將問(wèn)題劃分成若干相似子問(wèn)題；

(2) 從問(wèn)題的初始狀態(tài)開(kāi)始，給出一個(gè)可行性的解元素；

(3) 將所有的解元素組合成最終問(wèn)題的可行性解[3]。

1.2.3貪心算法的理論研究基礎(chǔ)

從之前的分析我們不難發(fā)現(xiàn)，貪心算法是比較符合人類認(rèn)知思維解決最優(yōu)問(wèn)題的方法。為了在使用之時(shí)無(wú)后顧之憂，我們必須要驗(yàn)證它的正確性。下面就用“擬陣”理論來(lái)證明。

“擬陣”理論能夠證明運(yùn)用貪心算法何時(shí)產(chǎn)生最優(yōu)解，在求解最優(yōu)解的問(wèn)題中發(fā)揮著重要作用。

擬陣M 定義成滿足以下 3 個(gè)條件的有序?qū)?(S ,I) ：

(1) S是非空有限集；

(2) I 是 S 的一類具有遺傳性質(zhì)的獨(dú)立子族集，若 B ∈I ，則 B 是 I 的獨(dú)立子集，且 B的任意子集也是 S的獨(dú)立子集；

(3) I 滿足交換性，若 A ∈I ， B ∈I 且|A|<|B|，則存在某一元素 x ∈ B -A,使得

A∪{x}=∈I。

則擬陣M中所有極大獨(dú)立子集具有相同的大小。

假設(shè)1設(shè)擬陣M ={S ,I}是有權(quán)函數(shù) M 的帶權(quán)擬陣，且S 中元素依權(quán)值從大到小排列，又設(shè) x 是 S 中{x}第一個(gè)成為獨(dú)立子集的元素，則存在最優(yōu)子集 A 使得 x ∈ A (擬陣的貪心選擇性)。

假設(shè)2設(shè)M{S , I } 為擬陣，若 S 中 x 不是空集的一個(gè)可擴(kuò)元素，則 x 也不可能是 S中的任意子集 A的可擴(kuò)元素。

假設(shè)3(擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì))設(shè)x 是求帶權(quán)擬陣 M{S , I } 的最優(yōu)子集的貪心算法所選擇 S 中的第一個(gè)元素。那么原問(wèn)題可化簡(jiǎn)求為帶權(quán)擬陣M′{S′ , I ′}的最優(yōu)子問(wèn)題，其中

S′ ={y | y ∈S且(x, y)∈I}；

I ′ = {B | B?S-{x}且B ∪{x}∈I} 。

M′ 的權(quán)函數(shù)是 M 的權(quán)函數(shù)在 S′ 上的限制(稱 M′ 為M在x的收縮)。

則(帶權(quán)擬陣貪心算法的正確性)M={S , I} 是有權(quán)函數(shù)M的帶權(quán)擬陣，貪心算法能夠返回最優(yōu)子集。

能夠使用貪心算法來(lái)解題的很多問(wèn)題都可以歸納成在加權(quán)擬陣中找出一個(gè)具有最大權(quán)值的獨(dú)立子集問(wèn)題，即給定一個(gè)加權(quán)擬陣M{S , I} ，若能找到一個(gè)獨(dú)立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨(dú)立子集所包含，那么A為最優(yōu)子集，也是一個(gè)最大的獨(dú)立子集。擬陣對(duì)于我們判斷問(wèn)題是否適用貪心算法有非常大的幫助，對(duì)于大多數(shù)信息問(wèn)題，只要滿足擬陣結(jié)構(gòu)，便可以運(yùn)用貪心策略求解。

1.3貪心算法的基本要素

1.3.1貪心選擇性質(zhì)

貪心算法的第一個(gè)要素就是問(wèn)題具有貪心選擇的性質(zhì)。貪心選擇性質(zhì)能夠通過(guò)局部最優(yōu)解求得整體的最優(yōu)解，也就是經(jīng)過(guò)若干步驟的貪心選擇來(lái)達(dá)到最優(yōu)的結(jié)果。

貪心算法和動(dòng)態(tài)規(guī)劃最大的區(qū)別也就是在于貪心選擇。貪心算法中，能夠僅在當(dāng)前狀態(tài)下做出最優(yōu)選擇，這種選擇依賴于上一步的選擇，但不依賴將來(lái)子問(wèn)題的選擇；而動(dòng)態(tài)規(guī)劃中，所做出的選擇往往依賴子問(wèn)題的解。正是這種差別貪心算法是自頂而下的方式進(jìn)行，每做出一次選擇就把問(wèn)題化簡(jiǎn)成規(guī)模更小的子問(wèn)題，而動(dòng)態(tài)規(guī)劃則是從底往上的方式解決各個(gè)問(wèn)題[4]。要確定問(wèn)題是否具有貪心選擇的性質(zhì)，必須要證明每一步的貪心選擇能夠得到整體最優(yōu)解。第一要考慮該問(wèn)題的整體最優(yōu)解，使其從貪心選擇開(kāi)始，做出貪心選擇之后，問(wèn)題就變成規(guī)模更小的相似子問(wèn)題，接著用數(shù)學(xué)歸納法證明每一步的貪心選擇都能夠得到整體最優(yōu)解。

1.3.2最優(yōu)子結(jié)構(gòu)性質(zhì)

因?yàn)樨澬乃惴ㄊ峭ㄟ^(guò)局部最優(yōu)解實(shí)現(xiàn)整體最優(yōu)解，所以待解決的問(wèn)題必須具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)是問(wèn)題的最優(yōu)解包括其子問(wèn)題的最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是貪心算法解題的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)構(gòu)產(chǎn)生直接的影響，對(duì)每一個(gè)子問(wèn)題都做出了解決方案，是不能夠回退的。

1.4貪心算法的優(yōu)缺點(diǎn)

說(shuō)到貪心算法的特點(diǎn)，不得不說(shuō)到簡(jiǎn)化、高效、容易理解。貪心算法通常是線性二次式，所以它占有的內(nèi)存少，再加之其容易編寫(xiě)，方便調(diào)試，所以決定了它必定具有高效快速的優(yōu)勢(shì)。在選擇使用貪心算法的同時(shí)，我們也應(yīng)該考慮應(yīng)用該種方法來(lái)達(dá)到目的。如何選擇貪心算法并能夠驗(yàn)證最優(yōu)的正確性是考驗(yàn)我們的難題。同時(shí)它也存在著不足：

(1) 貪心算法并不適用于所有問(wèn)題的最優(yōu)解，即它適用的范圍具有局限性；

(2) 貪心策略的應(yīng)用對(duì)待解決的問(wèn)題要求比較嚴(yán)格，具有貪心選擇性和最優(yōu)子結(jié)構(gòu)性；

(3) 貪心算法對(duì)于有些問(wèn)題只能確定其可行性范圍，例如臨界問(wèn)題。

2貪心算法在船舶領(lǐng)域的應(yīng)用

2.1船舶生產(chǎn)過(guò)程中倉(cāng)庫(kù)使用的優(yōu)化問(wèn)題

2.1.1問(wèn)題描述

由于船舶生產(chǎn)的特殊性，生產(chǎn)過(guò)程中所涉及到的原材料種類繁多，型號(hào)品種更是復(fù)雜多樣。單是管材就包括不銹鋼管、碳鋼管、銅鎳合金管等，此外還有各種管附件，比如法蘭、彎頭、三通、復(fù)板、墊片、同心異徑、偏心異徑等，而且每種原材料在生產(chǎn)中的重要性都是等同的。如何使用最少數(shù)量的倉(cāng)庫(kù)，來(lái)滿足生產(chǎn)需求，保證各種原材料的及時(shí)供應(yīng)，是船舶生產(chǎn)過(guò)程中需要迫切解決的問(wèn)題，這就要求在生產(chǎn)過(guò)程中合理有效地安排、分配倉(cāng)庫(kù)，使用盡可能少的倉(cāng)庫(kù)來(lái)滿足生產(chǎn)需要。解決這個(gè)問(wèn)題我們就可以使用貪心算法。

在處理此問(wèn)題的過(guò)程中，我們需要考慮的問(wèn)題是怎樣根據(jù)倉(cāng)庫(kù)的容量、使用狀態(tài)來(lái)安排倉(cāng)庫(kù)，使其能夠以最高效率派上用場(chǎng)。我們將問(wèn)題簡(jiǎn)化如下：挑選兩個(gè)倉(cāng)庫(kù)成為ai和aj，若滿足以下條件：ai的剩余容量si≥aj的已使用容量fj,或者ai的已使用容量fi≤aj的剩余容量sj，那么我們就稱這兩個(gè)倉(cāng)庫(kù)是相容的。

倉(cāng)庫(kù)分配問(wèn)題就轉(zhuǎn)換為求出最多相容的倉(cāng)庫(kù)集合A。其步驟如下：

(1) 將所有原材料所占面積按照從小到大的順序排列，得到集合E={a1,a2,…,an}；

(2) 先將a1入選到集合A中，得到A={a1}；

(3) 依次考察原材料ai，若ai的占地空間不小于當(dāng)前入選進(jìn)A的材料占地面積，就將ai加入到A中，否則就放棄ai。

2.1.2正確性證明

按照原材料的占地面積從小到大順序排列的集合E={a1,a2,…an}，不難看出a1的占地面積最小。假設(shè)存在這樣的最優(yōu)安排，其不包括a1，也就是倉(cāng)庫(kù)可以存入ai原材料，根據(jù)入選A的要求，亦不難得出除去原材料a1，其余都是不相容的最優(yōu)原材料集合。下面我們結(jié)合例子來(lái)求出倉(cāng)庫(kù)分配的最優(yōu)解。給出了10個(gè)倉(cāng)庫(kù)的剩余容量和已使用容量，用貪心算法求出最優(yōu)的倉(cāng)庫(kù)數(shù)目。

(1) 將原材料按照占地面積從小到大的順序排列，如表1所示。

表1　倉(cāng)庫(kù)分配表

(2) 先將a1放入倉(cāng)庫(kù)集合A1中，然后按照順序檢索原材料的占地面積，可以看出a3原材料的占地面積不小于原材料a1的占地面積，因此將a3添加到集合A1中，依次做法將a5,a6,a8,a10放入集合A1中，經(jīng)過(guò)一輪的選擇集合A1={a1,a3,a5,a6,a8,a10}。

(3) 經(jīng)過(guò)選取，沒(méi)有原材料相容于A1中了，接著上述的做法不難得到A2={a2,a7}，A3={a4,a9}。

(4) 得出總的倉(cāng)庫(kù)數(shù)目為N=3。

2.2船舶航行過(guò)程中加油次數(shù)的優(yōu)化問(wèn)題

2.2.1問(wèn)題描述

行船加油是船舶行駛過(guò)程中一項(xiàng)非常重要且繁雜的工作，遠(yuǎn)程航行的船舶在航行過(guò)程中都要經(jīng)歷數(shù)次的加油過(guò)程。船舶的加油工作一般都是在海上進(jìn)行的，由于風(fēng)浪等作用的影響,加油過(guò)程中出現(xiàn)安全事故的可能性極大,需要進(jìn)行實(shí)時(shí)的監(jiān)測(cè)與控制,所花費(fèi)的人力、物力、財(cái)力都非常大，如何設(shè)計(jì)算法，計(jì)算出最優(yōu)加油方案，使得船舶在指定位置的加油站加油才能使加油的次數(shù)最少，從而最大限度地減少成本。解決此問(wèn)題就需要用到貪心算法。在此問(wèn)題的解決中，我們把海上加油船、港口加油站統(tǒng)一稱為加油站。

假設(shè)船舶在加滿油后開(kāi)始航行，能夠航行n km。船舶在途中會(huì)經(jīng)過(guò)k個(gè)加油站，要使船舶在航行途中停泊加油的次數(shù)最少。對(duì)于給定的信息(即加滿油能航行n km和航行途中會(huì)有k個(gè)加油站位置)，設(shè)計(jì)算法，使得船舶在給定位置的加油站加油才能使加油次數(shù)最少。下面我們來(lái)分析各種情況下如何求解問(wèn)題。

設(shè)加油的最少次數(shù)為m，兩站之間的距離為L(zhǎng)[i](第i-1個(gè)加油站到第i個(gè)加油站的距離)，始點(diǎn)到終點(diǎn)的距離為S。

當(dāng)始點(diǎn)到終點(diǎn)的距離小于n時(shí)：則最少加油次數(shù)為0。

當(dāng)始點(diǎn)到終點(diǎn)的距離大于n時(shí)，則：

(1) 加油站之間的距離相等且等于n，加油的最少次數(shù)為k；

(2) 加油站之間的距離相等且大于n，那么將無(wú)法到達(dá)終點(diǎn)；

(3) 加油站之間的距離相等且小于n，加油的最少次數(shù)為S/n(當(dāng)n%L=0時(shí))或者(S/n)+1(當(dāng)n%L≠0時(shí))；

(4) 加油站之間的距離不等且到達(dá)第一個(gè)加油站的距離小于等于n,那么可以用貪心算法來(lái)求得加油的最少次數(shù)。

2.2.2貪心選擇性

貪心選擇來(lái)得到問(wèn)題的最優(yōu)解就是通過(guò)一系列的局部最優(yōu)選擇來(lái)達(dá)到的。對(duì)于給定的問(wèn)題我們要證明它具有貪心選擇性，就必須證明每一步所做的貪心選擇最終會(huì)導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。假設(shè)在加滿油后能夠航行的n km航程中任意取兩個(gè)加油站，加油站1比加油站2距離出發(fā)點(diǎn)近一些，如果在2點(diǎn)加油達(dá)不到終點(diǎn)，那么在1點(diǎn)加油更不可能到達(dá)終點(diǎn)，1點(diǎn)和2點(diǎn)的距離為S′，那么在2點(diǎn)加油比在1點(diǎn)加油能多航行S′ km。若終點(diǎn)不在1和2之間且在2點(diǎn)的右邊，根據(jù)貪心選擇為使加油次數(shù)最少，就得前往距離加滿油遠(yuǎn)一點(diǎn)的加油站加油。因此加油次數(shù)最少滿足貪心選擇性。

2.2.3最優(yōu)子結(jié)構(gòu)性

當(dāng)問(wèn)題的最終最優(yōu)解包含它的子問(wèn)題的最優(yōu)解時(shí)，就稱問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。在船舶加油的過(guò)程中，等到不能行駛到下一個(gè)加油站時(shí)我們才在當(dāng)前的加油站加油，每次從加油開(kāi)始到下一次加油滿足貪心選擇性，且加完油后又具有與開(kāi)始行使時(shí)相同的情況，這一過(guò)程又是獨(dú)立的，所以說(shuō)加油的最少次數(shù)又具有最優(yōu)子結(jié)構(gòu)的特性。

3總結(jié)

貪心算法是一種改進(jìn)的分級(jí)處理方法，有時(shí)會(huì)更便于我們求解問(wèn)題的最優(yōu)解。當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)時(shí)，相比于動(dòng)態(tài)規(guī)劃，貪心算法可以更好地處理該類問(wèn)題。在動(dòng)態(tài)規(guī)劃中，每一個(gè)父問(wèn)題的得出需要它的子問(wèn)題作為條件，而貪心算法每一個(gè)子問(wèn)題并不依賴另一個(gè)子問(wèn)題。在用貪心算法處理最優(yōu)問(wèn)題時(shí)，必須保證每一步作出的選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。它的解題流程大致有：(1) 讀入一個(gè)問(wèn)題；(2) 進(jìn)行貪心排序(當(dāng)前環(huán)境下作出最貪心的選擇排在最前)；(3) 處理問(wèn)題；(4) 得出綜合結(jié)果。

貪心算法簡(jiǎn)單、高效、容易理解，因此其往往是解決問(wèn)題最好的備選方案之一，將其盡可能地應(yīng)用在船舶建設(shè)領(lǐng)域具有十分深遠(yuǎn)的意義。

參考文獻(xiàn)

[1]Alsuwaiyel M H.算法設(shè)計(jì)技巧與分析[M].北京：電子工業(yè)出版社，2004.

[下轉(zhuǎn)第37頁(yè)]

The Discussion of the Greedy Algorithm and Its Application

in the Field of Ship

YAO Ju-ju

(Shanghai Jiangnan Shipbuilding Pipesystem Co., Ltd., Shanghai 201302, China)

AbstractThe basic idea of the greedy algorithm is that it is in solving the optimal solution from the initial state, through a series of choices, and those choices in the current environment can make the best choice, and ultimately the whole issue of optimal solution. It's not difficult to find that the greedy algorithm can only reach a local optimal solution, the choice made for the current depend on the choice made by the past, rather than the choices made by the future, and not rely on sub-solution. This point determines the greedy algorithm in solving the problem own the advantage of a certain speed. So it is one of the alternative optimal solutions in solving problem. The article discusses the greedy algorithm ideas, processes, the core idea, the basic properties and the limitations. We also study the classic problem resolution to know it deeply.

KeywordsGreedy algorithmHuffman algorithmSingle source shortest path

中圖分類號(hào)O224

文獻(xiàn)標(biāo)志碼A

作者簡(jiǎn)介：姚菊菊(1990-)，男，助理工程師。