一、实验目的
1.掌握能用动态规划方法求解的问题应满足的条件;
2.加深对动态规划方法的理解与应用;
3.锻炼学生对程序跟踪调试能力;
4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二.实验内容
对于任意数目的n个城市,分别用1~n编号,则这个问题归结为在有向带权图中,寻找一条路径最短的哈密尔顿回路问题。
三.实验要求
(1)用动态规划方法货郎担问题;
(2)上机实现所设计的算法;
四.实验过程设计(算法设计过程)
动态规划的思想实质是分治思想和解决冗余。 与分治法类似的是,将原问题分解成若干个子问题,先求解子问题,再从这些子问题的解得到原问题的解。与分治法不同的是,经分解的子问题往往不是互相独立的。若用分治法来解,有些共同部分(子问题或子子问题)被重复计算了很多次。如果能够保存已解决的子问题的答案,在需要时再查找,这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。
动态规划方法的基本思想是,把求解的问题分成许多阶段或多个子问题,然后按顺序求解各子问题。最后一个子问题就是初始问题的解。
由于动态规划的问题有重叠子问题的特点,为了减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
1、多段图
1)从最后一段算起,找出每段的每个点的最短距离;
2)每段逐一向前推,直到算至起点;
3)比较从起点到终点的距离得出最短距离。
2、货郎担
假设周游路线是开始于结点1并终止于结点1的了条简单路径。每一条周游路线都由一条边(1,k)和一条由结点k到结点1的路径所组成,其中k∈V-{1};而这条由结点k到结点1的路径通过V-{1,k}的每个结点各一次。容易看出,如果这条周游路线是最优的,那么这条由k到1的路径必定是通过V-{1,k}中所有结点的由k到1的最短路径,因此最优性原理成立。设g(i,S)是由结点i开始,通过S中的所有结点,在结点1终止的一条最短路径长度。g(1,V-{1})是一条最优的周游路线长度。于是可以得出
g(1,V-{1})=min{ +g(k,V-{1,k})}
将其一般化可得
g(i,S)—min{ +g(j,S-{j})}
五.源代码
1、多段图文章来源:https://www.toymoban.com/news/detail-739821.html
#include <iostream>
#include <vector>
#define MAX 9999
using namespace std;
void initGraph(vector<vector<int> > &g, vector<vector<int> > &s) {
cout << "输入边信息:(顶点a 顶点b 权值w)(输入0结束)" << endl;
int i, j;
while (cin >> i && i) {
cin >> j;
cin >> g[i][j];
}
cout << "输入起点:";
cin >> s[1][0];
int level;
cout << "输入中间阶段数:(不含起点和终点层)";
cin >> level;
int a = 2;
for (int i = 1; i <= level; i++) {
cout << "输入中间第" << i << "阶段的点:(输入0结束)";
int k, j = 0;
while (cin >> k && k) {
s[a][j++] = k;
}
a++;
}
cout << "输入终点:";
cin >> s[a][0];
}
void way(vector<vector<int> > &g, vector<vector<int> > &s, vector<vector<int> > &f, vector<int> &result) {
int n = g.size() - 1;
int level, i;
for (i = 1; i <= n; i++)
if (s[i][0] == 0)
break;
level = i - 1;
int t = n;
int start = s[1][0];
int end = s[level][0];
for (i = level - 1; i >= 1; i--){
int j = 0;
while (s[i][j]){
int m = 0;
f[i][j] = MAX;
if (g[s[i][j]][end] == MAX){
while (s[i + 1][m] != 0){
if (g[s[i][j]][s[i + 1][m]] != MAX){
if (f[i][j] > (f[i + 1][m] + g[s[i][j]][s[i + 1][m]])){
f[i][j] = f[i + 1][m] + g[s[i][j]][s[i + 1][m]];
result[s[i][j]] = s[i + 1][m];
t--;
}
}
m++;
}
}
else{
while (s[i + 1][m] != 0){
if (f[i][j] > (f[i + 1][m] + g[s[i][j]][s[i + 1][m]])){
f[i][j] = f[i + 1][m] + g[s[i][j]][s[i + 1][m]];
result[s[i][j]] = s[i + 1][m];
t--;
}
m++;
}
}
j++;
}
}
}
void print(vector<int> &result, vector<vector<int> > &s, vector<vector<int> > &f) {
int n = result.size() - 1;
cout << "最短路径为:";
int t = s[1][0];
cout << t;
while (result[t] != s[n][0]) {
cout << " ->" << result[t];
t = result[t];
}
cout << endl << "最短距离为:" << f[1][0] << endl;
}
int main() {
int vexNum;
cout << "输入点的个数:";
cin >> vexNum;
vector<vector<int> > graph(vexNum + 1, vector<int>(vexNum + 1, MAX));
vector<vector<int> > s(vexNum + 1, vector<int>(vexNum + 1, 0));
vector<vector<int> > f(vexNum + 1, vector<int>(vexNum + 1, 0));
vector<int > result(vexNum + 1, 0);
initGraph(graph, s);
way(graph, s, f, result);
print(result, s, f);
system("pause");
return 0;
}
运行结果示例:
2.货郎担问题文章来源地址https://www.toymoban.com/news/detail-739821.html
#include<iostream>
#include<iomanip>
using namespace std;
int n;
int cost[20][20];
bool done[20] = { 1 };
int start = 0;
int imin(int num, int cur)
{
if (num == 1)
return cost[cur][start];
int mincost = 10000;
for (int i = 0; i < n; i++)
{
cout << i << " i:" << done[i] << endl;
if (!done[i] && i != start)
{
done[i] = 1;
int value = cost[cur][i] + imin(num - 1, i);
if (mincost > value)
{
mincost = value;
cout << mincost << endl;
}
done[i] = 0;
}
}
return mincost;
}
int main()
{
cout << "请输入n的值"<<endl;
cin >> n;
int cc[100][100];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << "请输入各成本值" << endl;
cin >> cc[i][j];
cost[i][j] = cc[i][j];
}
}
cout << imin(n, start) << endl;
return 0;
}
到了这里,关于动态规划多段图和货郎担问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!