动态规划求最短路径实验报告_单源最短路径dijkstra算法「建议收藏」

动态规划求最短路径实验报告_单源最短路径dijkstra算法「建议收藏」1.问题描述给定先把图G(V,E),用动态规划的算法求一条从起点到终点的路径,使这条路径上经过的所有边的权重之和最小

1. 问题描述

给定先把图 G(V,E),用动态规划的算法求一条从起点到终点的路径,使这条路径上经过的所 有边的权重之和最小。
在这里插入图片描述

2. 算法描述

2.1 动态规划描述

动态规划是一种用来解决一类最优化问题的算法思想,将一个复杂的问题分解成若干个子问 题,通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的 解记录下来,这样下一次碰到同样的子问题时,就可以直接使用之前记录的结果。
在动态规划中,我们通常使用两种办法来求解:递推的自底向上办法(Bottom-up)递归的 自顶向下办法(Top-down),在本题我们采用递推的自底向上办法。
在最短路径问题中,我们首先要找到路径图中的拓扑排序顺序,作为递推的顺序。因为只有 知道当前节点所有入度节点的路径最大值,我们才能知道该节点的状态最优解。

2.2 拓扑排序

下面是拓扑排序的算法:

  1. 定义一个队列 Q,并把所有入度为 0 的节点加入序列。
  2. 取队列首节点,输出。然后删去所有从它出发的边。并另这些边到达顶点的入度减 1,如
    果某个顶点的入度减为 0,则将其加入队列。
  3. 反复进行步骤 2,直到队列为空。

当前节点 0 的入度为 0,将该节点加入序列中。用 S 记录下拓扑排序的顺序。S = [0]
在这里插入图片描述
删除从节点 0 出发的所有边
在这里插入图片描述
在这里插入图片描述
当前入度为 0 的节点为节点 1 和节点 6,将这两个节点加入序列并依次执行步骤 2 操作。 S=[0,6,1]
在这里插入图片描述
在这里插入图片描述
在当前的路径图中,节点 3 的入度为 0,加入队列,并执行步骤 2。S=[0,1,6,3]
在这里插入图片描述
在这里插入图片描述
将顶点 2 加入序列,并执行步骤 2。S=[0,1,6,3,2]
在这里插入图片描述
在这里插入图片描述
当前顶点 5 是入度为 0 的顶点,将其加入队列并执行步骤 2。S=[0,1,6,3,2,5]
在这里插入图片描述
在这里插入图片描述
顶点 4 是入度为 0 的节点,将其加入队列,并执行步骤 2。S=[0,1,6,3,2,5]
在这里插入图片描述
在这里插入图片描述
到达节点 7,将终点加入 S,S=[0,1,6,3,2,5,7],我们得到了拓扑排序的顺序

2.3 递推(Bottom-up Approach)

在得到拓扑排序 S=[0,1,6,3,2,5,7]后,我们使用动态规划的递推方法来得到该路径图从起点 到终点的最短路径。
在当前节点中考虑该节点所有入度的情况,比较上一跳最短路径加上上一跳到该节点的路径 长度的和与其他节点指向该节点的最短路径的长的大小。我们可以得到下面的表格。
在这里插入图片描述

3. 实验代码

// An highlighted block
import copy 
#拓扑排序
def topological_order(paths,indegree): 
	tempindegree = copy.deepcopy(indegree) 
	order = [] 
	for i in range(len(tempindegree)): 
		if tempindegree[i] == 0: 
			order.append(i) 
	num = 1 
	finalorder = [] 
	while len(order) != 0: 
		u = order.pop() 
		finalorder.append(u) 
		if num == len(tempindegree): 
			print("拓扑排序:",finalorder) 
			return finalorder 
	
		for j in range(len(paths)): 
			if paths[j][0] == u: 
				v = paths[j][1] 
				tempindegree[v] = tempindegree[v] - 1 
				if tempindegree[v] == 0: 
					order.append(v) 
					num = num + 1 
					#print(order)

if __name__ == "__main__": 
	paths = [ 
		#用邻接表存储下这张表 
		[0,1,5], 
		[0,6,3], 
		[1,2,2], 
		[1,3,1], 
		[2,4,7], 
		[2,5,3], 
		[3,2,1], 
		[3,4,2], 
		[3,5,1], 
		[4,7,1], 
		[5,4,2], 
		[5,7,5], 
		[6,2,2] ]
	
	#存储每个节点的入度 
	indegree = [0,1,2,1,3,2,1,2]
	finalorder = topological_order(paths,indegree) 
	#每个节点当前的最短路径长度和上一跳的节点 
	length = [0,0,0,0,0,0,0,0] 
	lastnode = [-1,-1,-1,-1,-1,-1,-1,-1]
	for i in finalorder: 
		for j in range(len(paths)): 
			if i == paths[j][1]: 
				if length[i] != 0 and length[i] < (length[paths[j][0]] + paths[j][2]): 
					continue 
				else:
					#print("节点:",i,"path:",length[paths[j][0]],",", paths[j][2]) 
					length[i] = length[paths[j][0]] + paths[j][2] 
					lastnode[i] = paths[j][0] 
	print("节点当前走过的最短路径",length) 
	print("上一跳节点",lastnode) 
	shortestpath = [] 
	index = len(lastnode) - 1 
	while index != 0: 
		shortestpath.append(index) 
		index = lastnode[index] 
	shortestpath.append(0) 
	shortestpath.reverse() 
	print("最短路径的长度:",length[-1]) 
	print("最短路径:",shortestpath)

4. 实验结果

成功运行代码后,我们得到了下面的实验结果。
在这里插入图片描述
这与我们的推论相符,实验成功。 在该问题中的最优子结构为每个节点相应的最短路径,使用拓扑排序我们肯定可以得到当前 节点所有入度情况并进行分析比较。通过记录下当前问题的最优子结构,我们可以避免重叠 问题的重复求解,这种动态规划的思想很好地提高了算法的效率。

参考和致谢

[1]胡凡,曾磊.算法笔记[M].机械工业出版社:北京,2016.7:390-392.
[2]【MIT 课程】动态规划 I-最短路径算法 https://www.bilibili.com/video/BV1Y441157H7
[3]漫画:什么是动态规划?(整合版) https://www.sohu.com/a/149075950_684445

今天的文章动态规划求最短路径实验报告_单源最短路径dijkstra算法「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/86247.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注