精华内容
下载资源
问答
  • 动态规划求解多段图问题

    千次阅读 2019-04-26 19:45:40
    首先,动态规划的求解思想可以归纳为两个步骤: ...接下来就是求解多段图问题 多段图G=(V, E)是一个有向图。它具有如下特性: 图中的结点被划分成 k³ 2个不相交的集合Vi ,1£i£k,其中V1和...

    首先,动态规划的求解思想可以归纳为两个步骤:

    1.证明问题满足最优性原理

    2.给出递推关系式

    *对于最优性原理,我们做如下的解释:

    无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。


    接下来就是求解多段图问题

    多段图G=(V, E)是一个有向图。它具有如下特性:

    图中的结点被划分成 k³ 2个不相交的集合Vi 1£i£k,其中V1Vk分别只有一个结点 s (源点) t (汇点)

    图中所有的<u, v>均具有如下性质:

        若,则v\inVi+11<i<k,且每条边<u, v>均                                                                                                               附有成本c(u, v)

    pst的一条路径成本是这条路径上边的成本和

    p多段图问题是求st的最小成本路径


    多段图问题的最优性原理证明:

    假设s,v2,v3,.......,vk-1,t是一条由st的最短路径。

    再假设从源点s开始,已作出了到结点v2的决策,因此v2就是初始决策所产生的状态。

    如果把v2看成是原问题的一个子问题的初始状态,解决这个子问题就是找出一条由v2t的最短路径。

    这条最短路径显然是v2,v3.......,vk-1,t .

    如果不是,设v2,q3,.......,qk-1,t是由v2t的更短路径,则s,v2,q3,.......,qk-1,t是一条比路径s,v2,v3,.......,vk-1,t更短的由st的路径,与假设矛盾,因此最优性原理成立。


    多段图的递推分析:

    向前处理法(forward approach)

      从最后阶段开始,以逐步向前递推的方式,列出求解前一阶段决策值的递推关系式,即根据xi+1, ¼, xn的那些最优决策序列来列出求取xi决策值的关系式。

    向后处理法(backward approach)

       从初始阶段开始,以逐步向后递推的方式,列出求解后一阶段决策值的递推关系式,即根据x1, ¼, xi-1的那些最优决策序列来列出求取xi决策值的关系式。


    多段图向前处理递推关系式:

    向前处理法:从最后阶段开始,逐步向前递推,根据xi+1, ¼, xn的那些最优

    决策序列来列出求取xi决策值的关系式。

     

    P(i, j)是一条从Vi中的结点j 汇点t 的最小成本路径,

       COST(i, j)表示从结点j 汇点t这条路径的成本。

    根据向前处理方法:

        COST(i, j)= min{ c(j, l)+COST(i+1, l)}

       其中:lÎVi+1<j, l>ÎE,  c(j, l)表示该边的成本。


    多段图向前处理的计算过程:

    初始化:对于k段图,当i=k-1时,

    如果<j, t>ÎECOST(k-1, j)= c(j, t)

    如果<j, t>ÏECOST(k-1, j)=\infty


    多段图向前处理的计算过程:

    COST(i, j)=min{ c(j, l)+COST(i+1, l)}

    COST(4, 9)=c(9,12)=4

    COST(4,10)=c(10,12)=2

    COST(4,11)=c(11,12)=5

    COST(3,6)=min{c(6,9)+COST(4,9) ,

                                 c(6,10)+COST(4,10)}

                       =min{6+4, 5+2}=7

    COST(3,7)=min{c(7,9)+COST(4,9) , c(7,10)+COST(4,10)}

                      =min{4+4, 3+2}=5

    COST(3,8)=min{c(8,10)+COST(4,10) , c(8,11)+COST(4,11)}

                      =min{5+2, 6+5}=7

    COST(3,6)=7

    COST(3,7)=5

    COST(3,8)=7

     

    COST(2,2)

    =min{c(2,6)+COST(3,6),

              c(2,7)+COST(3,7),

              c(2,8)+COST(3,8)}

    =min{4+7, 2+5, 1+7}=7

     

    COST(2,3)=min{2+7,7+5}=9

    COST(2,4)=min{11+7}=18

    COST(2,5)=min{11+5,8+7}=15

     

    COST(1,1)

    =min{c(1,2)+COST(2,2),

              c(1,3)+COST(2,3),

              c(1,4)+COST(2,4),

              c(1,5)+COST(2,5)}

    =min{9+7,7+9,3+18,2+15}=16

     

    展开全文
  • 动态规划——多段图问题

    千次阅读 2019-08-01 11:04:55
    多段图问题 多段图问题是利用动态规划思想解决的经典问题之一,在日常生活中应用广泛。 问题描述 若存在一个有向加权图G,且G能分出起点和终点以及中间的n的阶段,求起点到终点的最短(长)距离。 分析设计 通过上...

    多段图问题

    多段图问题是利用动态规划思想解决的经典问题之一,在日常生活中应用广泛。

    问题描述

    若存在一个有向加权图G,且G能分出起点终点以及中间的n的阶段,求起点到终点的最短(长)距离
    博客中代码以此图编写

    分析设计

    通过上图我们可以很容易知道,如果用穷举的方法是没有办法求解的,问题规模实在太大,我们需要使用其他更为高效的算法:动态规划

    动态规划解决该问题的主要思想:n个阶段的大问题很难求解,可以将其进行划分成子问题:n-1个阶段的多段图……1个阶段的子问题容易解决,就能解决整个问题。也就是说每一个阶段都是整个问题的一个最优子结构

    如果从点s到点t的最短路径经过点vi,则vi到t也是最短距离。

    构造规划方程:
    fi = min{fi-1[n] + xi}
    i是该段图中的点,fi 表示该点到终点的最短距离,xi表示该点到上一阶段的点的距离;

    因此多段图问题的算法步骤为:

    1. 从最后一段算起,找出每段的每个点的最短距离;
    2. 每段逐一向前推,直到算至起点;
    3. 比较从起点到终点的距离得出最短距离。

    源代码

    #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;					//i+1阶段的点
    			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;
    }
    

    运行结果

    在这里插入图片描述

    展开全文
  • 动态规划法(五)——多段图问题

    千次阅读 2017-04-11 14:36:35
    给定一个多段图,求出多段图中的最短路径和最短路径长度。 什么是多段图多段图是一个有向、无环、带权 图。 有且仅有一个起始结点(原点source) 和 一个终止结点(汇点target)。 它有n个阶段,每个阶段由特定...

    这里写图片描述

    问题描述

    给定一个多段图,求出多段图中的最短路径和最短路径长度。

    什么是多段图?

    • 多段图是一个有向、无环、带权 图。
    • 有且仅有一个起始结点(原点source) 和 一个终止结点(汇点target)。
    • 它有n个阶段,每个阶段由特定的几个结点构成。
    • 每个结点的所有结点都只能指向下一个相邻的阶段,阶段之间不能越界。
      title

    数据结构

    • cost数组:
      该数组用于记录以某个结点为起点,到终点t的最短路径长度值。
      数组的下标表示结点的编号(因此所有结点都必须从0开始依次编号),数组的值表示:以该结点为起点,到终点的最短路径长度。
    • d数组:
      该数组用于记录最短路径中出现的所有结点。
      下标表示结点的编号,d[i]表示:结点i的后继结点编号。

    算法思路

    算法流程

    1. 从前往后依次给所有结点编号;序号必须从0开始,依次递增,同一阶段的结点顺序可以随意;
    2. 创建数组cost和d,分别记录每个结点的最短路径长度 和 每个结点最短路径的前驱结点;
    3. 从最后一个结点开始,从后向前,依次计算每个结点的cost值和d值;
    4. 直到将所有结点都计算完毕后,即可得到最短路径。

    每个结点cost和d的计算方法

    设当前要计算cost[i]的值。

    1. 找到i结点所有的出边,假设出边的终点分别是a、b、c,边上的权值分别是w1、w2、w3;
    2. 分别计算w1+cost[a]、w2+cost[b]、w3+cost[c],将其中最小的那个值作为cost[i];并将最小的那个后继结点作为d[i]。

    这里写图片描述

    展开全文
  • 多段图的最短路径问题 问题:设图G=(V,E)是一个带权有向图,如果把顶点集合V划分成k个互不相交的子集Vi(2<=k<=n,1<=i<=k), 使得E中的任何一条边<u,v>,必有u∈Vi,v∈Vi+m(1<=i<k,1&...

    多段图的最短路径问题

    问题:设图G=(V,E)是一个带权有向图,如果把顶点集合V划分成k个互不相交的子集Vi(2<=k<=n,1<=i<=k),

              使得E中的任何一条边<u,v>,必有u∈Vi, v∈Vi+m(1<=i<k,1<i+m<=k),则称图G为多段图,称s∈V1为源点,

             t∈Vk为终点。

             多段图的最短路径问题为从源点到终点的最小代价路径。

    子问题:设Cuv表示多段图的有向边<u,v>上的权值,将从源点s到终点t的最短路径长度即为d(s,t),

                  考虑原问题的部分解d(s,v),显然有下式成立

                 d(s,v)=Csu                                  (<s,v>∈E)

                 d(s,v)=min(d(s,u)+Cuv)            (<u,v>∈E)

    算法:多段图的最短路径问题

    输入:多段图的代价矩阵

    输出:最短长度及路径c[n][n]

    1.循环变量j从1~n-1重复下述操作,执行填表工作

       1.1考察顶点j的所有入边,对于边<i,j>∈E,执行下述操作

           1.1.1cost[j]=min{cost[i]+c[i][j]};

           1.1.2path[j]=使cost[i]+c[i][j]最小的i;

         1.2 j++;

    2.输出最短路径长度cost[n-1];

    3.循环变量i=path[n-1].循环直到path[i]=0,输出最短路径经过的顶点;

       3.1 输出path[i];

       3.2 i=path[i]

    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #define Max 0xffff
    using namespace std;
    //动态规划求最短路径
    void dp_path(int c[][100], int *cost, int *path) {
        int m, n;
        cout << "输入顶点个数和边个数" << endl;
        cin >> n >> m;
        //初始化代价矩阵
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                c[i][j] = Max;
        //输入代价矩阵
        int u, v, s;
        for (int i = 0; i < m; i++) {
            cin >> u >> v >> s;
            //cout<<u<<v<<s<<endl;
            c[u][v] = s;
        }
        for(int i=0;i<n;i++)
            cost[i]=Max;
        path[0] = -1;
        cost[0] = 0;
        for (int j = 1; j < n; j++) {
            for (int i = j-1; i >=0; i--) {
                if (cost[j] > cost[i] + c[i][j]) {
                    path[j] = i;
                    cost[j] = cost[i] + c[i][j];
                }
            }
        }
        cout<<cost[n-1]<<endl;
        int i=path[n-1];
        cout<<path[n-1]<<endl;
        while(path[i]>=0){
            cout<<path[i]<<endl;
            i=path[i];
        }
    }
    int main()
    {
        int c[100][100], cost[100], path[100];
        dp_path(c, cost, path);
        getchar();
        return 0;
    }

     

    转载于:https://www.cnblogs.com/zuoyou151/p/9028675.html

    展开全文
  • 多段图的最短路径问题-----动态规划法

    万次阅读 多人点赞 2013-06-06 22:27:01
    多段图,求最短路径,如图: 对其使用动态规划法: 阶段:将图中的顶点划分5个阶段,k 状态:每个阶段有几种供选择的点s 决策:当前状态应在前一个状态的基础上获得。决策需要满足规划方程 规划方程:f(k)...
  • 多段图的最短路径问题

    千次阅读 2015-09-02 17:03:06
    求源点0到终点9的最短路径 ...int inp(int n) //求n个顶点的多段图的最短路径 { int i,j,temp; for(i=1;i =0;j--) //考察所有入边 { if(arc[j][i]+cost[j] =0) //依次输出path[i] { cout
  • [图算法]多段图最短路径

    千次阅读 2015-11-15 21:06:53
    [图算法]多段图最短路径多段图最短路径问题是应用动态规划的经典问题之一,许多优化问题都能转化为多段图最短路径问题进而求解。多段图最短路径的问题描述如下:问题描述 设G=(V,E)是一个赋权有向图,其顶点集V被...
  • 多段图的动态规划算法(C、C++)

    千次阅读 2019-05-06 22:39:43
    多段图问题是一种特殊的有向无环图的最短路径问题。其中产生从源点s到汇点t的最短路径的决策序列就是最优决策,此长度最短的路径是最优解,而路径长度就是最优解值。 (2) 数据结构: 采用邻接表存储该有向无环图...
  • 时间复杂度为O(m+k):m为边的数目,k为的数目。 #include<iostream> using namespace std; #define INF 999 int arc[100][100]; // 最多100个点 int CreateGraph() { int vnum,arcnum; cout<<"请...
  • 动态规划---->多段图

    万次阅读 多人点赞 2013-05-14 09:36:12
    多段图问题是求由s到t的最小成本路径。 图中的结点被划分成 k≥ 2个不相交的集合Vi , 1≤i≤k,其中V1和Vk分别只有一个结点 s (源点) 和t ( 汇点)。 多段图向前处理的算法 1、算法执行过程 COST[j]=c(j,r)+...
  • 经典算法7:动态规划之多段图

    千次阅读 2013-06-27 13:32:24
    一.实验要求 1. 理解最优子结构的问题。 有一类问题的活动过程可以分成若干个阶段,而且在任一阶段后的行为依赖于该阶段的状态,与该阶段之前的过程如何达到这种状态的...对于一个阶段过程问题,是否可以分段实现
  • 多段图最短路径

    千次阅读 2014-11-30 16:42:46
    问题描述:设是一个赋权有向,其顶点集V被划分为个不相交的子集,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中:, 且边(u,v)有一个正...
  • 毕业论文 一级标题问题

    千次阅读 2020-07-03 00:36:42
    说,直接上 这里这个前明显与实际不符,怎么改了,按如下步骤来: 1)点开大纲视图 2)你可能会看到这个标题前面是分节符和分页符,分页符可能是造成这个问题的关键,所以我们删除 “分页符” 3...
  • 动态规划--多段图最短路径

    万次阅读 2017-10-29 12:50:17
    问题描述:设是一个赋权有向,其顶点集V被划分为个不相交的子集,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中:, 且边(u,v)有一个正...
  • 秒杀线程第五篇 经典线程同步 关键CS

    万次阅读 多人点赞 2012-04-11 09:06:40
    上一篇《秒杀线程第四篇 一个经典的线程同步问题》提出了一个经典的线程同步互斥问题,本篇将用关键CRITICAL_SECTION来尝试解决这个问题。本文首先介绍下如何使用关键,然后再深层次的分析下关键的实现...
  • webpack打包后图片显示问题

    万次阅读 2018-05-04 13:22:42
    1、先解释一下这配置代码的意思,test是正则匹配规则,匹配项目中所有的以正则规则结尾的格式的文件,然后通过url-loader进行处理,不大于10kb就会进行base64转码,就是将图片转为base65格式,如果超过10KB的图片...
  • 关于在HTML表格中插入背景图片图片重复显示的问题

    万次阅读 多人点赞 2015-05-13 19:15:40
    先来一问题的代码(其实也不能说是有问题,毕竟语法上是没问题的,只是出来的效果不是我们想要的——我们假设预期的效果是背景图片只填充一次而不是次。) 设定表格的背景图像 姓名 张三 性别...
  • 谈谈程序中BSS大小问题

    千次阅读 2016-01-22 17:13:14
    前几天,有一位网友编译eCos时,出现了BSS错误,提示的错误信息大概是:ld: address 0x2000f028 of stress_threads section .bss is not within region sram。...所以,本文主要谈谈BSS段问题,以及
  • latex第一的首行缩进问题

    万次阅读 多人点赞 2018-06-16 22:18:16
    \indent也是首行缩进 %第一第一行的缩进只能用 \hspace{0.5em} 来控制空格的多少,解决中文排版问题。 \hspace{0.5em}随着科学技术和互联网行业的发展,其中以文字、图像和声音为主要内容的多媒体技术也飞速发展...
  • 动态规划法求多段图的最短路径

    千次阅读 2006-12-20 16:29:00
    #include "stdio.h"#include "conio.h"#define n 16 /*的顶点数*/#define k 7 /*数*/#define l 30#define MAX 100typedef int NodeNumber;/*节点编号*/typedef int CostType;/*成本值类型*/CostType cost[n...
  • 解决 DataGrip 无法提示表字段问题

    千次阅读 2018-04-16 13:59:27
    使用 DataGrip 过程中发现当前数据库用户下无法提示表字,编写 SQL 语句比较麻烦。经过一番的搜索,没能发现问题对应的答案。自动手动操作,探索一番……突然间发现,测试环境上的用户居然可以提示,那就表示配置...
  • RunLoop优化加载大量图片的卡顿问题

    千次阅读 热门讨论 2017-02-10 11:46:32
    经典问题:在tableView的cell上加载高清大,tableView上有很这样的cell,也就是说 页面展示的时候,要展示大量高清大。 普通的写法会造成刷新UI耗费大量时间,使主线程阻塞。给用户直观的体验就是页面卡顿 ...
  • Android使用XUtils多图片上传

    千次阅读 多人点赞 2015-11-04 15:57:53
    Android使用Xutils框架实现多图片上传。
  • 秒杀线程第四篇 一个经典的线程同步问题

    万次阅读 多人点赞 2012-04-10 09:57:02
    这个问题涉及到线程的同步和互斥,是一道非常有代表性的线程同步问题,如果能将这个问题搞清楚,那么对线程同步也就打下了良好的基础。 程序描述:主线程启动10个子线程并将表示子线程序号的变量地址作为参数...
  • 最近在做项目,发现使用ueditor上传图片后拖动图片不能手机端自适应的问题,在网上搜索和好多都不能解决,经过次测试 发现拖拽图片的时候会自动添加style属性,导致图片不能自使用手机端,经过查看源代码发现在...
  • Anaconda卸载不彻底以及环境串用问题卸载问题多环境串用问题功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中...
  • MATLAB GUI界面切换问题及其他相关问题

    万次阅读 多人点赞 2019-06-01 15:03:59
    由于前时间,一直在从事MATLAB GUI方面的设计工作,尤其是在界面切换方面的经验尤其,所以分享出来。 首先是切面切换的问题,这是个简单的问题,其实就是新建一个GUI,然后在GUI上创建面板的工作 然后...
  • 基于cefsharp项目用C#开发的程序在windows 系统上运行一时间老是出现崩溃卡死的情况 如下: 经过次测试和调查 发现是在部分机器上才出现该问题 ,其他机器连续运行一周也无错误出现 研读了国内外很...
  • 秒杀线程第十篇 生产者消费者问题

    万次阅读 多人点赞 2012-05-21 10:18:09
    生产者消费者问题是一个著名的线程同步问题,该问题描述如下:有一个生产者在生产产品,这些产品将提供给若干个消费者去消费,为了使生产者和消费者能并发执行,在两者之间设置一个具有个缓冲区的缓冲池,生产者将...
  • 前段时间在项目中需要将Shp文件中的多线段(Polyline)的坐标提取出来,存成坐标序列文件如XML,方便前端应用中展示。 于是直接将Polyline强转为IPointCollection接口,...原来ArcGIS中多段线(Polyline)有一部分是结

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,390,173
精华内容 556,069
关键字:

多段图问题