第八章 贪心算法.ppt

算法设计与分析
Algorithms Design and Analysis
赵廷刚
兰州城市学院数学学院

本章内容
引言
最短路径问题
最小耗费生成树(Kruskal算法)
最小耗费生成树(Prim算法)
文件压缩
引言
贪心算法:通常用来求解最优化问题,即量的最大化或最小化。
贪心算法通常包含一个用以寻找局部最优解的迭代过程。在某些实例中,这些局部最优解转变为全局最优解,而在另外一些情形下,则无法得到最优解。
贪心算法在少量计算的基础上做出正确猜想而不急于考虑以后的情况,这样,它一步步地来构造解,每一步均是建立在局部最优解的基础上,而每一步又都扩大了部分解的规模,做出的选择产生最大收益而又保持可行性。由于每一步工作量少且基于少量信息,所以算法特别有效。
设计贪心算法的困难:证明该算法确实能得到问题最优解。
最短路径问题
问题:设G=(V,E)是一个每个边都有非负长度的有向图,有一个特别顶点s称为源。问题是要确定从顶点s到V中每一其它顶点的距离,称为单源最短路径问题。假设V={1,2,…,n}, s=1.
Dijkstra算法:初始时,将顶点分为两个集合X={1}和Y={2,3,…,n}。这样做的目的是让X包含这样的顶点:从源点到这些顶点的距离已经确定。在每一步中,我们选择源点到它的距离已经获得的一个顶点y∈Y,并将这个顶点移到X中。与Y中的每一个顶点y联系的是标号λ[y],它是只经过X中顶点的最短路径的长度,一旦顶点y移到X中,与y相邻的每个顶点w的标号就被更新,这表示找到了经过y到w的更短路径。对每个顶点v∈V, δ[v]表示从源点到v的距离,算法结束时,对所有v∈V, δ[v]= λ[y].
算法概要如下:
function [lmd,y1]=DIJKSTRA(A)
[n,m]=size(A);X=[1,zeros(1,n-1)];Y=[0,ones(1,n-1)];
lmd(1)=0;y1(1)=1;
for y=2:n
if A(1,y)~=inf, lmd(y)=A(1,y);else lmd(y)=inf; end
end
for j=1:n-1
y=find(lmd==min(lmd(Y==1))); y1(j+1)=y;
X(y)=1; Y(y)=0;
for k=find(X==1);
for j=find(Y==1);
if (lmd(k)+A(k,j)<lmd(j)),lmd(j)=lmd(k)+A(y,j); end
end
end
end
Matlab代码