首页 > 编程语言 >代码随想录算法训练营第64天 | 图论:Floyd 算法+A * 算法

代码随想录算法训练营第64天 | 图论:Floyd 算法+A * 算法

时间:2024-08-08 18:16:12浏览次数:11  
标签:遍历 int 随想录 range 算法 Floyd grid 节点

97.小明逛公园
https://kamacoder.com/problempage.php?pid=1155
Floyd 算法精讲
https://www.programmercarl.com/kamacoder/0097.小明逛公园.html#floyd-算法精讲

Floyd 算法精讲

  • 问题总结:双向道路;路径规划;多个起点到多个终点

  • 核心思想:动态规划

    • 确定dp数组和下标含义:grid[i][j][k] = m 含义:节点i到节点j以【1...k】集合为中间节点的最短距离为m k是集合
    • 确定递推公式:
      1. 节点i->节点j最短路径经过节点k:
        grid[i][j][k] = grid[i][k][k-1]+grid[k][j][k-1]
      2. 节点i->节点j最短路径不经过节点k
        grid[i][j][k] = grid[i][j][k-1]
      3. 最终递推式为:
        grid[i][j][k] = min(grid[i][k][k-1]+grid[k][j][k-1],grid[i][j][k-1])
    • dp数组初始化
      grid[i][j][0]:节点0无意义;从节点0开始初始化;

    image

    • 确定遍历顺序:从底层一层一层遍历上去;
    • 推导dp数组
    点击查看代码
    def floyd(n,grid):
    	for k in range(1,n+1):
    		for i in range(1,n+1):
    			for j in range(1,n+1):
    				grid[i][j][k] = min(grid[i][k][k-1]+grid[k][j][k-1],grid[i][j][k-1])
    	return grid
    def main():
    	max_int = 10005
    
    	n,m = map(int,input().split())
    	grid = [[[max_int]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
    
    	for _ in range(m):
    		p1,p2,w = map(int,input().split())
    		grid[p1][p2][0] = w
    		grid[p2][p1][0] = w
    
    	grid = floyd(n,grid)
    
    	q = int(input())
    	for _ in range(q):
    		start,end = map(int,input().split())
    		if grid[start][end][n]==max_int:
    			print(-1)
    		else:
    			print(grid[start][end][n])
    
    if __name__ == '__main__':
    	main()
    

Astar算法

  • 其实是BFS的变形;

  • BFS和Astar算法的动画如图:https://kamacoder.com/tools/knight.html

  • Astar遍历:
    image

  • BFS遍历:
    image

  • BFS 是没有目的性的 一圈一圈去搜索, 而 A * 是有方向性的去搜索。

  • 其关键在于 启发式函数。

  • 每个节点的权值为F,给出公式为:F = G + H

    • G:起点达到目前遍历节点的距离
    • F:目前遍历的节点到达终点的距离
  • 本题的图是无权网格状,在计算两点距离通常有如下三种计算方式:

    • 曼哈顿距离,计算方式: d = abs(x1-x2)+abs(y1-y2)
    • 欧氏距离(欧拉距离) ,计算方式:d = sqrt( (x1-x2)^2 + (y1-y2)^2
    • 切比雪夫距离,计算方式:d = max(abs(x1 - x2), abs(y1 - y2))
  • 计算出来 F 之后,按照 F 的 大小,来选去出队列的节点。可以使用 优先级队列 帮我们排好序,每次出队列,就是F最小的节点。

  • 多个目标找最近目标(特别是潜在目标数量很多的时候),可以考虑 Dijkstra ,BFS 或者 Floyd

    点击查看代码
    import heapq
    import math
    
    def heuristic(x1, y1, x2, y2):
    	# 欧式距离作为启发式函数
    	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    
    def a_star(a1,a2,b1,b2):
    	# 定义骑士的8个移动方向
    	directions = [(-2, -1), (-1, -2), (1, -2), (2, -1),
    			  (2, 1), (1, 2), (-1, 2), (-2, 1)]
    	pq = []
    	heapq.heappush(pq,(0,0,a1,a2))
    
    	visited = set()
    	while pq:
    		total_cost,curr_cost,x,y = heapq.heappop(pq)
    
    		if (x,y) == (b1,b2):
    			return curr_cost
    		if (x,y) in visited:
    			continue
    		visited.add((x,y))
    
    		for dx,dy in directions:
    			nx,ny = x+dx,y+dy
    			if 1<=nx<=1000 and 1<=ny<=1000 and (nx,ny) not in visited:
    				new_cost  = curr_cost+1
    				total_cost = new_cost+heuristic(nx,ny,b1,b2)
    				heapq.heappush(pq,(total_cost,new_cost,nx,ny))
    	return -1
    
    def main():
    	# 定义骑士的8个移动方向
    	directions = [(-2, -1), (-1, -2), (1, -2), (2, -1),
    			  (2, 1), (1, 2), (-1, 2), (-2, 1)]
    
    	n = int(input())
    	res = []
    	for _ in range(n):
    		a1,a2,b1,b2 = map(int,input().split())
    		res_i = a_star(a1,a2,b1,b2)
    		res.append(res_i)
    	for res_i in res:
    		print(res_i)
    if __name__ == '__main__':
    	main()
    

路径规划算法总结

算法 源点数 边的权值是否为负数 检测负权回路 有限节点最短路径 思路
dijkstra朴素版 单源 不可以 不可以 不可以 遍历未被访问的节点更新mindist
dijkstra堆优化版 单源 不可以 不可以 不可以 用堆栈优化
Bellman_ford 单源 可以 可以 可以 遍历边更新mindist
SPFA 单源 可以 可以 可以 只优化当前节点相连的点
Floyd 多源 可以 可以 不可以 三维动态优化

图算法总结

  1. 深搜与广搜:遍历;
  2. 并查集:判断是否相连;
  3. 最小生成树;
  4. 拓扑排序;
  5. 最短路径算法;

标签:遍历,int,随想录,range,算法,Floyd,grid,节点
From: https://www.cnblogs.com/P201821440041/p/18349493

相关文章

  • 揭秘人工智能三大基石:数据、算法与算力的深度融合
    在科技日新月异的今天,人工智能(AI)作为引领未来科技浪潮的核心力量,正以前所未有的速度改变着我们的生活、工作乃至整个社会的面貌。人工智能的快速发展并非偶然,而是建立在三大坚实基石之上:数据、算法与计算能力。这三者相辅相成,共同构筑了人工智能技术的基石,推动了AI技术的不断突破......
  • 2024-8-7 算法学习
    P6136【模板】普通平衡树(数据加强版)题意:1,插入一个数;2,删除一个数3,查询一个数的排名4,查询第x个数5,查询x的前驱和后继重点在于分裂split和合并merge操作:1:分裂为X[0,x],Y[x+1,n],后rt=merge(X,x,Y)2:分裂为X[0,x-1],Y[x,x],Z[x+1,n]后Y=merge(Y.l,Y.r),后rt=merge(X,Y,Z);3......
  • paxos算法详解
    1分布式一致性:共识算法对于一个分布式系统来说,保障集群中所有节点的数据完全相同(即一致性)是很重要的,随着多节点的引入,这影响的是整个分布式系统对外服务的表象一致性。也就是说,一个分布式系统想要做到完全的一致性,需要对外表现为顺序一致性,即各个节点上的操作顺序都一致。而在......
  • 【Python机器学习】利用AdaBoost元算法提高分类性能——基于单层决策树构建弱分类器
    单层决策树(也称决策树桩)是一种简单的决策树。它基于单个特征来做决策,由于这棵树只有一次分裂过程,因此它实际上就是一个树桩。在构造AdaBoost代码时,首先通过一个简单数据集来确保在算法上一切就绪:fromnumpyimport*defloadSimpData():datMat=matrix([[1.0,2.1],......
  • 机器学习算法之一 线性回归
    1.线性预测函数定义左侧为真实值,右侧为预测值与误差的和,其中为权重矩阵。2.目标函数的推导2.1高斯分布函数误差符合独立同分布假设,服从均值为0的高斯分布:将线性函数带入,得:......
  • 文心一言 VS 讯飞星火 VS chatgpt (320)-- 算法导论22.3 12题
    十二、证明:我们可以在无向图G上使用深度优先搜索来获得图G的连通分量,并且深度优先森林所包含的树的棵数与G的连通分量数量相同。更准确地说,请给出如何修改深度优先搜索来让其给每个结点赋予一个介于1和k之间的整数值v.cc,这里k是G的连通分量数,使得u.cc=v.cc当且仅当结点u和结......
  • 文心一言 VS 讯飞星火 VS chatgpt (319)-- 算法导论22.3 11题
    十一、请解释有向图的一个结点u怎样才能成为深度优先树中的唯一结点,即使结点u同时有入边和出边。如果要写代码,请用go语言。文心一言:在一个有向图中,如果结点u在深度优先搜索(DFS)的过程中成为深度优先树(DFS树)中的唯一结点,这通常意呀着在DFS遍历的某个特定时刻,从u出发能够探索......
  • 清晰易懂二分查找算法 你确定不看吗?
    @目录前言简介一、二分查找算法的原理是什么?1.确定搜索范围:2.计算中间位置:3.比较中间元素:4.调整搜索范围:5.重复迭代:二、二分查找算法的优缺点是什么?优点:缺点:三、java实现二分查找案例总结前言请各大网友尊重本人原创知识分享,谨记本人博客:南国以南i、提示:以下是本篇文......
  • 数组排序算法
    4.2数组排序算法4.2.1冒泡排序冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“......
  • 代码随想录day23 || 39 组合总和,40 组合总和2,131 分割回文串
    39组合总和funccombinationSum(candidates[]int,targetint)[][]int{ //思路,组合问题考虑回溯算法,考虑到元素可能重复问题,所以,树的最大深度应该是target/min(candudates)+1 varpath=[]int{} varres=[][]int{} backtracking(target,candidates,&path,&res......