绿色健康小清新

耐得住寂寞,守得住繁华

贪心思想与案例

说明


本文我先写在我的CSDN上后再转到该博客系统的,可能有些链接会跳转我的CSDN上。并且在CSDN上将内容分开了!


何为贪心

 假设有四种硬币:二角五分、一角、五分和一分。现要找给顾客六角三分。
 显然,会拿出2个二角五分、1个一角和3个一分的硬币交给顾客。
 贪心方法思路:首先选出一个面值不超过六角三分的最大硬币,即二角五分,然后在剩余数中再选最大面值的硬币,依此类推,得到其解
 若硬币面值改为:一角一分、五分和一分,而要找给顾客一角五分钱。
 用贪心算法将找给1个一角一分和4个一分的硬币。然而,3个五分硬币是最好的找法。
 此时,贪心算法没有得到整体最优解。但通常可得到最优解的很好近似。


 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择
 当然,希望贪心算法得到的最终结果也是整体最优的。
 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解
 在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。


贪心算法的基本要素

  • 考察用贪心算法求解的问题的一般特征
  • 对于一个具体问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢? 这个问题很难给予肯定的回答。
  • 从许多用贪心算法求解的问题中看到,这类问题一般具有2个重要性质:贪心选择性质最优子结构性质

贪心选择性质

  • 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。也是贪心算法与动态规划算法的主要区别
  • 贪心算法通过一系列的选择来得到问题的解,它所做的每步选择都是当前状态下局部最好选择,即局部最优选择(贪心选择)。贪心算法所做的贪心选择可以依赖于以往所做过的选择,但不依赖于子问题的解。每作一次贪心选择就将所求问题简化为规模更小的子问题
  • 在动态规划算法中,每步所做的选择往往依赖于相关子问题的解,因而只有在解出相关子问题后,才做出选择。
  • 正是由于上述差别,动态规划方法以自底向上的方式解决各个子问题,而贪心方法以自顶向下的方式进行

证明贪心选择性质的方法:
  对具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解

  1. 首先考察一个问题的整体最优解(x1,x2,…,xn),并证明可修改这个最优解,使其以贪心选择开始。
  2. 然后,用数学归纳法证明,通过进一步做贪心选择,最终可得到问题的整体最优解(y1,y2,…,yn)
    (y1,y2,…,yn)是用贪心选择做出的最优解。

最优子结构性质

  • 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质
  • 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心选择与最优子结构

  • 满足贪心选择性质必满足最优子结构性质。
  • 满足最优子结构性质却未必满足贪心选择性质。
  • 虽然能够应用贪心算法一定能够应用动态规划法,但是一般来说,贪心算法的效率高于动态规划法,因而还是应用贪心算法

贪心算法与动态规划算法的差异

  • 共同点:贪心算法和动态规划算法都要求问题具有最优子结构性质
  • 具有最优子结构的问题应该选用贪心算法,还是动态规划算法求解? 是否能用动态规划算法求解的问题也能用贪心算法求解?
  • 下面研究2个经典的组合优化问题(0-1背包问题和装载问题),并以此说明贪心算法与动态规划算法的主要差别。

 👉结合0-1背包问题和装载问题进行分析


贪心算法的一般框架

1
2
3
4
5
6
7
8
GreedyAlgorithm(parameters)
{
初始化;
重复执行以下的操作:
选择当前可以选择的最优解;
将所选择的当前解加入到问题的解中去;
直至满足问题求解的结束条件。
}








活动安排问题

问题描述

 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。
该问题要求高效地安排一系列争用某一公共资源的活动
 贪心算法使得尽可能多的活动能兼容地使用公共资源。

 设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源
 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi, 且si <fi 。
 如果选择了活动i,则它在[si, fi)内占用资源。
 若[si, fi)与[sj, fj)不相交,则称活动i与j是相容的。即当si≥fj或sj≥fi时,活动i与活动j相容。

活动安排问题就是求E={1,2,…,n}的最大相容活动子集。


问题分析

  • 用数组A分别存放所有活动的起始时间、结束时间以及是否予以安排的标记
  • 某项活动结束时间愈早,安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排
  • 为此,将数组中的活动按结束时间的非减顺序排序,即f1≤f2≤…≤fn。
  • 显然排序需要的时间为O(nlogn)。

核心算法

1
2
3
4
5
6
7
8
9
10
template<class Type>
void GreedySelector(int n, Type s[ ], Type f[ ], bool A[ ])
{
A[1]=true;
int j=1;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) { A[i]=true; j=i; }
else A[i]=false;
}
}

  • 由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。
  • 算法贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
  • 当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。
  • 如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。

例子

 设待安排的11个活动的开始时间和结束时间,按结束时间的非减序排列如下:

  • 若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi,则不选择活动i,否则选择活动i加入集合A中。
  • 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。









0-1背包问题(不适合用贪心)

提示

0-1背包问题不适合用贪心法来求解。以下仅仅是来模拟和解释为什么不能用贪心


问题描述

  • 给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。
  • 应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
  • 在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。

基本步骤

  1. 计算每种物品单位重量的价值vi/wi
  2. 依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
  3. 若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
  4. 依此策略一直地进行下去,直到背包装满为止。

核心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//n中物品已经排好序
void Knapsack(int n,float M,float v[],float w[],float x[])
{
Sort(n,v,w);
int i;
for (i=1;i<=n;i++) x[i]=0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i]>c) break;
x[i]=1;
c-=w[i];
}
if (i<=n) x[i]=c/w[i];
}

 算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此,算法的计算时间上界为O(nlogn)。为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。


0-1背包问题不适用贪心算法

  • 背包容量为50kg,物品1, 2和3的容量和价值分别为(10kg, $60), (20kg, $100)和(30kg, $120)。

  • 单位重量价值最高的为物品1,6$/kg。但是依照贪心算法首选物品1却不能获得最优解:

  • 对于0-1背包问题,贪心选择之所以不能得到最优解, 是因为在这种情况下,无法保证最终能将背包装满部分闲置的背包空间使每公斤背包空间的价值降低了

  • 在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。

  • 由此导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。









最优装载

问题描述

  • 有一批集装箱,要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。
  • 最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船

装载问题的形式化描述


算法描述

 最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。


核心算法

1
2
3
4
5
6
7
8
9
Template <class Type>
void Loading(int x[ ], Type w[ ], Type c, int n)
{
int *t = new int [n+1];
Sort(w, t, n); //N个集装箱按照重量由小到大排好序放入数组t中
for (int i = 1; i <= n; i++) x[i] = 0;
for (int i = 1; i <= n && w[t[i]] <= c; i++)
{x[t[i]] = 1; c -= w[t[i]];}
}

完整算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
typedef struct Goods
{
int weight;
int id;
};
int x[MAX];
Goods g[MAX];
int c, n, loaded_n;
void Input()
{
cout<<"请输入载重和箱子个数:";
cin>>c>>n;

cout<<"请输入箱子的重量:";
for(int i = 1; i <= n; ++i)
{
cin>>g[i].weight;
g[i].id = i;
}
}
bool compare(const Goods &a, const Goods &b)
{
return a.weight < b.weight;
}
void Loading()
{
loaded_n = 0;
memset(x, 0, sizeof(x));
sort(g + 1, g + n+1, compare);

for(int i = 1; i <= n && c >= g[i].weight; ++i)
{
x[g[i].id] = 1;
c -= g[i].weight;
++loaded_n;
}

}
void Output()
{
cout << "装入了 " << loaded_n << " 件物品" << endl;
cout << "分别是" << endl;
for(int i = 1; i <= n; ++i)
if(x[i] == 1)
cout << i << " ";
}
int main()
{
Input();
Loading();
Output();
}


测试样例

输入
请输入载重和箱子个数:15 6
请输入箱子的重量:5 1 4 8 6 3

输出
装入了 4 件物品
分别是
1 2 3 6









哈夫曼编码

哈夫曼树的定义

 n个叶结点,权分别为w1,w2,···,wn的二叉树中,带权路径长度WPL最小的二叉树叫哈夫曼树(Huffman Tree ), 即:最优二叉树


哈夫曼原理

1)将字符集中每个字符c出现的频率f(c)作为权值
2)根据给定的权值{w1,w2,···,wn}构造n个二叉树F={T1,T2,···,Tn}, 每个Ti只有一个根结点,权为wi。
3)在F中选取两棵根结点权值最小的树构成一棵新的二叉树,其根的权值为左右子树根的权值的和
4)F中删去这两棵树,加上新得的树。
5)重复2)3)直到只剩一棵树。

在实际操作中步骤2其实只选取权值最小的两个构成一个新节点


例子

 一个文件由4个字母{b, c, j, m, p} 构成,其出现的频率分别为 {5, 6, 2, 9, 7} ,构造哈夫曼树。


完整代码

1:在算法huffmanTree中,编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时,有效地确定算法当前要合并的2棵具有最小频率的树。
2:一旦2棵具有最小频率的树合并后,产生一棵新树,频率为其合并频率之和,并将新树插入优先队列Q。

3:经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
//哈夫曼树结点结构
typedef struct {
int weight;//结点权重
int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode, *HuffmanTree;
//动态二维数组,存储哈夫曼编码
typedef char ** HuffmanCode;

//HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2)
{
int min1, min2;
//遍历数组初始下标为 1
int i = 1;
//找到还没构建树的结点
while(HT[i].parent != 0 && i <= end){
i++;
}
min1 = HT[i].weight;
*s1 = i;

i++;
while(HT[i].parent != 0 && i <= end){
i++;
}
//对找到的两个结点比较大小,min2为大的,min1为小的
if(HT[i].weight < min1){
min2 = min1;
*s2 = *s1;
min1 = HT[i].weight;
*s1 = i;
}else{
min2 = HT[i].weight;
*s2 = i;
}
//两个结点和后续的所有未构建成树的结点做比较
for(int j=i+1; j <= end; j++)
{
//如果有父结点,直接跳过,进行下一个
if(HT[j].parent != 0){
continue;
}
//如果比最小的还小,将min2=min1,min1赋值新的结点的下标
if(HT[j].weight < min1){
min2 = min1;
min1 = HT[j].weight;
*s2 = *s1;
*s1 = j;
}
//如果介于两者之间,min2赋值为新的结点的位置下标
else if(HT[j].weight >= min1 && HT[j].weight < min2){
min2 = HT[j].weight;
*s2 = j;
}
}
}

//HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
{
if(n<=1) return; // 如果只有一个编码就相当于0
int m = 2*n-1; // 哈夫曼树总节点数,n就是叶子结点
*HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用
HuffmanTree p = *HT;
// 初始化哈夫曼树中的所有结点
for(int i = 1; i <= n; i++)
{
(p+i)->weight = *(w+i-1);
(p+i)->parent = 0;
(p+i)->left = 0;
(p+i)->right = 0;
}
//从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
for(int i = n+1; i <= m; i++)
{
(p+i)->weight = 0;
(p+i)->parent = 0;
(p+i)->left = 0;
(p+i)->right = 0;
}
//构建哈夫曼树
for(int i = n+1; i <= m; i++)
{
int s1, s2;
Select(*HT, i-1, &s1, &s2);
(*HT)[s1].parent = (*HT)[s2].parent = i;
(*HT)[i].left = s1;
(*HT)[i].right = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
}
//HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC,int n){
*HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
cd[n-1] = '\0';//字符串结束符

for(int i=1; i<=n; i++){
//从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
int start = n-1;
//当前结点在数组中的位置
int c = i;
//当前结点的父结点在数组中的位置
int j = HT[i].parent;
// 一直寻找到根结点
while(j != 0){
// 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
if(HT[j].left == c)
cd[--start] = '0';
else
cd[--start] = '1';
//以父结点为孩子结点,继续朝树根的方向遍历
c = j;
j = HT[j].parent;
}
//跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
(*HC)[i] = (char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i], &cd[start]);
}
//使用malloc申请的cd动态数组需要手动释放
free(cd);
}
//打印哈夫曼编码的函数
void PrintHuffmanCode(HuffmanCode htable,int *w,int n)
{
printf("Huffman code : \n");
for(int i = 1; i <= n; i++)
printf("%d code = %s\n",w[i-1], htable[i]);
}
int main(void)
{
int w[5] = {2, 8, 7, 6, 5};
int n = 5;
HuffmanTree htree;
HuffmanCode htable;
CreateHuffmanTree(&htree, w, n);
HuffmanCoding(htree, &htable, n);
PrintHuffmanCode(htable,w, n);
return 0;
}

测试样例









单源最短路径

问题描述

 给定一个图G = (V, E),其中每条边的权是一个非负实数。另外给定顶点集合V中的一个顶点v,称为
 问题:求从源v到所有其它各个顶点的最短路径

问题分析

 单源最短路径问题的贪心选择策略选择从源v出发目前用最短的路径所到达的顶点,这就是目前的局部最优解。


基本思想

 设置一个集合S,初始时S中仅含有源v,然后不断地用贪心选择来扩充集合S ,即:从源v出发,选择用最短的路径所到达的顶点u,加入到集合S中,直至S包含所有V中顶点。

 把从源v到顶点u中间只经过S中顶点的路称为从源v到顶点u的特殊路径,用dist[u]来记录当前顶点u所对应的最短特殊路径长度

 贪心选择:每次找到最小的dist[u],将u添加到S中,同时对数组dist[]作必要的修改。


核心算法


例子

dist[w] := min(dist[w] , dist[u]+C[u ,w])

迭代Sudist[2]dist[3]dist[4]dist[5]
初始{1}- -1030100
1{1,2}2106030100
2{1,2,4}410503090
3{1,2,4,3}310503060
4{1,2,4,3,5}510503060

  prev[2]=1 prev[4]=1 prev[3]=4 prev[5]=3

 由数组dis[i]可知:从顶点1到顶点2、3、4、5的最短通路的长度分别为10、50、30和60。

 根据prev数组,源节点1到5的最短路径为:1,4,3,5


复杂度分析

  • Dijkstra 算法有两层循环,外层循环为n次,内层有两个循环:一个是选出最小的u(第5行),另一个是修订disw。它们的次数都是n/2,所以内层循环的时间为O(n)
  • Dijkstra算法的时间复杂度为 O(n2)
  • Dijkstra 算法能求出从源到其它各顶点的最短通路的长度,但是却并没有给出其最短通路。可借助prev数组得到。

完整代码

下面的代码是基于有向图的代码。若求无向图,在inPut()方法中打开Graph[pos2][pos1] = dis。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int max_ = 0x3f3f3f;
int Graph[110][110];
int dist[110]; //dist[i]存储源到顶点 i 的当前最短路长度
int visited[110]; //标记i号顶点是否已并入S
int pre[110]; //记录的是从源到顶点i的最短路径上i的前一个顶点。用来求出相应的最短路径
int m, n, p; //m代表路径的个数, n代表顶点的个数,p代表源
//回溯输出路径
void traceback(int i)
{
if(pre[i] == i)
{
printf("%d", i);
}
else
{
traceback(pre[i]);
printf(" %d", i);
}
}
void outPut()
{
for(int i = 1; i <= n; ++i)
{
if(i != p)
{
printf("点 %d 到点 %d 的最小距离为 %d\n", p, i, dist[i]);
cout << "路径为 :" << endl;
traceback(i);
cout << endl;
}
}
}
void Dijkstra()
{
//初始化
for(int i = 1; i <= n; ++i)
{
dist[i] = Graph[p][i];
visited[i] = 0;
pre[i] = p;
}
dist[p] = 0;
visited[p] = 1;
for(int i = 1; i < n; ++i)
{
int pos, min_len = max_;
for(int i = 1; i <= n; ++i)
{
if(!visited[i] && min_len > dist[i])
{
pos = i, min_len = dist[i];
}
}
visited[pos] = 1;
for(int j = 1; j <= n; ++j)
{
if(!visited[j] && dist[j] > min_len + Graph[pos][j])
{
dist[j] = min_len + Graph[pos][j];
pre[j] = pos;
}
else
continue;
}
}
}
void inPut()
{
int pos1, pos2, dis;
memset(Graph, max_, sizeof(Graph));
scanf("%d %d %d", &p, &n, &m);
// cout << "p = " << p << " n = " << n << " m = " << m << endl;
for(int i = 1; i <= m; ++i)
{
scanf("%d %d %d", &pos1, &pos2, &dis);
Graph[pos1][pos2] = dis;
//Graph[pos2][pos1] = dis;//若图是无向图,则打开此代码
}
}
int main()
{
inPut();
Dijkstra();
outPut();
}

测试用例

测试无向图

输入
1 5 7
1 2 10
1 4 30
1 5 100
2 3 50
4 5 60
3 5 10
3 4 20

输出
点 1 到点 2 的最小距离为 10
路径为 :
1 2
点 1 到点 3 的最小距离为 50
路径为 :
1 4 3
点 1 到点 4 的最小距离为 30
路径为 :
1 4
点 1 到点 5 的最小距离为 60
路径为 :
1 4 3 5

测试有向图

输入
1 5 7
1 2 10
1 5 100
1 4 30
2 3 50
3 5 10
4 3 20
4 5 60

输出
点 1 到点 2 的最小距离为 10
路径为 :
1 2
点 1 到点 3 的最小距离为 50
路径为 :
1 4 3
点 1 到点 4 的最小距离为 30
路径为 :
1 4
点 1 到点 5 的最小距离为 60
路径为 :
1 4 3 5

在这里插入图片描述










最小生成树(Prim)

问题描述

 设G = (V, E)是一个无向连通带权图,即一个网络。E的每条边(v, w)的权为c[v][w]。

 如果G的一个子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。

 生成树的各边权的总和称为该生成树的耗费

 在G的所有生成树中,耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。


算法思想

  • 在保证连通的前提下依次选出权重较小的n – 1条边。
  • G=(V, E)为无向连通带权图,令V={1, 2, …, n}。
  • 设置一个集合S ,初始化S = {1},生成树T = Φ。
  • 贪心策略:如果V–S中的顶点j与S中的某个点i连接, 且(i, j)是E中的权重最小的边,则选择j(将j加入S),并将(i, j) 加入生成树T中。
  • 重复执行贪心策略,直至V–S为空。

Prim算法中的数据结构

  • 图用连接矩阵C[i][j]给出,即C[i][j]为结点i到结点j的权重。
  • 为了有效地找出V–S中满足与S中的某个点i连接且(i, j) 权重最小的顶点j,对其中的每个顶点j设立两个数组closest[j]和lowcost[j]:
  • 对于每一个j ∈ V–S , 定义closest[j] 数组,closest[j]是j 在S中的邻居邻接顶点,它与j在S中的其它邻居节点k比较,有c[j][closest[j]]c[j][k];定义lowcost[j]数组, lowcost[j]的值就是c[j][closest[j]]。
  • Prim算法执行过程中每一个j ∈ V–S,先找出使得lowcost[j]最小的顶点j,根据数组closest[j]选取边(j, closest[j] ),最后,将j添加到S中。

核心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Prim(int n, Type **c) {
int j = 1; s[j] = true;
for (int i = 2; i <= n; i++) {
closest[i] = 1; lowcost[i]=c[1][i]; s[i]=false;}
for (int i = 1; i < n; i++) {min= inf;
for (int k = 2; k <= n; k++) {
if (lowcost[k]<min&&!s[k])
{min = lowcost[k]; j = k}
s[j] = true;
for (int k = 2; k <= n; k++) {
if (c[j][k]< lowcost[k]&&!s[k])
{lowcost[k] = c[j][k]; closest[k] = j}
}
}

例子

 给定一个连通带权图如下:
          

 假如从顶点A出发,顶点 B、C、D 到顶点 A 的权值分别为 2、4、2,所以,对于顶点 A 来说,顶点 B 和顶点 D 到 A 的权值最小,假设先找到的顶点 B:
              
 继续分析顶点 C 和 D,顶点 C 到 B 的权值为 3,到 A 的权值为 4;顶点 D 到 A 的权值为 2,到 B 的权值为无穷大(如果之间没有直接通路,设定权值为无穷大)。所以顶点 D 到 A 的权值最小:

              

 最后,只剩下顶点 C,到 A 的权值为 4,到 B 的权值和到 D 的权值一样大,为 3。所以该连通图有两个最小生成树:
          


完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int max_ = 0x3f3f3f;
int Graph[110][110];
int visited[110];
int closest[110];
int prepos[110]; //记录到当前节点最小距离的节点代号
int pointnum, edgenum;
int FindMinLen()
{
int pos, min_ = max_;
for(int i = 1; i <= pointnum; ++i)
if(min_ > closest[i] && closest[i])
{
min_ = closest[i];
pos = i;
}
return pos;
}
void Prim()
{
//初始化
for(int i = 2; i <= pointnum; ++i)
{
closest[i] = Graph[1][i];
prepos[i] = 1;
}
closest[1] = 0;
for(int i = 1; i < pointnum; ++i)
{
int pos;
pos = FindMinLen();
closest[pos] = 0; //赋0
//更新表
for(int j = 2; j <= pointnum; ++j)
{
if(closest[j] > Graph[pos][j])
{
closest[j] = Graph[pos][j];
prepos[j] = pos;
}
}
printf("%d -> %d\n", prepos[pos], pos);
}
}
void InPut()
{
int pos1, pos2, len;
scanf("%d %d", &pointnum, &edgenum);
memset(Graph, max_, sizeof(Graph));
for(int i = 1; i <= edgenum; ++i)
{
scanf("%d %d %d", &pos1, &pos2, &len);
Graph[pos1][pos2] = len;
Graph[pos2][pos1] = len;
}
}
int main()
{
InPut();
Prim();
}

测试用例

输入
4 5
1 2 2
1 3 2
1 4 4
2 4 3
3 4 3

输出
1 -> 2
1 -> 3
2 -> 4









最小生成树(Kruskal)

问题描述

 设G = (V, E)是一个无向连通带权图,即一个网络。E的每条边(v, w)的权为c[v][w]。

 如果G的一个子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。

 生成树的各边权的总和称为该生成树的耗费

 在G的所有生成树中,耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。


算法思想

  • 在保证无回路的前提下依次选出权重较小的n – 1条边
  • 贪心策略:如果(i, j)是E中尚未被选中的边中权重最小的,并且(i, j)不会与已经选择的边构成回路,于是就选择 (i, j)。

如何知道(i, j)不会造成回路?

  • 为此初始时将图的n个顶点看成n个孤立连通分支,将所有的边按权由小到大排序, 并依边权递增顺序检查每一条边:
  • 若边(i, j) 的两个端点i和j属于同一个连通分支,则选择(i, j) 会造成回路,反之则不会造成回路。
               

Kruskal算法的数据结构

  • 数组e[][]表示图的边,e[i][u]、e[i][v]和e[i][w]分别表示边i的两个端点及其权重。
  • 函数Sort(e, w)将数组e按权重w从小到大排序。
  • 一个连通分支中的顶点表示为一个集合。
  • 函数Initialize(n)将每个顶点初始化为一个集合。
  • 函数Find(u)给出顶点u所在的集合。
  • 函数Union(a, b)给出集合a和集合b的并集。
  • 重载算符!=判断集合的不相等。


核心代码

1
2
3
4
5
6
7
8
9
10
11
12
Kruskal(int n, **e)  {
Sort(e, w); //将边按权重从小到大排序
initialize(n); //初始时每个顶点为一个集合
k = 1; //k累计已选边的数目,
j = 1; //j为所选的边在e中的序号
while (k < n) //选择n – 1条边
{a = Find(e[j][u]); b = Find(e[j][v]);
//找出第j条边两个端点所在的集合
if (a != b) {t[k++] = j; Union(a, b)}
//若不同,第j条边放入树中并合并这两个集合
j++ } //继续考察下一条边
}

例子

给定一个连通带权图如下:
          

 首先,在初始状态下,对各顶点赋予不同的标记(用颜色区别),如下图所示:
              

 对所有边按照权值的大小进行排序,按照从小到大的顺序进行判断,首先是(1,3),由于顶点 1 和顶点 3 标记不同,所以可以构成生成树的一部分,遍历所有顶点,将与顶点 3 标记相同的全部更改为顶点 1 的标记,如(2)所示:
              
 其次是(4,6)边,两顶点标记不同,所以可以构成生成树的一部分,更新所有顶点的标记为:
              
 其次是(2,5)边,两顶点标记不同,可以构成生成树的一部分,更新所有顶点的标记为:
              
 然后最小的是(3,6)边,两者标记不同,可以连接,遍历所有顶点,将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记:
              
 继续选择权值最小的边,此时会发现,权值为 5 的边有 3 个,其中(1,4)和(3,4)各自两顶点的标记一样,如果连接会产生回路,所以舍去,而(2,3)标记不一样,可以选择,将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记:
              

当选取的边的数量相比与顶点的数量小 1 时,说明最小生成树已经生成。

完整算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>

#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef struct Edge //定义边集数组元素,v1,v2存顶点,weight存权重。
{
int v1;
int v2;
int weight;
}Edge;

typedef struct ALGraph //定义图的结构,peak存顶点的数量,edge存边的数量
{ //指针p作为边集数组,指针m为作为顶点数组
int peak;
int edge;
Edge *p;
int *m;
}ALGraph;


//创建图
void CreatALGraph(ALGraph *G)
{
int i,j;
printf("输入图的顶点数量和边的数量:");
scanf("%d %d",&G->peak,&G->edge);
G->p=(Edge *)malloc(sizeof(Edge)*(G->edge+1));
G->m=(int *)malloc(sizeof(int)*G->peak);
for(i=0;i<G->peak;i++)
{
printf("请输入输入顶点:");
scanf("%d",&G->m[i]);
}
for(i=0;i<G->edge;i++)
{
printf("请输入(vi-vj)和权重:");
scanf("%d %d %d",&G->p[i].v1,&G->p[i].v2,&G->p[i].weight);
}
for(i=0 ;i<G->edge;i++) //冒泡排序法,权重从小到大存在边集数组中
{
for(j=G->edge-1;j>i;j--)
{
if(G->p[i].weight>G->p[j].weight)
{
G->p[G->edge]=G->p[i];
G->p[i]=G->p[j];
G->p[j]=G->p[G->edge];
}
}
}
}


//通过parent[]找到可连接的边
int Find(int *parent,int g)
{
while(parent[g]!=0)
{
g=parent[g];
}
return g;
}

//判断生成树是否完成,完成的标志是生成树的边等于顶点的数量减1
int Finish(ALGraph *G,int *parent)
{
int i,n=0;

for(i=0;i<G->peak;i++)
{
if(parent[i])
{
n++;
}
}
if(n==G->peak-1)
{
return 1;
}
return 0;
}

//找到顶点的下标

int FindPeak(ALGraph *G,int g){
int i;
for(i=0;i<G->peak;i++)
{
if(G->m[i]==g)
return i;
}
return -1;
}
void MinTree_Kruskal(ALGraph *G)
{
int i,a,b;

int parent[G->peak];

for(i=0;i<G->peak;i++) //初始化parent[]
{
parent[i]=0;
}
for(i=0;i<G->edge;i++)
{
a=Find(parent,FindPeak(G,G->p[i].v1));
b=Find(parent,FindPeak(G,G->p[i].v2));

if(a!=b) //如果a==b则表是a和b在同一颗生成树上,如果a和b连接则为生成环,不符合生成树
{
parent[a]=b;
printf("%d->%d %d\n",G->p[i].v1,G->p[i].v2,G->p[i].weight);
}
if(Finish(G,parent)) //完成后返回
{
return;
}
}
}

int main()
{
ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
MinTree_Kruskal(G);
return 0;
}

测试样例

测试样例是上面例子中的数据,但是注意这里是从0开始的

输入
输入图的顶点数量和边的数量:6 10
请输入输入顶点:0
请输入输入顶点:1
请输入输入顶点:2
请输入输入顶点:3
请输入输入顶点:4
请输入输入顶点:5
请输入(vi-vj)和权重:0 1 6
请输入(vi-vj)和权重:0 2 1
请输入(vi-vj)和权重:0 3 5
请输入(vi-vj)和权重:1 2 5
请输入(vi-vj)和权重:1 4 3
请输入(vi-vj)和权重:2 3 5
请输入(vi-vj)和权重:2 4 6
请输入(vi-vj)和权重:2 5 4
请输入(vi-vj)和权重:3 5 2
请输入(vi-vj)和权重:4 5 6

输出
0->2 1
3->5 2
1->4 3
2->5 4
1->2 5










汽车加油问题

问题描述

 一辆汽车加满油后可行驶nkm 。旅途中有k个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并计算最少加油次数。


问题分析

 根据贪心算法的贪心选择性质, 为了要使加油次数最少,就会选择离加满油的点远一点的加油站加油

 另外,当加满油之后,都要是此后的过程中使加油次数最少。每一次汽车中剩下的油不能再行驶到下一站时,就在该站加油。每一次加满油之后与起点具有相同的条件,可以看做一个新的起点,过程也是相同的。因此,该问题具有最优子结构性质


核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nt greedy(vector<int> x, int n)
{
  int j, i, s, sum=0, k=x.size(); //sum是行驶距离之和,k是加油站之和
  for(j=0; j<k; ++j)
    if(x[j] > n) {
      cout<<"No Solution"<<endl; //如果无法到达目的地,则输出”No Solution”
      return -1;
    }
  for(i=0, s=0; i <k; ++i) {
    s += x[i];
    if(s > n) sum++, s = x[i]; //当无法到达下一个加油站时,要再此处加油。并且将s赋值为下一个加油站的距离
  }
  return sum;
}

n:表示汽车加满油之后可以行驶nkm;k:旅途中有k个加油站


例子

 加油站数:7
 最大行驶距离:7
 每个站之间的距离:1 2 3 4 5 1 6 6

红色部分表明要在从前一个加油站不能行驶到当前加油站,需在前一个加油站加油。

一共需要加油4次


完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//汽车加油
#include<iostream>
using namespace std;
int main()
{
int n,k;
int a[100];
cin>>n>>k;
int num=0,s=n;
for(int i=0;i<=k;i++)
{
cin>>a[i];
}
for(int i=0;i<=k;i++)
{
if(a[i]>n)
{
cout<<"No Solution";
return 0;
}
if(s-a[i]>=0)
{
s-=a[i];
}
else
{
num++;
s=n-a[i];
}
}
cout<<num;
return 0;
}


测试样例

输入
7
7
1 2 3 4 5 1 6 6

输出
4

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道