贪心算法课后作业C++实现贪心法实验内容

137 阅读 0 评论 91 点赞

我是靠谱客的博主务实戒指，这篇文章主要介绍贪心算法课后作业C++实现贪心法实验内容，现在分享给大家，希望可以做个参考。

贪心算法课后作业C++实现

贪心法实验内容
- TSP问题
- 银行排队问题
- 图着色问题

贪心法实验内容

记录课堂老师布置的课后作业（没有水内容的意思哈哈哈哈哈哈

TSP问题

利用贪心法求解 30 个城市的 TSP 问题。城市坐标如下：
{41,94},{37,84},{54,67},{25,62},{7,64},{2,99},{68,58},{71,44},{54,62},{83,69} ，{64,60},{18,54},{22,60},{83,46},{91,38},{25,38},{24,42},{58,69},{71,71},{74,78} ，{87,76},{18,40},{13,40},{82,7},{62,32},{58,35},{45,21},{41,26},{44,35},{4,50}
TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
第一个贪心想法使是从第一个点出发，每次选择距离最短的没有走过的邻接点作为下一个点，直到最后走完全部城市。

复制代码

#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
using namespace std;
struct Point {
int x;
int y;
};
double distan(Point a, Point b) {
return sqrt((double)(b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
double TSP(Point City[], int n) {
double d[32][32];
for (int i = 1; i <= n; i++) {
d[i][i] = INT_MAX;
for (int j = i + 1; j <= n; j++) {
d[i][j] = distan(City[i], City[j]);
d[j][i] = d[i][j];
}
}
double min, num = 0;
int count = 0, index = 0, i = 1, j = 1;
while (count < n) {
min = INT_MAX;
for (j = 1; j <= n; j++) {
if (d[i][j] < min) {
index = j;
min = d[i][j];
}
}
cout << i << " ";
count++;
if (count == n) {
num += d[1][index];
break;
}
for (int k = 1; k <= n; k++) {
d[k][i] = INT_MAX;
}
i = index;
if (min < INT_MAX) {
num += min;
}
}
cout << '1' << endl;
return num;
}
int main() {
int n = 30;
Point City[100] = { {0,0} ,{41,94},{37,84},{54,67},{25,62},
{7,64},{2,99},{68,58},{71,44},{54,62},{83,69} ,{64,60},{18,54},
{22,60},{83,46},{91,38},{25,38},{24,42},{58,69},{71,71},{74,78} ,
{87,76},{18,40},{13,40},{82,7},{62,32},{58,35},{45,21},{41,26},{44,35},{4,50} };
cout << "第一种贪心算法求得的路径为：" << endl;
double x = TSP(City, n);
cout << "最短路程为：" << fixed << setprecision(2) << x << endl;
}

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
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
using namespace std;
struct Point {
int x;
int y;
};
double distan(Point a, Point b) {
return sqrt((double)(b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
double TSP(Point City[], int n) {
double d[32][32];
for (int i = 1; i <= n; i++) {
d[i][i] = INT_MAX;
for (int j = i + 1; j <= n; j++) {
d[i][j] = distan(City[i], City[j]);
d[j][i] = d[i][j];
}
}
double min, num = 0;
int count = 0, index = 0, i = 1, j = 1;
while (count < n) {
min = INT_MAX;
for (j = 1; j <= n; j++) {
if (d[i][j] < min) {
index = j;
min = d[i][j];
}
}
cout << i << " ";
count++;
if (count == n) {
num += d[1][index];
break;
}
for (int k = 1; k <= n; k++) {
d[k][i] = INT_MAX;
}
i = index;
if (min < INT_MAX) {
num += min;
}
}
cout << '1' << endl;
return num;
}
int main() {
int n = 30;
Point City[100] = { {0,0} ,{41,94},{37,84},{54,67},{25,62},
{7,64},{2,99},{68,58},{71,44},{54,62},{83,69} ,{64,60},{18,54},
{22,60},{83,46},{91,38},{25,38},{24,42},{58,69},{71,71},{74,78} ,
{87,76},{18,40},{13,40},{82,7},{62,32},{58,35},{45,21},{41,26},{44,35},{4,50} };
cout << "第一种贪心算法求得的路径为：" << endl;
double x = TSP(City, n);
cout << "最短路程为：" << fixed << setprecision(2) << x << endl;
}

但是这种贪心策略并不一定能找到最优解，所以设计另一种贪心策略，每次在整个图的范围内选择最短边加入集合中，但是要保证集合中的边最终形成一个哈密顿回路。所以选择边的时候就要符和一些规则：
（1）不能选择那些使已选择的边的集合中产生回路的边；

（2）不能选择那些使已选择的边中产生分支的边；

（3）在剩下可选择边中选择最小的。
代码太难了不会写，把伪代码放一下~

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
最短连接策略求解TSP问题
输入：无向带权图G=(V,E)
输出：回路长度TSPLength
1.初始化：P={};TSPLength=0;
2.E'=E;
3.循环直到集合P中包含n-1条边
3.1 在E'中选取最短边(u,v);
3.2 E'=E-{(u,v)};
3.3 如果(等点u和v在P中不连通and不产生分枝)则
P=P+{(u,v)};TSPLength=TSPLength+C(u,v);
4.输出TSPLength.

算法分析：在上述算法中，共进行n-1次贪心选择，每次贪心选择中，如果顺序查找最短边，时间复杂度为O( $N^2$ )，如果采用堆排序间里堆后取最短边可以提高到O(log2n)，可以采用并查集的操作考察两个顶点是否联通以及是否会产生分枝，时间复杂度为O(log2n)，因此算法的时间复杂度为O(nlog2n)。

如果有大佬写了代码教教我怎么实现TAT。

银行排队问题

设有 10 个顾客在一个银行窗口排队，他们各自业务所需的服务时间分别为{8, 13, 6, 9, 7, 4, 22, 3, 12, 15}分钟。应如何安排这 10 个顾客的服务次序，才能使顾客总的等待时间最小？最小等待时间为多少？
这题相当于C++贪心算法学习&练习中的排队接水。
用时少的先办理业务，这样平均排队时间才会最少。通过局部最优解可以导出整体最优解，所以可以采用贪心算法的到最优解。
为了练习# $i n c l u d e < i o m a n i p >$ 所以还是暑促保留两位小数的结果。

复制代码

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>
#include <algorithm>
#include <iomanip>
using namespace std;
bool cmp(pair<int, int>a, pair<int, int>b) {
if (a.second < b.second) return true;
if (a.second == b.second && a.first < b.first) return true;
else return false;
}
int main() {
int n;
cout << "请输入人数：" << endl;
cin >> n;
pair<int, int> T[1000];
pair<int, int>x;
cout<<"请输入每个人需要的服务时间："<<endl;
for (int i = 1; i <= n; i++) {
x.first = i;
cin
>> x.second;
T[i] = x;
}
sort(T + 1, T + n + 1,cmp);
long num=0;
cout << "顾客服务次序为：" << endl;
for (int i = 1; i <= n; i++) {
cout << T[i].first<<' ';
num += T[i].second* (n - i);
}
cout << endl;
cout << "最小等待时间为：" << endl;
cout << fixed << setprecision(2) << num / 10.0;
}

图着色问题

有一个 500 个节点的图。请设计贪心法，求解其最小着色数和着色方案。
图着色问题是指求图G的最小色数k，使得k种颜色对G中的顶点着色，可使任意两个相邻顶点着不同颜色。老师给的测试数据集这里的贪心思想体现在每种颜色都要找到尽量多的可行的点进行上色，对于每种颜色，需要遍历所有的点，排除已经上色和邻接点以及上了该种颜色的点后的点都上此时的颜色。但是贪心法也不一定找到最优解，比如在二部图中，贪心法找到k=n，实际上k=2。

复制代码

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
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int G[500][500];
//判断该点邻接点是不是有同样的颜色
int beside(int G[500][500],int i,pair<int,int> Point[],int n,int k){
for (int j = 0; j < n; j++) {
if (G[i][j] != 0 && Point[j].second ==k) {
return 0;
}
}
return 1;
}
//颜色标记函数
int Color_Graph(int G[500][500],int n) {
pair<int,int> Point[500];
for (int i = 0; i < n; i++) {
Point[i].first = i;
Point[i].second = 0;
}
int k = 0,count=0;
while (count<n) {
k++;
for (int i = 0; i < n; i++) {
//如果该点没有涂色且邻接点不会阻止
if (Point[i].second == 0 && beside(G,i,Point,n,k) == 1) {
Point[i].second = k;
count++;
}
}
}
cout << endl;
for (int i = 0; i < n; i++) {
cout<< Point[i].second << " ";
}
cout << endl;
return k;
}
int main() {
int n;
cout << "点的总个数：" << endl;
cin >> n;
cout << "输入邻接矩阵" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> G[i][j];
}
}
cout << "每个点的颜色标记为：";
int x=Color_Graph(G,n);
cout << "最少需要的颜色数为：" << x;
}