贪心算法的探讨及其在船舶领域的应用

姚菊菊

(上海江南船舶管业有限公司， 上海 201302)



贪心算法的探讨及其在船舶领域的应用

姚菊菊

(上海江南船舶管业有限公司， 上海 201302)

摘要贪心算法是在求问题的最优解时，从最初的状态，通过一系列在当前环境下所能做出的最优的选择而得到整个问题的最优解，这便是贪心算法的基本思想。从中不难发现，贪心算法只能达到局部的最优解，它对于当前做出的选择只依赖于以往做出的选择，而不与未来做出的选择相关，即不依赖子问题的解。这也就决定了贪心算法在解决问题时有一定的速度优势，由于此解决问题的优势使得它成为最优方案的备选方法之一。本文论述了贪心算法的实现思路和过程、核心思想、基本特性、特点以及存在的问题，并详细论述了其在船舶建设领域中的几点应用。

关键词贪心算法哈弗曼算法单源最短路径

0引言

当今是信息化社会，计算机的算法通常被运用于处理较大信息量的数据，以快速解决实际问题。为了使算法针对实际问题获得更好的性能，需要对算法进行改进。

贪心算法的思想就是从问题的初状态出发，通过一系列的贪心选择来得到解决问题最优解的一种解题方法。通过对当前状态下所作出最好的选择来实现最优解，它所适用的范围是问题具有最优子结构和贪心选择，并运用贪心选择的策略给出简便和高效的解决方法。本文通过对贪心算法进行深入研究，分析了其在船舶领域的实际应用(船舶建设中仓库的分配优化问题)。总之，正是因为贪心算法简单、高效、容易理解，所以其往往是解决问题最好的备选方案之一，将其尽可能地应用在船舶建设领域具有十分深远的意义。

1贪心算法的知识概述

1.1贪心算法的简单描述

所谓的贪心算法是在问题的处理过程中，对于每一次做出的选择都是在当前状态下最好或最优的选择，从而使得结果是最优的算法[1]。即对于一组数据进行排序，找出最小值，并进行处理；接着再找出最小值，进行处理，直到问题解决。

贪心算法是对问题在具有某种度量意义的情况下进行分级处理的方法，它是通过一系列的选择来得到问题的解，而这些选择是当前能做出的最好选择，具有贪心的意义，即贪心选择。从而不难看出这种算法是通过局部最优解来求解整体最优解。这种方法很容易被人理解，经常被人们所采用。它除了简单，高效，也有其弊端，不是所有的问题采用贪心算法都能够得到整体最优解，有时得到的只是最优解的相似值[2]。

1.2贪心算法的解题思路和过程

1.2.1贪心算法的解题思路

用贪心算法解题的整体思想就是以局部的方法最终求得全局解，即将问题划分成若干个子问题，直到解决无法再划分的问题为止。贪心算法的基本思想就是各个解决，处理的子问题的结果都是当前看来最好的解。用贪心算法解题，需要考虑两个问题：

(1) 该问题是否符合用贪心算法求解；

(2) 如何规范贪心算法的标准，得到最优解[3]。

1.2.2贪心算法的解题过程

(1) 使用同样的规则，将问题划分成若干相似子问题；

(2) 从问题的初始状态开始，给出一个可行性的解元素；

(3) 将所有的解元素组合成最终问题的可行性解[3]。

1.2.3贪心算法的理论研究基础

从之前的分析我们不难发现，贪心算法是比较符合人类认知思维解决最优问题的方法。为了在使用之时无后顾之忧，我们必须要验证它的正确性。下面就用“拟阵”理论来证明。

“拟阵”理论能够证明运用贪心算法何时产生最优解，在求解最优解的问题中发挥着重要作用。

拟阵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}第一个成为独立子集的元素，则存在最优子集 A 使得 x ∈ A (拟阵的贪心选择性)。

假设2设M{S , I } 为拟阵，若 S 中 x 不是空集的一个可扩元素，则 x 也不可能是 S中的任意子集 A的可扩元素。

假设3(拟阵的最优子结构性质)设x 是求带权拟阵 M{S , I } 的最优子集的贪心算法所选择 S 中的第一个元素。那么原问题可化简求为带权拟阵M′{S′ , I ′}的最优子问题，其中

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的带权拟阵，贪心算法能够返回最优子集。

能够使用贪心算法来解题的很多问题都可以归纳成在加权拟阵中找出一个具有最大权值的独立子集问题，即给定一个加权拟阵M{S , I} ，若能找到一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。拟阵对于我们判断问题是否适用贪心算法有非常大的帮助，对于大多数信息问题，只要满足拟阵结构，便可以运用贪心策略求解。

1.3贪心算法的基本要素

1.3.1贪心选择性质

贪心算法的第一个要素就是问题具有贪心选择的性质。贪心选择性质能够通过局部最优解求得整体的最优解，也就是经过若干步骤的贪心选择来达到最优的结果。

贪心算法和动态规划最大的区别也就是在于贪心选择。贪心算法中，能够仅在当前状态下做出最优选择，这种选择依赖于上一步的选择，但不依赖将来子问题的选择；而动态规划中，所做出的选择往往依赖子问题的解。正是这种差别贪心算法是自顶而下的方式进行，每做出一次选择就把问题化简成规模更小的子问题，而动态规划则是从底往上的方式解决各个问题[4]。要确定问题是否具有贪心选择的性质，必须要证明每一步的贪心选择能够得到整体最优解。第一要考虑该问题的整体最优解，使其从贪心选择开始，做出贪心选择之后，问题就变成规模更小的相似子问题，接着用数学归纳法证明每一步的贪心选择都能够得到整体最优解。

1.3.2最优子结构性质

因为贪心算法是通过局部最优解实现整体最优解，所以待解决的问题必须具有最优子结构性质。最优子结构性质是问题的最优解包括其子问题的最优解。问题的最优子结构性质是贪心算法解题的关键特征。贪心算法的每一次操作都对结构产生直接的影响，对每一个子问题都做出了解决方案，是不能够回退的。

1.4贪心算法的优缺点

说到贪心算法的特点，不得不说到简化、高效、容易理解。贪心算法通常是线性二次式，所以它占有的内存少，再加之其容易编写，方便调试，所以决定了它必定具有高效快速的优势。在选择使用贪心算法的同时，我们也应该考虑应用该种方法来达到目的。如何选择贪心算法并能够验证最优的正确性是考验我们的难题。同时它也存在着不足：

(1) 贪心算法并不适用于所有问题的最优解，即它适用的范围具有局限性；

(2) 贪心策略的应用对待解决的问题要求比较严格，具有贪心选择性和最优子结构性；

(3) 贪心算法对于有些问题只能确定其可行性范围，例如临界问题。

2贪心算法在船舶领域的应用

2.1船舶生产过程中仓库使用的优化问题

2.1.1问题描述

由于船舶生产的特殊性，生产过程中所涉及到的原材料种类繁多，型号品种更是复杂多样。单是管材就包括不锈钢管、碳钢管、铜镍合金管等，此外还有各种管附件，比如法兰、弯头、三通、复板、垫片、同心异径、偏心异径等，而且每种原材料在生产中的重要性都是等同的。如何使用最少数量的仓库，来满足生产需求，保证各种原材料的及时供应，是船舶生产过程中需要迫切解决的问题，这就要求在生产过程中合理有效地安排、分配仓库，使用尽可能少的仓库来满足生产需要。解决这个问题我们就可以使用贪心算法。

在处理此问题的过程中，我们需要考虑的问题是怎样根据仓库的容量、使用状态来安排仓库，使其能够以最高效率派上用场。我们将问题简化如下：挑选两个仓库成为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的占地面积最小。假设存在这样的最优安排，其不包括a1，也就是仓库可以存入ai原材料，根据入选A的要求，亦不难得出除去原材料a1，其余都是不相容的最优原材料集合。下面我们结合例子来求出仓库分配的最优解。给出了10个仓库的剩余容量和已使用容量，用贪心算法求出最优的仓库数目。

(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船舶航行过程中加油次数的优化问题

2.2.1问题描述

行船加油是船舶行驶过程中一项非常重要且繁杂的工作，远程航行的船舶在航行过程中都要经历数次的加油过程。船舶的加油工作一般都是在海上进行的，由于风浪等作用的影响,加油过程中出现安全事故的可能性极大,需要进行实时的监测与控制,所花费的人力、物力、财力都非常大，如何设计算法，计算出最优加油方案，使得船舶在指定位置的加油站加油才能使加油的次数最少，从而最大限度地减少成本。解决此问题就需要用到贪心算法。在此问题的解决中，我们把海上加油船、港口加油站统一称为加油站。

假设船舶在加满油后开始航行，能够航行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贪心选择性

贪心选择来得到问题的最优解就是通过一系列的局部最优选择来达到的。对于给定的问题我们要证明它具有贪心选择性，就必须证明每一步所做的贪心选择最终会导致问题的一个整体最优解。假设在加满油后能够航行的n km航程中任意取两个加油站，加油站1比加油站2距离出发点近一些，如果在2点加油达不到终点，那么在1点加油更不可能到达终点，1点和2点的距离为S′，那么在2点加油比在1点加油能多航行S′ km。若终点不在1和2之间且在2点的右边，根据贪心选择为使加油次数最少，就得前往距离加满油远一点的加油站加油。因此加油次数最少满足贪心选择性。

2.2.3最优子结构性

当问题的最终最优解包含它的子问题的最优解时，就称问题具有最优子结构性质。在船舶加油的过程中，等到不能行驶到下一个加油站时我们才在当前的加油站加油，每次从加油开始到下一次加油满足贪心选择性，且加完油后又具有与开始行使时相同的情况，这一过程又是独立的，所以说加油的最少次数又具有最优子结构的特性。

3总结

贪心算法是一种改进的分级处理方法，有时会更便于我们求解问题的最优解。当一个问题具有最优子结构时，相比于动态规划，贪心算法可以更好地处理该类问题。在动态规划中，每一个父问题的得出需要它的子问题作为条件，而贪心算法每一个子问题并不依赖另一个子问题。在用贪心算法处理最优问题时，必须保证每一步作出的选择最终导致问题的整体最优解。它的解题流程大致有：(1) 读入一个问题；(2) 进行贪心排序(当前环境下作出最贪心的选择排在最前)；(3) 处理问题；(4) 得出综合结果。

贪心算法简单、高效、容易理解，因此其往往是解决问题最好的备选方案之一，将其尽可能地应用在船舶建设领域具有十分深远的意义。

参考文献

[1]Alsuwaiyel M H.算法设计技巧与分析[M].北京：电子工业出版社，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-)，男，助理工程师。