java贪婪算法

A. 贪婪算法之——最小耗费生成树

在例 及 中已考察过这个问题 因为具有n 个顶点的无向网络G的每个生成树刚好具有n 条边 所以问题是用某种方法选择n 条边使它们形成G的最小生成树 至少可以采用三种不同的贪婪策略来选择这n 条边 这三种求解最小生成树的贪婪算法策略是 K r u s k a l算法 P r i m算法和S o l l i n算法

Kruskal算法

( ) 算法思想

K r u s k a l算法每次选择n 条边 所使用的贪婪准则是 从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中 注意到所选取的边若产生环路则不可能形成一棵生成树 K r u s k a l算法分e 步 其中e 是网络中边的数目 按耗费递增的顺序来考虑这e 条边 每次考虑一条边 当考虑某条边时 若将其加入到已选边的集合中会出现环路 则将其抛弃 否则 将它选入

考察图 a 中的网络 初始时没有任何边被选择 图 b 显示了各节点的当前状态 边( )是最先选入的边 它被加入到欲构建的生成树中 得到图 c 下一步选择边( )并将其加入树中(如图 d所示) 然后考虑边( ) 将它加入树中并不会产生环路 于是便得到图 e 下一步考虑边( )并将其加入树中(如图 f所示) 在其余还未考虑的边中 ( )具有最小耗费 因此先考虑它 将它加入正在创建的树中会产生环路 所以将其丢弃 此后将边( )加入树中 得到的树如图 g 所示 下一步考虑边( ) 由于会产生环路 将其丢弃 最后考虑边( )并将其加入树中 产生了一棵生成树 其耗费为 图 给出了K r u s k a l算法的伪代码

/ /在一个具有n 个顶点的网络中找到一棵最小生成树

令T为所选边的集合 初始化T=

令E 为网络中边的集局野合

w h i l e(E≠ )&&(| T |≠n ) {

令(u v)为E中代价最小的边 E=E { (u v) } / /从E中删除边

i f( (u v)加入T中不会产生环路)将( u v)加入T

}

i f(| T | = =n ) T是最小耗费生成树

e l s e 网络不是互连的 不能找到生成树

图 Kruskao算法的伪代码

( ) 正确性证明

利用前述装载问题所用的转化技术可以证明图 的贪婪算法总能建立一棵最小耗费生成树 需要证明以下两点 ) 只要存羡旅在生成树 K r u s k a l算法总能产生一棵生成树; ) 产生的生成树具有最小耗费 令G为任意加权无向图(即G是一个无向网络) 从 节可知当且仅当一个无向图连通时它有生成树 而且在Kruskal 算法中被拒绝(丢弃)的边是那些会产生环路的边 删除连通图环路中的一条边所形成兄腊凳的图仍是连通图 因此如果G在开始时是连通的 则T与E中的边总能形成一个连通图 也就是若G开始时是连通的 算法不会终止于E= 和| T |< n

现在来证明所建立的生成树T具有最小耗费 由于G具有有限棵生成树 所以它至少具有一棵最小生成树 令U为这样的一棵最小生成树 T与U都刚好有n 条边 如果T=U 则T就具有最小耗费 那么不必再证明下去 因此假设T≠U 令k(k > ) 为在T中而不在U中的边的个数 当然k 也是在U中而不在T中的边的数目 通过把U变换为T来证明U与T具有相同的耗费 这种转化可在k 步内完成 每一步使在T而不在U中的边的数目刚好减 而且U的耗费不会因为转化而改变 经过k 步的转化得到的U将与原来的U具有相同的耗费 且转化后U中的边就是T中的边 由此可知 T具有最小耗费 每步转化包括从T中移一条边e 到U中 并从U中移出一条边f 边e 与f 的选取按如下方式进行

) 令e 是在T中而不在U中的具有最小耗费的边 由于k > 这条边肯定存在

) 当把e 加入U时 则会形成唯一的一条环路 令f 为这条环路上不在T中的任意一条边

由于T中不含环路 因此所形成的环路中至少有一条边不在T中

从e 与f 的选择方法中可以看出 V=U+ {e} { f } 是一棵生成树 且T中恰有k 条边不在V中出现 现在来证明V的耗费与U的相同 显然 V的耗费等于U的耗费加上边e 的耗费再减去边f 的耗费 若e 的耗费比f 的小 则生成树V的耗费比U的耗费小 这是不可能的 如果e 的耗费高于f 在K r u s k a l算法中f 会在e 之前被考虑 由于f 不在T中 Kruskal 算法在考虑f 能否加入T时已将f 丢弃 因此f 和T中耗费小于或等于f 的边共同形成环路 通过选择e 所有这些边均在U中 因此U肯定含有环路 但是实际上这不可能 因为U是一棵生成树 e 的代价高于f 的假设将会导致矛盾 剩下的唯一的可能是e 与f 具有相同的耗费 由此可知V与U的耗费相同

( ) 数据结构的选择及复杂性分析

为了按耗费非递减的顺序选择边 可以建立最小堆并根据需要从堆中一条一条地取出各边 当图中有e 条边时 需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边 边的集合T与G中的顶点一起定义了一个由至多n 个连通子图构成的图 用顶点集合来描述每个子图 这些顶点集合没有公共顶点 为了确定边( u v)是否会产生环路 仅需检查u v 是否在同一个顶点集中(即处于同一子图) 如果是 则会形成一个环路;如果不是 则不会产生环路 因此对于顶点集使用两个F i n d操作就足够了 当一条边包含在T中时 个子图将被合并成一个子图 即对两个集合执行U n i o n操作 集合的F i n d和U n i o n操作可利用 节的树(以及加权规则和路径压缩)来高效地执行 F i n d操作的次数最多为 e Un i o n操作的次数最多为n (若网络是连通的 则刚好是n 次) 加上树的初始化时间 算法中这部分的复杂性只比O (n+e) 稍大一点

对集合T所执行的唯一操作是向T中添加一条新边 T可用数组t 来实现 添加操作在数组的一端进行 因为最多可在T中加入n 条边 因此对T的操作总时间为O (n)

总结上述各个部分的执行时间 可得图 算法的渐进复杂性为O (n+el o ge)

( ) 实现

利用上述数据结构 图 可用C + +代码来实现 首先定义E d g e N o d e类(见程序 ) 它是最小堆的元素及生成树数组t 的数据类型

程序 Kruskal算法所需要的数据类型

template

class EdgeNode {

p u b l i c :

operator T() const {return weight;}

p r i v a t e :

T weight;//边的高度

int u v;//边的端点

} ;

为了更简单地使用 节的查找和合并策略 定义了U n i o n F i n d类 它的构造函数是程序 的初始化函数 U n i o n是程序 的加权合并函数 F i n d是程序 的路径压缩搜索函数

为了编写与网络描述无关的代码 还定义了一个新的类U N e t Wo r k 它包含了应用于无向网络的所有函数 这个类与U n d i r e c t e d类的差别在于U n d i r e c t e d类中的函数不要求加权边 而U N e t Wo r k要求边必须带有权值 U N e t Wo r k中的成员需要利用N e t w o r k类中定义的诸如B e g i n和N e x t Ve r t e x的遍历函数 不过 新的遍历函数不仅需要返回下一个邻接的顶点 而且要返回到达这个顶点的边的权值 这些遍历函数以及有向和无向加权网络的其他函数一起构成了W N e t w o r k类(见程序 )

程序 WNeork类

template

class WNeork : virtual public Neork

{

public :

virtual void First(int i int& j T& c)= ;

virtual void Next(int i int& j T& c)= ;

} ;

象B e g i n和N e x t Ve r t e x一样 可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类中加入函数F i r s t与N e x t 现在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r k中派生而来 由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p h类需要访问U N e t w o r k的成员 所以这两个类还必须从U N e t Wo r k中派生而来 U N e t Wo r k : : K r u s k a l的代码见程序 它要求将Edges() 定义为N e t Work 类的虚成员 并且把U N e t Wo r k定义为E d g e N o d e的友元) 如果没有生成树 函数返回f a l s e 否则返回t r u e 注意当返回true 时 在数组t 中返回最小耗费生成树

程序 Kr u s k a l算法的C + +代码

template

bool UNeork ::Kruskal(EdgeNode t[])

{// 使用K r u s k a l算法寻找最小耗费生成树

// 如果不连通则返回false

// 如果连通 则在t [ : n ]中返回最小生成树

int n = Ve r t i c e s ( ) ;

int e = Edges();

/ /设置网络边的数组

InitializePos(); // 图遍历器

EdgeNode *E = new EdgeNode [e+ ];

int k = ; // E的游标

for (int i = ; i <= n; i++) { // 使所有边附属于i

int j;

T c;

First(i j c);

while (j) { // j 邻接自i

if (i < j) {// 添加到达E的边

E[++k] weight = c;

E[k] u = i;

E[k] v = j;}

Next(i j c);

}

}

// 把边放入最小堆

MinHeap > H( );

H Initialize(E e e);

UnionFind U(n); // 合并/搜索结构

B. 找零钱问题 [贪心算法](java实现）

public getMin{

public int MinNumber=0;

public int findMax(int[] a){
for(int i=0;i<a.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}

public boolean Compare(int a,int b){
public boolean flag=true;
if(a>b) flag=flase;
return flag;
}

public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];

int index=0;

for(int i=0;i<M.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}

int max = this.findMax(findM);
MinNumber++;

if((Money-max)!=0) {
getMinNumber(M,Money-max)
}

return MinNumber;
}

public int[] Start(){
System.out.println("请输入查询组数");
int group=System.in.read();

int[] M={1,2,5,10,20,50,100};

int[] Result = new Int[group];
int index=0;

while (group-- > 0){
System.out.println("请输入金额");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}

public void print(int[] MinNumber){
for(int i=0;i<MinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}

public static void main(String[] args){
new getMin().print(new getMin().Start());
}

没测试啊，有问题请勿喷，呵呵

C. 贪心算法的特性

贪婪算法可解决的问题通常大部分都有如下的特性：
⑴随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
⑵有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
⑶还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
⑸最后，目标函数给出解的值。
⑹为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。