算法设计与分析论文

double[] p = newdouble[a[0].length]; // the price of goods System.arraycopy(a[1], 0, p, 0, p.length); // copy the array double[] pw = newdouble[w.length]; for (int i = 0; i < w.length; i++)

// price/weight pw[i] = p[i] / w[i];

// weight and pw

double[][] wpw = newdouble[2][w.length]; // record the table of System.arraycopy(w, 0, wpw[0], 0, w.length); System.arraycopy(pw, 0, wpw[1], 0, w.length); EnumerationSearch sea = new EnumerationSearch(); Quick.Sort(pw);

int i = (pw.length - 1);

int j = sea.search(wpw[1], pw[i]); while (wpw[0][j] <= c && i >= 0) { } }

c = c - wpw[0][j]; ans[j] = 1; i--;

j = sea.search(wpw[1], pw[i]);

程序运行结果见附录。

根据程序运行的结果，我们分别得到三个答案。放置的物品方案分别为：

10?20、30?20、10?30。如此看来，根据价格的贪心策略是最“贪心”的。

其实不然，根据价格与重量比值的贪心策略的适应范围更加广阔，效果一般来说也更加的好。本例中受到小数据的局限性，无法发挥出其真正的效果。

贪心策略之所以能成为贪心算法的核心，就是因为它决定着贪心算法是爆发还是灭亡，以及爆发的程度。上面的例子用三种不同的贪心策略，结果也截然不同。当扩大问题规模时，这种差距就更加的明显。

5. 贪心算法的特点

货郎担问题(或称旅行商问题或巡回售货员问题)，是NP问题中的著名问题。它通常的提法是：货郎到各村去卖货，再回到出发点处，每村到且仅到一次。为其设计一种路线，使得所用旅行售货的时间最短。

建立数学模型时，把村庄设为结点，村庄与村庄之间的路线设为结点之间的

带权的边，则货郎担问题转化为在图上寻求最优Hamilton圈问题。即在加权图上求一个Hamilton圈Ch使得

W(Ck)?w(e)??eC?k min{各个Hamilton圈的权}。贪心算法每选入一边都保证了是当前可选边中权值最小的边，这便是“贪心”的含义。基本思想为首先选择图中任意顶点u，并将u置于顶点集合的子集S中。如果S是顶点集合V的真子集，就继续选择顶点j添加到子集S中，c[i][j]是权值最小的边。按照同样的步骤不断进行贪心选择，直到子集S=V为止。此时，选取到的所有的边就构成了一棵最小生成树。伪代码如下：

publicvoid find(int[][] distance,int[] ans)

{ } {

int minN=0; int temp=100;

EnumerationSearch sea = new EnumerationSearch(); for(int i=0;i

if(sea.search(b, (i+1))==-1)

if(a[i]

temp=a[i]; minN=i;

int j=1; //starting city

for(int i=0;i

ans[i]=j;

j=min(distance[j-1],ans);

privateint min(int[] a,int[] b)

程序运行结果见附录。

同时我们运用动态规划法来求解同样的问题，问题规模为8个城市。动态求解过程需要使用10ms的时间，而贪心算法只需要使用1ms以内的时间即可完成

计算，我们可以理解到贪心算法的爆发力了。但是，它们的结果并不相同。动态规划法求解的答案为：1->3->5->8->4->6->7->2->1，而贪心算法的答案为：

1->3->4->2->5->6->7->8->1。动态规划法需要走的路程为21，而贪心算法需要

走的路程为25。这就是贪心算法的特点，虽快但不一定准。贪心算法每次都是局部寻优，很容易会陷入局部最优解的波谷。所以，贪心算法总结起来一共有三个小缺点。

1) 不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是

最优的选择，因此并不从整体上加以考虑。

2) 贪心算法只能用来求某些最大或最小解的问题。从前面的讨论中，背包

问题要求得到最大价值是可行的，但是在另外一个求解最小路径时采用贪心算法得到的结果并不是最佳。

3) 贪心算法只能确定某些问题的可行性范围。

贪心算法的优点已经提到了，就是快，通常是线性到二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用!因为它容易编写，容易调试，速度极快，并且节约空问。几乎可以说，此时它是所有算法中最好的。

6. 结束语

贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。

总之，如果一个贪心解决方案存在，就使用它。

7. 参考文献：

[1] 肖衡.浅析贪心算法[J].荆楚理工学院学报.2009.09

[2] 常友渠,肖贵元,曾敏.贪心算法的探讨与研究[J].重庆电力高等专科学校学

报.第13卷, 第3期

[3] 汪莹.论贪心算法在图论中的应用[J].南京邮电大学学报 [4] 董军军.动态规划算法和贪心算法的比较与分析[J].软件导刊. 7卷第2期

[5] 林章美.货郎担问题的若干解法[J].

[6] 王红梅.算法设计与分析[M].北京：清华大学出版社.2006.7 [7] 江红,余青松.Java程序设计教程[M].

第