貪心算法的探討及其在船舶領域的應用

姚菊菊

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

?

貪心算法的探討及其在船舶領域的應用

姚菊菊

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

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

關鍵詞貪心算法哈弗曼算法單源最短路徑

0引言

當今是信息化社會，計算機的算法通常被運用于處理較大信息量的數據，以快速解決實際問題。為了使算法針對實際問題獲得更好的性能，需要對算法進行改進。

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

1貪心算法的知識概述

1.1貪心算法的簡單描述

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

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

1.2貪心算法的解題思路和過程

1.2.1貪心算法的解題思路

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

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

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

1.2.2貪心算法的解題過程

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

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

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

1.2.3貪心算法的理論研究基礎

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

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

擬陣M 定義成滿足以下 3 個條件的有序對 (S ,I) ：

(1) S是非空有限集；

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

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

A∪{x}=∈I。

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

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

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

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

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

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

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

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

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

1.3貪心算法的基本要素

1.3.1貪心選擇性質

貪心算法的第一個要素就是問題具有貪心選擇的性質。貪心選擇性質能夠通過局部最優(yōu)解求得整體的最優(yōu)解，也就是經過若干步驟的貪心選擇來達到最優(yōu)的結果。

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

1.3.2最優(yōu)子結構性質

因為貪心算法是通過局部最優(yōu)解實現(xiàn)整體最優(yōu)解，所以待解決的問題必須具有最優(yōu)子結構性質。最優(yōu)子結構性質是問題的最優(yōu)解包括其子問題的最優(yōu)解。問題的最優(yōu)子結構性質是貪心算法解題的關鍵特征。貪心算法的每一次操作都對結構產生直接的影響，對每一個子問題都做出了解決方案，是不能夠回退的。

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

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

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

(2) 貪心策略的應用對待解決的問題要求比較嚴格，具有貪心選擇性和最優(yōu)子結構性；

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

2貪心算法在船舶領域的應用

2.1船舶生產過程中倉庫使用的優(yōu)化問題

2.1.1問題描述

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

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

倉庫分配問題就轉換為求出最多相容的倉庫集合A。其步驟如下：

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

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

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

2.1.2正確性證明

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

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

表1　倉庫分配表

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

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

(4) 得出總的倉庫數目為N=3。

2.2船舶航行過程中加油次數的優(yōu)化問題

2.2.1問題描述

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

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

設加油的最少次數為m，兩站之間的距離為L[i](第i-1個加油站到第i個加油站的距離)，始點到終點的距離為S。

當始點到終點的距離小于n時：則最少加油次數為0。

當始點到終點的距離大于n時，則：

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

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

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

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

2.2.2貪心選擇性

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

2.2.3最優(yōu)子結構性

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

3總結

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

貪心算法簡單、高效、容易理解，因此其往往是解決問題最好的備選方案之一，將其盡可能地應用在船舶建設領域具有十分深遠的意義。

參考文獻

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

[下轉第37頁]

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

中圖分類號O224

文獻標志碼A

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