中国数学建模-编程交流-贪婪算法 - 1(5)

2则表示顶点在B中。函数有两个输出参数： C和m，m为所建立的覆盖的大小， C [ 0 , m - 1

]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回f a l s e；否则返回t r u e。完整的代码见程序1 3 - 4。 程序13-4 构造贪婪覆盖

bool Undirected::BipartiteCover(int L[], int C[], int& m) {// 寻找一个二分图覆盖

// L 是输入顶点的标号, L[i] = 1 当且仅当i 在Ａ中 // C 是一个记录覆盖的输出数组

// 如果图中不存在覆盖，则返回f a l s e // 如果图中有一个覆盖，则返回t r u e ;

// 在m中返回覆盖的大小; 在C [ 0 : m - 1 ]中返回覆盖 int n = Ve r t i c e s ( ) ; // 插件结构

int SizeOfA = 0;

for (int i = 1; i <= n; i++) // 确定集合A的大小 if (L[i] == 1) SizeOfA++; int SizeOfB = n - SizeOfA; CreateBins(SizeOfB, n);

int *New = new int [n+1]; / /顶点i覆盖了Ｂ中N e w [ i ]个未被覆盖的顶点

bool *Change = new bool [n+1]; // Change[i]为t r u e当且仅当New[i] 已改变

bool *Cov = new bool [n+1]; // Cov[i] 为true 当且仅当顶点i 被覆盖 I n i t i a l i z e P o s ( ) ; LinkedStack S; // 初始化

for (i = 1; i <= n; i++) { Cov[i] = Change[i] = false; if (L[i] == 1) {// i 在A中

New[i] = Degree(i); // i 覆盖了这么多 InsertBins(New[i], i);}}

// 构造覆盖

int covered = 0, // 被覆盖的顶点 MaxBin = SizeOfB; // 可能非空的最大箱子 m = 0; // C的游标

while (MaxBin > 0) { // 搜索所有箱子 // 选择一个顶点

if (bin[MaxBin]) { // 箱子不空 int v = bin[MaxBin]; // 第一个顶点 C[m++] = v; // 把v 加入覆盖 // 标记新覆盖的顶点 int j = Begin(v), k; while (j) {

if (!Cov[j]) {// j尚未被覆盖 Cov[j] = true;

c o v e r e d + + ; // 修改N e w k = Begin(j);

while (k) {

New[k]--; // j 不计入在内 if (!Change[k]) {

S.Add(k); // 仅入栈一次 Change[k] = true;}

k = NextVe r t e x ( j ) ; } }

j = NextVe r t e x ( v ) ; } // 更新箱子

while (!S.IsEmpty()) { S . D e l e t e ( k ) ; Change[k] = false;

MoveBins(SizeOfB, New[k], k);} }

else MaxBin--; }

D e a c t i v a t e P o s ( ) ; D e s t r o y B i n s ( ) ; delete [] New; delete [] Change;

delete [] Cov;

return (covered == SizeOfB);

}

程序1 3 - 4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组C o

v和C h a n g e初始化为f a l s e，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。

为了构造覆盖，首先按SizeOfB 递减至1的顺序检查双向链表。当发现一个非空的表时，就将其第一个顶点v

加入到覆盖中，这种策略即为选择具有最大New 值的顶点。将所选择的顶点加入覆盖数组C并检查B中所有与它邻接的顶点。若顶点j 与v

邻接且还未被覆盖，则将C o v [ j ]置为t r u e，表示顶点j 现在已被覆盖，同时将已被覆盖的B中的顶点数目加1。由于j 是最近被覆盖的，所有A中与j 邻接的顶点的New 值减1。下一个while 循环降低这些New 值并将New

值被降低的顶点保存在一个栈中。当所有与顶点v邻接的顶点的Cov 值更新完毕后，N e

w值反映了A中每个顶点所能覆盖的新的顶点数，然而A中的顶点由于New 值被更新，处于错误的双向链表中，下一个while

循环则将这些顶点移到正确的表中。

----------------------------------------------

plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);

2004-5-27 19:40:53

b

等级：职业侠客 文章：470 积分：956

门派：黑客帝国 注册：2003-8-28

第 9 楼

1.3.5 单源最短路径

在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费） a [i ][ j

]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a

给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s 为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。 利用E.

Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a的方法按路径长度顺序产生最短路径。 首先最初产生从s

到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是D

i j k s t r a算法。

可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1 3 - 1 0中，b

中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。 通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p [ i ]给出从s 到达i的路径中顶点i

前面的那个顶点。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从s 到顶点i

的路径可反向创建。从i 出发按p[i],p[p[i]],p[p[p[i]]], .的顺序，直到到达顶点s 或0。在本例中，如果从i = 5开始，则顶点序列为p[i]=4, p[4]=3, p[3]=1=s，因此路径为1 , 3 , 4 , 5。

为能方便地按长度递增的顺序产生最短路径，定义d [ i

]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s 到s

的一条长度为0的路径，这时对于每个顶点i，d [ i ]等于a [ s ] [ i ]（a

是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。 综上所述，可以得到图1 3 - 11所示的伪代码， 1) 将与s 邻接的所有顶点的p

初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s 到i

的最短路径，即是由s到它自身那条路径再扩充一条边得到。当找到更短的路径时， p [ i

]值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新d 的值。

1) 初始化d[i ] =a[s] [i ]（1≤i≤n），

对于邻接于s的所有顶点i，置p[i ] =s, 对于其余的顶点置p[i ] = 0； 对于p[i]≠0的所有顶点建立L表。 2) 若L为空，终止，否则转至3 )。 3) 从L中删除d值最小的顶点。

4) 对于与i 邻接的所有还未到达的顶点j，更新d[ j ]值为m i n{d[ j ], d[i ] +a[i ][ j ]

}；若d[ j ]发生了变化且j 还未

在L中，则置p[ j ] = 1，并将j 加入L，转至2。 图1 - 11 最短路径算法的描述

1. 数据结构的选择

我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d 值最小的顶点。如果L用最小堆（见9 .

3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n

)。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d 值，所以在4) 中可能需要改变一些d

值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O (

n2 )，因此执行减操作的总时间为O ( n2 l o g n )。

若L用无序的链表来维护，则3) 与4) 花费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n

)的时间，每次减操作需( 1 )的时间（需要减去d[j] 的值，但链表不用改变）。利用无序链表将图1 - 11的伪代码细化为程序1

3 - 5，其中使用了C h a i n (见程序3 - 8 )和C h a i n I t e r a t o r类（见程序3 - 1 8）。

程序13-5 最短路径程序 template

void AdjacencyWDigraph::ShortestPaths(int s, T d[], int p[]) {// 寻找从顶点s出发的最短路径, 在d中返回最短距离 // 在p中返回前继顶点

if (s < 1 || s > n) throw OutOfBounds(); Chain L; // 路径可到达顶点的列表 ChainIterator I; // 初始化d, p, L

for (int i = 1; i <= n; i++){ d[i] = a[s][i];

if (d[i] == NoEdge) p[i] = 0; else {p[i] = s;

L . I n s e r t ( 0 , i ) ; } }

// 更新d, p

while (!L.IsEmpty()) {// 寻找具有最小d的顶点v int *v = I.Initialize(L); int *w = I.Next(); while (w) {

if (d[*w] < d[*v]) v = w; w = I.Next();}

// 从L中删除通向顶点v的下一最短路径并更新d int i = *v;

L . D e l e t e ( * v ) ;

for (int j = 1; j <= n; j++) {

if (a[i][j] != NoEdge && (!p[j] || d[j] > d[i] + a[i][j])) { // 减小d [ j ]

d[j] = d[i] + a[i][j];

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库中国数学建模-编程交流-贪婪算法 - 1(5)在线全文阅读。