牛博网站建设更新网站的方法

牛博网站建设,更新网站的方法,酷我音乐网站架构,设计与绘制一个网站首页文章目录#x1f4cb; 题目#x1f511; 一、理解关键概念1.1 d(v) 是什么#xff1f;1.2 π(v) 是什么#xff1f;#x1f4ca; 二、新的例题#x1f3af; 三、关键问题解答Q1#xff1a;d(V)更新的逻辑是什么#xff1f;Q2#xff1a;为什么选择某个点#xff1f;Q…文章目录 题目 一、理解关键概念1.1 d(v) 是什么1.2 π(v) 是什么 二、新的例题 三、关键问题解答Q1d(V)更新的逻辑是什么Q2为什么选择某个点Q4π值什么时候改变 四、总结核心概念算法流程关键理解 题目 一、理解关键概念1.1 d(v) 是什么d(v) 的含义当前已知的从顶点v到已连通区域的最短距离如果v已经在连通区域中d(v) 0如果v还没连通d(v) 从v到连通区域的某条边的最小权重通俗理解就像从村庄v到已修路区域最便宜的路要花多少钱初始时除了起始点其他点的d值都是∞无穷大1.2 π(v) 是什么π(v) 的含义父节点在已连通区域中哪个顶点通过权重为d(v)的边连接到v如果v已经在连通区域中π(v) nil没有父节点或者是起始点通俗理解就像从哪个村庄修路到v最便宜如果d(v) 4, π(v) a意思是从a修路到v成本是4关键关系边 (π(v), v) 的权重 d(v)这条边就是当前已知的连接v到连通区域的最便宜的路 二、新的例题 三、关键问题解答Q1d(V)更新的逻辑是什么更新规则对于新加入连通区域的顶点u检查它的每个邻居v如果 v 还没连通v不在连通区域中 如果 w(u,v) d(v) 更新d(v) w(u,v) 更新π(v) u通俗理解“如果从u到v的路比v当前已知的最便宜的路更便宜”“就更新v的距离和父节点”例子步骤©中更新d选择e后检查e → dd当前d(d) 5从a到de → d权重4因为4 5所以更新d(d) 4π(d) eQ2为什么选择某个点选择规则从所有未连通的顶点中选择d值最小的为什么这样选择贪心思想d值最小 连接到连通区域最便宜每次选择最便宜的保证总成本最小证明思路简化假设存在更优的方案不选择d值最小的点那么必然存在一条更便宜的路但我们选择的是d值最小的矛盾所以选择d值最小的是最优的例子步骤c中选择e未连通顶点{b, c, d, e, f}d值b4, c∞, d5, e2, f6e的d值最小2所以选择eQ4π值什么时候改变π值改变的条件初始时所有顶点的π nil第一次发现路径当某个顶点v第一次被发现可以连接到连通区域时例如步骤(b)中b第一次被发现π(b) a发现更便宜的路径当发现从新顶点u到v的路比v当前已知的路更便宜时例如步骤©中发现e → d4比a → d5便宜所以π(d)从a改为eπ值不变的情况如果新发现的路径不比当前已知的路径便宜π值不变例如步骤©中e → f9不比a → f6便宜所以π(f)保持为a 四、总结核心概念d(v)从v到连通区域的最短距离当前已知的π(v)v的父节点通过权重为d(v)的边连接到v选择规则每次选择d值最小的未连通顶点更新规则如果发现更便宜的路径更新d和π值算法流程1. 初始化选择起始点ad(a)0其他d(v)∞ 2. 重复直到所有顶点连通 a. 选择d值最小的未连通顶点u b. 把u加入连通区域修路(π(u), u) c. 更新u的邻居如果发现更便宜的路径更新d和π 3. 返回MST关键理解贪心策略每次选择最便宜的得到全局最优动态更新随着连通区域扩大不断发现更便宜的路径π值记录最优路径π(v)记录当前已知的连接v到连通区域的最便宜的方式记忆要点d值记录距离π值记录父节点选择最小d值更新更便宜路径