动态规划多段图和货郎担问题

这篇具有很好参考价值的文章主要介绍了动态规划多段图和货郎担问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、实验目的

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、多段图

#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;
}

运行结果示例:
货郎担问题动态规划,算法分析设计,动态规划,算法,c++
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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划课堂5-----子序列问题(动态规划 + 哈希表)

    目录 引言: 例题1:最长递增子序列 例题2:最长定差子序列 例题3:最长的斐波那契子序列的长度 例题4:最长等差数列 例题5:等差数列划分II-子序列 结语: 要想解决子序列问题那么就要理解子序列和子数组的区别,二者的定义如下。 子序列: 是由数组派生而来的序列,

    2024年03月13日
    浏览(75)
  • 动态规划问题实验:数塔问题

    动态规划是一种解决复杂问题的方法,它将一个问题分解为若干个子问题,然后从最简单的子问题开始求解,逐步推导出更复杂的子问题的解,最终得到原问题的最优解。动态规划的关键是找到子问题之间的递推关系,以及确定合适的边界条件和初始值。 数塔问题是一个经典

    2024年02月10日
    浏览(41)
  • 动态规划详细讲解c++|经典例题讲解认识动态规划|0-1背包问题详解

    uu们,你们好!这次的分享是动态规划,其中介绍了动态规划的相关概念和做题模板(三要素),同时为了uu们对动态规划方法有更加形象的认识,特地找了两个经典问题,和大家一起分析。并且呢,为了大家检验自己的学习成果,我专门在常用的oj上为uu们找到了相关题目的

    2024年04月11日
    浏览(60)
  • 租用游艇问题 石子合并问题 动态规划实验

    实验名称:                动态规划                          一、实验预习 1、实验目的 1. 理解并掌握动态规划方法的设计思想; 2. 提高应用动态规划方法解决问题和设计算法的能力; 3. 通过编程实现租用游艇问题和石子合并问题,进一步理解动态规划方

    2024年02月07日
    浏览(48)
  • 动态规划 背包问题

    进入正题: 假设有3件物品,每件物品价值分别为value[3] = { 2, 5, 6 } ,重量为 weight[3] = { 1, 3, 4 };背包的最大重量为4,我们列出如下表格: 1 2 3 4 1 2 3 对于这个表格,横向表示背包容量,纵向表示能装入该物体和该物体以前物体的最大价值。 对于每一个格子: 选择装入该物体,则

    2024年02月04日
    浏览(29)
  • 【动态规划】回文串问题

    题目链接 状态表示 f[i][j]表示 i 到 j 的子串当中是否是回文 状态转移方程 初始化 最初所有的内容都是0即可 填表 因为 i j 需要用 i + 1 来初始化,所以这个时候需要从下往上填表 返回值 返回整个dp 表里true 的数目就可以 AC代码: 题目链接 如果需要求一个字符串当中的最长的回

    2024年02月09日
    浏览(39)
  • 动态规划--回文串问题

    一)回文子串: 647. 回文子串 - 力扣(LeetCode) 思路1:暴力枚举: for(int i=0;iarray.length;i++) for(int j=i;jarray.length;j++) 我们的中心思路就是枚举出所有的子字符串,然后进行判断所有的子串是否是回文串 每一次我们固定i位置,j向后走, 就成功枚举出了以i位置为起点的所有回文字串的

    2024年04月22日
    浏览(49)
  • 点菜问题动态规划

    ‏ “因为疫情问题,某公司员工就餐时需通过APP点外卖。每次点外卖的报销金额最大为M元,有N种菜品可以点,每种菜i都有一个评分Pi(即表示菜的受欢迎程度),每种菜i的价格为Vi。现该公司员工如何选择各种菜,能够在报销额度范围内使点到的菜的总评分最大。注意:由

    2024年02月12日
    浏览(34)
  • 近似串匹配问题(动态规划)

    1.问题描述 2.思路分析 两个字符串文本P和样本T,对齐方式不一样则差别数不一样,编辑距离是最小差别数。 根据上课讲的两个例子最长公共子序列和背包问题类比分析,这两个问题都是从最后开始分析的,最长公共子序列分为最后一位相同和最后一位不同的情况,背包问题

    2024年02月10日
    浏览(26)
  • C++--动态规划路径问题

    1.不同路径 力扣 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径

    2024年02月15日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包