算法设计与分析 课件 许瑾晨 第十章 -综合应用

信息工程大学算法设计与分析综合应用国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版算法设计策略的分析和对比每种算法设计策略的特点算法设计策略间的联系和区别最大子段和问题穷举法穷举法的改进分治法动态规划在线算法最短路径问题单源最短路径问题迪杰斯特拉算法（贪心法）Bellman-Ford算法SPFA算法所有点对间的最短路径问题弗洛伊德算法（动态规划）资源分配问题动态规划贪心法回溯法分支限界法信息工程大学算法设计与分析综合应用—算法设计策略得对比国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版递归分治动态规划贪心回溯分支限界概率算法递归分治两者的关系：递归与分治密不可分，分治要使用递归，而递归隐含着分治的思想。通常把两者合二为一，统称为递归与分治策略。思想：函数调用自己关键：递归式和边界条件思想：分而治之关键：分、治、合分治动态规划两者的关系：都是通过把问题分解为子问题求解，子问题独立时用分治，子问题有重复时用动态规划。思想：最优子结构和重叠子问题关键：问题和子问题的最优值递归关系思想：分而治之关键：分、治、合动态规划贪心思想：最优子结构和重叠子问题关键：问题和子问题的最优值递归关系思想：一系列局部最优得到全局最优关键：选择正确的贪心选择策略两者的关系：求解的问题都具有最优子结构性质，如果具有贪心选择性质可以使用贪心法求解。回溯分支限界两者的关系：求解的问题都是对解空间树进行搜索，边搜索边判断；回溯使用深搜，分支限界使用广搜。思想：对解空间树进行深度优先搜索关键：设计合适的剪枝函数思想：对解空间树进行广度优先搜索关键：设计合适的限界函数算法设计策略之间有一定的联系和区别；

在解决具体问题时，应该根据问题的特点，选择合适的算法设计策略，使问题得到高效求解。信息工程大学算法设计与分析综合应用—最大子段和问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版已知某支股票连续若干天的价格，问：这段时间内，应该在哪天买入哪天卖出才能获得最大收益？天0123456789101112131415价格1001131108510510286638110194106101799490表1：某支股票的价格变动情况思路一：找最低价和最高价思路一：最低价买入，最高价卖出。不正确最低价出现在第7天，最高价出现在第1天。思路二思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。正确吗？1343思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。不正确反例：如下表中的最大收益是第2天买入、第3天卖出，与最低价和最高价无关。天01234价格10117106表2：某支股票的价格变动情况思路三：穷举法，计算所有前后两天的价格差，找最大的，即为最大收益。表1：某支股票的价格变动情况天0123456789101112131415价格1001131108510510286638110194106101799490intmax_value=0;fori=0ton-1forj=i+1ton{t=p[j]-p[i];if(t>max_value)max_value=t;}returnmax_value;时间复杂度为O(n2)思路四：从价格变化的角度考虑，最大收益等价于连续区间的价格变化之和最大的。表3：某支股票的价格变动情况天0123456789101112131415价格p1001131108510510286638110194106101799490变化a13-3-2520-3-16-231820-712-5-2215-4用a[i]表示第i天与前一天的价格差，则最大收益为给定一个序列，找连续区间中和的最大值。最大子段和例1：序列(-20,11,-4,13,-5,-2)的最大子段和为(11,-4,13)=20。例2：序列(-20,11,-4,-6,-5,-2)的最大子段和为(11)=11。例3：序列(-20,-11,-4,-13,-5,-2)的最大子段和为0。选择题序列(20,11,4,6,5,2)的最大子段和为（）。A.48B.20C.0D.以上都不对穷举法：计算所有连续区间的和，找其中最大的。a[i]a[j]1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5. for(i=1;i<=n;i++)/*a[i]为起点*/6. for(j=i;j<=n;j++){/*a[j]为终点*/7. ThisSum=0;8. for(k=i;k<=j;k++)/*累加a[i]~a[j]*/9. ThisSum+=a[k];10. if(ThisSum>MaxSum)MaxSum=ThisSum;12.}13. returnMaxSum;14.}时间复杂度为:O(n3)穷举法改进：去除重复计算，优化连续区间的求和方法。1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5

for(i=1;i<=n;i++){/*a[i]为起点*/6.

ThisSum=0;7.

for(j=i;j<=n;j++){/*a[j]为终点*/8.

ThisSum+=a[j];9.

if(ThisSum>MaxSum)10. MaxSum=ThisSum;11.}12}13. returnMaxSum;14.}时间复杂度为O(n2)a[i]a[j]a[j+1]分治法：序列一分为二，取三种情况的最大值。情况1：左边序列的最大子段和情况2：右边序列的最大子段和情况3：跨越中间位置的最大子段和-2011-4135-2110131120T(n/2)T(n/2)O(n)T(n)=2T(n/2)+cn,T(1)=O(1)=O(nlogn)01376/*分治法求最大子段和*/1.intMaxSum(int*a,intleft,intright){2.intsum=0;3.intcenter=0,leftsum=0,rightsum=0,lefts=0,rights=0,s1=0,s2=0;4.if(left==right){/*如果序列长度为1，直接求解*/5.

if(a[left]>0)sum=a[left];6.

elsesum=0;7.}else{8.center=(left+right)/2;9.leftsum=MaxSum(a,left,center);/*求左序列的最大子段和*/10.

rightsum=MaxSum(a,center+1,right);/*求右序列的最大子段和*/11.

s1=0;lefts=0;12.for(inti=center;i>=left;i--){/*求中间位置向左的最大和*/13. lefts+=a[i];if(lefts>s1)s1=lefts;}14.s2=0;rights=0;15.for(intj=center+1;j<=right;j++){/*求中间位置向右的最大和*/16.

rights+=a[j];if(rights>s2)s2=rights;}17.sum=s1+s2;18.if(sum<leftsum)sum=leftsum;19.if(sum<rightsum)sum=rightsum; 20.}21.returnsum;}动态规划：用dp[i]表示以第i项结尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整个问题的最大子段和为：max(dp[i]，0)。下标123456a[i]-2011-413-5-2dp[i]-20117152013动态规划：用dp[i]表示以第i项结尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整个问题的最大子段和为：max(dp[i],0)。/*动态规划求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. intMaxSum,i;4. dp[0]=0;5. MaxSum=0;/*MaxSum初始化为0，保证了最大子段和>=0*/6.

for(i=1;i<=n;i++){7. dp[i]=max(dp[i-1]+a[i],a[i]);8.

if(dp[i]>MaxSum)MaxSum=dp[i];9.}10. returnMaxSum;11.}时间复杂度为O(n)在线算法：从第1项开始，依次累加后面的项，如果小于等于0，则舍弃，否则继续累加，记录其中的最大值。下标123456a[i]-2011-413-5-21172015130/*在线算法求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. inttSum,MaxSum,j;4. tSum=MaxSum=0;5. for(j=1;j<=n;j++){6. tSum+=a[j];7. if(tSum>MaxSum)8. MaxSum=tSum;9. elseif(tSum<0)10. tSum=0;11. }12. returnMaxSum;13.}时间复杂度为O(n)在线算法：从第1项开始，依次累加后面的项，如果小于等于0，则舍弃，否则继续累加，记录其中的最大值。

从价格变化的角度考虑，问题等价于求解连续序列的最大和，抽象为最大子段和问题。以股票问题为例，考虑直观的求解思路：从最高价和最低价分析，但该方法并不正确。正确方法为：计算所有可能的情况，时间复杂度为O(n2)。问题转换讨论最大子段和问题的若干求解方法:穷举法O(n3)穷举法的改进O(n2)分治法O(nlogn)动态规划O(n)在线算法O(n)信息工程大学算法设计与分析综合应用—最短路径问题问题描述和分析国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版最短路径问题是图论中的一个经典问题，有以下几种常见形式：确定起点的最短路径问题确定终点的最短路径问题确定起点终点的最短路径问题任意两点间的最短路径问题单源最短路径问题

给定带权有向图G=(V,E)，图G的顶点编号为1~n(1≤n≤100)。求G中某两点间的最短路径长度。50102060100301012534从点1到其他点的最短路径是：1-21-41-4-31-4-3-550102060100301012534边数最长的最短路径是1-4-3-5，这个最短路径也包含了1到4、1到3的最短路径。可以从中发现什么？从点1到其他点的最短路径是：1-21-41-4-31-4-3-5一般地，假设从u

到点v的最短路径是u->u1->…uk->uk+1->v，那么从u到uk的最短路径是什么？50102060100301012534从u到v的最短路径包含了从u到u1、u2…uk、uk+1的最短路径。最短路径问题满足最优子结构性质：u到v的最短路径包含u到该路径上其它各点的最短路径。反证法：已知，一条从起点u到v的最短路径:uu1…uk+1vuu1u2…uk-1ukuk+1vⅠⅡ反证法：已知，一条从起点u到v的最短路径:uu1…uk+1vuu1u2…uk-1ukuk+1vⅠⅡ③做如下替换：ⅡⅠⅡⅢ④可得,路径的长度小于路径的长度ⅡⅠⅡⅢ⑤该结论与已知条件矛盾，假设不成立。①假设，路径Ⅰ不是起点u到中间点uk的最短路径。②则必然存在一条比路径Ⅰ更短的路径Ⅲ：uu’1…u’m-1ukuu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路径问题满足最优子结构性质：u到v的最短路径包含u到该路径上其它各点的最短路径。扩展：u到v的最短路径包含该路径上任意两点间的最短路径。信息工程大学算法设计与分析综合应用—最短路径问题迪杰斯特拉算法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

给定带权有向图G=(V,E)，其中每条边的权值是非负数，u称为源点；图G的顶点编号为1~n(1≤n≤100)。求从u到G中所有其余顶点的最短路径长度。50102060100301012534uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路径长度递增迪杰斯特拉(Dijkstra)提出：按最短路径长度递增的次序，依次产生每个点的最短路径。最短路径问题满足最优子结构性质：u到v的最短路径包含u到该路径上其它各点的最短路径。边的权值为非负判断题。Dijkstra算法按路径长度递增的次序依次产生源点到各点的最短路径。A.错误

B.正确uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路径长度递增Dijkstra提出：按最短路径长度递增的次序，依次产生每个点的最短路径。进一步可知：第一条最短路径：直达其他：利用已得到最短路径的点，求未知点的最短路径集合集合SS’S中的点表示已找到该点的最短路径S’中的点表示未找到最短路径的点1.将图中点分成两个集合：S和S’;集合集合SS’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；集合集合SS’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；3.从S’中选择距离最短的点v加入S中，并从S’中移除该点，同时更新S’中点的最短距离；集合S集合S’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；3.从S’中选择距离最短的点v加入S中，并从S’中移除该点，同时更新S’中点的最短距离；4.重复第3步，直到S’为空。算法需要的数据结构：1.对各点所处集合的状态进行标记，使用数组s；2.需要存储S’中各点的距离，使用数组dist；3.记录点的前驱，使用数组pre；初始时，先将源点u放入S。对u之外的每个顶点v，令dist[v]为边<u,v>的权或+∞；不断地做贪心选择来扩充S，直到所有顶点均进入S。贪心策略：如果顶点v不属于S，且dist[v]值最小，则优先选择v。当v加入S后，需调整尚未进入S的点的dist和pre。算法结束时，dist[i]就是u到点i的最短距离。迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,5550102060100301012534迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,55选择题。根据下表，源点1到点5的最短路径长度和最短路径是（）。A.60,1-5

B.60,1-3-5C.60,1-4-3-5/*graph表示图的邻接矩阵，u表示源点，n表示顶点总数*/voidDijkstra(int**graph,intu,intn){ints[MaxSize],i=0;memset(s,0,sizeof(s));s[u]=1;for(i=1;i<=n;i++){dist[i]=graph[u][i];pre[i]=-1;}i=1;while(i<n){v为

满足s[v]==0&&dist[v]最小的点;s[v]=1;i++;for(对每个相邻于v的顶点k){

if

（(s[k]==0)&&

(dist[v]+graph[v][k]<dist[k])）{

dist[k]=dist[v]+graph[v][k]); pre[k]=v; }}/*endfor*/}/*endwhile*/}时间复杂度：O(n2)/*借助优先队列实现迪杰斯特拉算法*/#include<iostream>#include<cstring>#include<queue>usingnamespacestd;#defineMaxSize101typedefstruct{intno;/*no表示顶点的编号，从1开始*/intdist=0x3f3f3f3f;/*dist表示长度，初值为一个较大的值*/intprev=0;/*prev表示源点到该点的最短路径中该点的前驱顶点的编号*/intflag=0;/*flag=0表示源点到该点的最短路径还未求出*/}vertex;structcomp{/*定义优先队列的排序规则*/booloperator()(vertexa,vertexb){returna.dist>b.dist;}};/*函数功能：dijkstra算法求解单源最短路径*//*参数说明：n表示图中顶点总数，graph表示图的邻接矩阵*//*a存储顶点信息，u表示源点编号*/voiddijsktra(intn,intgraph[][MaxSize],vertexa[],intu){priority_queue<vertex,vector<vertex>,comp>p;/*定义优先队列*/inti=0;a[u].dist=0;/*设置源点到它自身的最短路径长度为0*/p.push(a[u]);/*源点加入优先队列*/intt=0;vertexv;while(!p.empty()){v=p.top();/*取dist最小的顶点*/p.pop();/*dist最小的顶点出队*/t=v.no;a[t].flag=1;/*出队顶点的最短路径已得到*/ ……}借助优先队列优化算法时间复杂度O(|V|log|V|)单选题。

Dijkstra算法求解单源最短路径，适用于（）。 A.权值为非负 B.权值为负 C.权值无要求Q：迪杰斯特拉算法为什么需要“边的权值为非负数”？12323-101233-241236-25图中有负值环时，不存在最短路径；图中无负值环但存在负值边时，不能使用Dijkstra。图1有负值环时，不存在最短路径图2有负值边，但可以得到正确解图3有负值边，不能得到正确解12323-101233-241236-25信息工程大学算法设计与分析综合应用—最短路径问题-贝尔曼·福特算法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版当图中存在负权边时，迪杰斯特拉算法无法正确求解单源最短路径问题。这种情况下，该如何求解呢？理查德·贝尔曼（RichardBellman）和莱斯特·福特共同提出了Bellman-Ford算法。

该算法可以求解有负权边的单源最短路径问题，也可以判断图中是否存在负环。

边(u,v)的松弛过程：Relax(u,v,w){if(d[v]>d[u]+w(u,v)){d[v]=d[u]+w(u,v);pre[v]=u;}}d[v]：记录源点s到v的最短路径估计w(u,v)：记录点u到点v的边的权值pre[v]：记录点v的前驱uvsBellman-Ford算法通过边的松弛操作得到单源最短路径。Bellman-Ford算法过程：1.对所有边进行(|V|-1)

轮松弛操作，得到源点到所有点的最短路径长度；2.再进行1轮松弛操作，如果发现某些点的最短路径长度仍有更新，则说明图中存在负环。

初始化点dpreA0-1B∞-1C∞-1D∞-1E∞-11.初始化，设源点为A。初始化d数组。初始化pre数组。

初始化第一轮点dpredpreA0-10-1B∞-1-1AC∞-12BD∞-11BE∞-11B2.对所有边进行第一轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。

初始化第一轮第二轮点dpredpredpreA0-10-10-1B∞-1-1A-1AC∞-12B2BD∞-11B-2EE∞-11B1B3.对所有边进行第二轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。

初始化第一轮第二轮第三轮第四轮第五轮点dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1B4.对所有边进行第三~五轮松弛操作。依次遍历边A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d数组和pre数组。/*贝尔曼•福特算法求解单源最短路径*/voidBellman-Ford(G,w,s){/*G表示有向网，w表示邻接矩阵，s表示源点*//*1.初始化*/d[s]=0;pre[s]=-1;foreachv∈V-{s}{d[v]=+∞;pre[v]=-1;}

/*2.松弛步骤*/fori=1to|V|-1foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)){ d[v]=d[u]+w(u,v); pre[v]=u;}

/*3.检查是否存在负值环*/foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)) printf(“存在负值环”);}时间复杂度：O(VE)

定理：如果图G=(V,E)不包含负环，执行Bellman-Ford算法后，d[v]即是源点s到点v的最短路径距离。证明：假设v是G中的任一结点，从源点s到v、且边数最少的最短路径为p，如图10-10所示：

证明：假设v是G中的任一结点，从源点v0到vk、长度最短且边数最少的最短路径为p，如下图所示：

由于p是最短路径，有d[vi]=d[vi-1]+w(vi-1,vi)。

第一轮遍历后，有d[v1]=d[v0]+w(v0,v1)；

第二轮遍历后，有d[v2]=d[v1]+w(v1,v2)；

……

第k轮遍历后，有d[v]=d[vk]=d[vk-1]+w(vk-1,vk)。

由于图G没有负值环存在，路径p是一条简单路径（边数最少），因此，路径p最多有(|V|-1)条边，Bellman-Ford算法经过(|V|-1)轮遍历后，可以得到每个点的单源最短路径。

推论：如果在(|V|-1)轮遍历后，存在某个点的最短路径距离仍然有变化，那么G中存在负值环。

如下图所示，经过(|V|-1)轮遍历，可得从源点到v1、v2、…、vk的当前最短路径距离；

继续进行第|V|轮遍历时，假定从vk到v2存在一条边，此时d[v2]=min{d[v2],d[vk]+w(vk,v2)}，若d[v2]有更新，说明从源点s(v0)->v1->v2->…->vk->v2是比s(v0)->v1->v2更短的一条路径，即v2->…->vk->v2构成一个负值环。因此，推论成立。负环思考：什么情况发生松弛操作？只有d[u]更新后，从u发出的点才可能进行松弛操作。

初始化第一轮第二轮第三轮第四轮第五轮点dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1BBellman-Ford算法的优化1.首先对从源点发出的边进行松弛操作；2.找到d[u]降低的点u，继续对从点u发出的边进行松弛操作；3.重复步骤2，直到所有点的最短路径长度d[i]都不再改变。SPFA(ShortestPathFasterAlgorithm)while(队列不为空){取出队列中结点；松弛它发出的边；把最短路径长度有更新的点加入队列；}队列d[A]d[B]d[C]d[D]d[E]A0∞∞∞∞B、C0-14∞∞C、D、E0-1211D、E0-1211E0-1211D0-12-210-12-21SPFA算法的局限性：1.无法判断负环，因为一个点可能被入队多次2.最坏时间复杂度没有改进3.实际运行效果可能不如Bellman-Ford算法上述过程是不断发现问题、解决问题的过程！发现问题比解决问题更重要！

科学研究、创新研发的道路从来都不是一帆风顺的，只要朝着正确的方向，坚持下去，一定有收获！信息工程大学算法设计与分析综合应用—最短路径问题-弗洛伊德算法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版思考：如何求解任意两点间的最短路径？

重复执行迪杰斯特拉(Dijkstra)算法|V|次。总的执行时间为O(|V|3)。

重复执行Bellman-Ford算法|V|次。总的执行时间为O(|E||V|2)，稠密图需O(|V|4)。

弗洛伊德（Floyd）算法。时间复杂度也是O(|V|3)，但形式上非常简洁优雅，而且对于比较稠密的图，实际运行效率更快。求解任意两点间的最短路径：ikj最短路径问题满足最优子结构性质：u到v的最短路径包含该路径上任意两点间的最短路径。用d(i,j)表示i到j的最短路径长度，k是该路径上的一个中间点（k=1,2,3,…,n），那么有d(i,j)=min{w(i,j),d(i,k)+d(k,j)},w(i,j)是边(i,j)的权值定义d[k][i][j]：中间点编号≤k，点i到点j之间的最短路径长度。iji1jk=1时，d[1][i][j]得到中间点编号不超过1的最短路径长度，包括：直达路径以1号点为中间点的路径d[k][i][j]的含义：中间点编号≤k，点i到点j之间的最短路径长度。k=2时，d[2][i][j]得到中间点编号不超过2的最短路径长度，包括：i1jiji2ji2j1i1j2直达路径以1号点为中间点的路径以2号点为中间点的路径依次经过1、2点的路径依次经过2、1点的路径d[k][i][j]的含义：中间点编号≤k，点i到点j之间的最短路径长度。k=n时，d[n][i][j]得到中间点编号不超过n的最短路径长度，即i到j的最短路径长度。可以按照中间点编号k从小到大的顺序寻找最短路径。关键问题：已知d[k-1][i][j]，如何求解d[k][i][j]？d[k][i][j]的含义：中间点编号≤k，点i到点j之间的最短路径长度。对于d[k][i][j]，可以分为两种情况：（1）i到j的最短路不经过k：d[k][i][j]=d[k-1][i][j]。（2）i到j的最短路经过k：d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。d[i][j]=min(d[i][j],d[i][k]+d[k][j]),

k,i,j∈[1,n];d[k][i][j]的含义：中间点编号≤k，点i到点j之间的最短路径长度。弗洛伊德算法(Floyd)因此，最短路径的递归关系式：d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])

（k,i,j∈[1,n]）[例]给出一个有向网及其邻接矩阵A。用Floyd算法求该有向网中每对顶点之间的最短路径长度及其最短路径。d(0)[i][j]的含义是：从vi到vj的直达的最短路径长度d(0)v1(a)

v2(b)

v3(c)

v4(d)0

5∞

∞10061

∞04∞820v1v2v3v4d(0)v1(a)

v2(b)

v3(c)

v4(d)0

5∞

∞10061

∞04∞820v1v2v3v4v1v2v3v40

5∞

∞10061

∞04∞820v1v2v3v4d(1)v1v2v3v40

5∞

∞0613804∞820v1v2v3v4d(1)v1v2v3v40

5∞

∞0613804∞820v1v2v3v4v1v2v3v40

5∞

∞0613804∞820v1v2v3v4d(2)v1v2v3v40

5116061380418820v1v2v3v4v1v2v3v40

511

610061

80418820v1v2v3v4d(3)v1v2v3v40

511

6906138045820v1v2v3v4v1v2v3v40

511

6906138045820v1v2v3v4d(4)v1v2v3v40

586603138045820v1v2v3v4d(2)v1v2v3v40

5116061380418820v1v2v3v4d(3)v1v2v3v40

511

6906138045820v1v2v3v4单选题。以下说法正确的是（）。A.Floyd算法适用于权值为负的情况B.Floyd算法不适用于权值为负的情况p(0)[i][j]=i的含义是：从vi到vj的最短路径中，vj的前驱结点为vip(4)[2][1]=4的含义是：从v2到v1的最短路径中，v1的前驱为点v4p(0)v1v2v3v41

1-1-122223-133-1444v1v2v3v4p(1)v1v2v3v41

1-1-122223133-1444v1v2v3v4p(2)v1v2v3v41

122222231332444v1v2v3v4p(3)v1v2v3v41

122322231333444v1v2v3v4p(4)v1v2v3v41

142424231333444v1v2v3v4单选题。下图是最终得到的前驱矩阵，从V1到V3点的最短路径是（）。 A.v1-v4-v3 B.v1-v3 C.v1-v2-v4-v3 D.以上都不对P(4)v1v2v3v41

142424231333444v1v2v3v4void

floyd(){/*Floyd算法求解任意两点间的最短路径*//*初始化*/

for(int

i=1;i<=n;i++)

for(int

j=1;j<=n;j++)

d[0][i][j]=graph[i][j];

/*自底向上动态规划求解*/

for(int

k=1;k<=n;k++){

for(int

i=1;i<=n;i++){

for(int

j=1;j<=n;j++){

d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]);

}

}}}时间复杂度：O(n3)空间复杂度：O(n2)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);d[i][j]=graph[i][j];信息工程大学算法设计与分析综合应用—资源分配问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

有一笔资金共计m份，现给n个工程项目投资，给第i项工程投资资金j(份)所得的收益用p(i,j)(i,j为非负整数)表示。问应该如何分配资金，使得投资的收益最大。

比如m=4，n=3时，p(i,j)如下表所示，给工程1、2、3分别分配资金1、1、2时获得最大收益为43。投资金额01234工程1收益013151922工程2收益01213.514.516工程3收益014182124分配资金的方法很多，从中选择收益最大的。该问题是一个最优化问题，如果符合最优子结构性质，进一步判断是否可用动态规划和贪心法求解。该问题也是一个搜索问题，可以用回溯法、分支限界求解。结合实例分析：当m=4，n=3时，对应的最优解为（1，1，2），那么，(1,1)是2份资金给工程1、2投资对应的最佳分配方案。投资金额01234