企业官网建设流程全解析

烟台网站建设方案报价,天津滨海新区落户政策,python怎么做专门的手机网站,微信个人公众号如何开通搜索评价一个搜索算法#xff0c;从四个维度进行——完备性、最优性、空间复杂度、时间复杂度完备性#xff1a;只要问题有解#xff0c;算法能不能一定找到#xff1f;#xff08;比如找钥匙#xff0c;能不能保证找到#xff0c;不管钥匙藏在哪#xff09;最优性从四个维度进行——完备性、最优性、空间复杂度、时间复杂度完备性只要问题有解算法能不能一定找到比如找钥匙能不能保证找到不管钥匙藏在哪最优性找到的解是不是 “最好的”比如找最短路径能不能找到距离最短 / 代价最小的时间复杂度找解要花多久用 “搜索的节点数” 衡量节点越多越慢空间复杂度找解要占多少内存用 “同时记住的节点数” 衡量记的节点越少越省内存传统基础搜索这类算法只知道 “初始状态、目标状态、能做什么动作”不知道 “当前状态离目标多远”像瞎摸一样找路。深度优先搜索DFS不具备完备性、最优性但空间复杂度良好优点空间复杂度低。只需要记当前路径上的节点不用记所有探索过的节点比如迷宫里只记 “现在在哪、走过哪些岔路”。缺点① 不完备如果迷宫有无限长的路会一直走下去永远找不到出口② 不最优可能找到一条绕远的路就停了没机会找更短的。广度优先搜索BFS具备完备性、最优性但空间复杂度很高优点① 完备性只要有出口一定能找到不会漏层② 最优性如果每步代价相同比如每段路距离一样找到的一定是最短路径步数最少。缺点空间复杂度极高要记所有已经探索过的 “层”节点多了会占满内存比如迷宫大了要记上百个岔路。改进搜索迭代深入搜索结合DFS的空间优势和BFS的时间优势先做 “深度限制为 1 的 DFS”只走 1 步就回头没找到就做 “深度限制为 2 的 DFS”依次增加深度直到找到目标。代价一致搜索Dijkstra 算法找路时不看走了多少步只看从起点到当前节点的 “总距离”总距离最小的节点先探索。比 BFS 更通用适合 “每步代价不同” 的情况如果每步代价相同代价一致就和 BFS 一样。启发式搜索——A*算法传统搜索没有考虑本身信息不会用 “当前节点离目标有多远” 就像没导航找路瞎转悠。启发式搜索会用 “导航”启发式函数效率大幅提升。A * 算法是启发式搜索的最优算法核心目标是 “在初始状态到目标状态的所有可能路径中高效找到代价最小的最优路径”。它不像盲搜BFS/DFS那样 “瞎转悠”而是通过 “已走的实际代价 到目标的估计代价” 综合判断节点优先级既保证最优性又大幅提升搜索效率相当于 “带精准导航的找路算法”。首先先由一个例子介绍一下A*算法的执行过程再证明其最优性。A*算法涉及3个函数其中最终决定下一步走哪里的是f(n)g(n)从初始节点到当前节点 n的实际代价固定值路径确定则 g (n) 唯一h(n)从当前节点 n到目标节点的估计代价启发函数决定 A * 效率与最优性f(n)从初始节点经 n 到目标的总代价估计A * 每次优先扩展 f (n) 最小的节点。算法执行过程目标从城市 Arad 到 Bucharest 的最优路线。为了实现这个目标需要维护一个优先队列该队列按节点的f值升序排列当前对头即为下一步需要处理的节点。还需要维护一个关闭列表记录已经遍历过的节点优先队列fringe存储待扩展节点按 f (n) 升序排列初始队列[Aradg0h366f0366366]关闭列表closed存储已扩展节点初始为空逻辑初始节点 Arad 无前置路径g0h366Arad 到 B 的直线距离f366 为当前唯一节点。选中节点队列中 f 最小的 Arad将其加入关闭列表closed{Arad}扩展 Arad 的 3 个邻居计算每个邻居的 g、h、fZerindZgArad 的 g7507575h374Z 到 B 的直线距离f75374449SibiuSg0140140h253S 到 B 的直线距离f140253393TimisoaraTg0118118h329T 到 B 的直线距离f118329447更新队列按 f 升序[Sibiu393、Timisoara447、Zerind449]选中节点队列中 f 最小的 Sibiu加入关闭列表closed{Arad、Sibiu}扩展 Sibiu 的 4 个邻居Arad 已在 closed跳过FagarasFg14099239h176F 到 B 的直线距离f239176415OradeaOg14092232h380O 到 B 的直线距离f232380612Rimnicu VilceaRg14080220h193R 到 B 的直线距离f220193413更新队列按 f 升序[Rimnicu Vilcea413、Fagaras415、Timisoara447、Zerind449、Oradea612]选中节点队列中 f 最小的 Rimnicu Vilcea加入关闭列表closed{Arad、Sibiu、Rimnicu Vilcea}扩展 Rimnicu Vilcea 的 3 个邻居Sibiu 已在 closed跳过PitestiPg22097317h100P 到 B 的直线距离f317100417CraiovaCg220146366h160C 到 B 的直线距离f366160526更新队列按 f 升序[Fagaras415、Pitesti417、Timisoara447、Zerind449、Craiova526、Oradea612]选中节点队列中 f 最小的 Fagaras加入关闭列表closed{Arad、Sibiu、Rimnicu Vilcea、Fagaras}扩展 Fagaras 的 2 个邻居Sibiu 已在 closed跳过BucharestBg239211450h0目标节点 h0f4500450更新队列按 f 升序[Pitesti417、Timisoara447、Zerind449、Bucharest450、Craiova526、Oradea612]关键此时 Bucharest 已加入队列但 f450 并非当前最小不选中。选中节点队列中 f 最小的 Pitesti加入关闭列表closed{Arad、Sibiu、Rimnicu Vilcea、Fagaras、Pitesti}扩展 Pitesti 的 2 个邻居Rimnicu Vilcea 已在 closed跳过BucharestBg317101418h0f4180418更新队列此时 Bucharest 有两个路径记录Fagaras→Bf450Pitesti→Bf418队列按 f 升序更新为 [Bucharest418、Timisoara447、Zerind449、Bucharest450、Craiova526、Oradea612]此时继续执行选中节点队列中 f 最小的 Bucharestf418Bucharest 是目标节点算法终止最优路径Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest总实际代价 g418。为什么A*算法得到的一定是最优解对于树搜索和图搜索来说A*算法得到最优解的条件是不太一样的树搜索的要求更低一些A * 图搜索的最优性条件启发函数 h (n) 满足 “一致性”从A*涉及到的三个函数来说很明显可以看到h(n)是其中最关键的g(n)是已知条件f(n)只是用来求和因此如何设计一个合理的h(n)是最重要的低估或者高估h(n)都会对算法的性能造成影响。因此A * 算法要保证找到最优解核心条件是启发函数 h (n) 满足 “一致性”具体如下一致性Consistency定义通俗来说就是当前节点到目标的估计代价不能比 “先到相邻节点的实际代价 相邻节点到目标的估计代价” 还大。一致性的作用保证f(n)沿路径单调不减f(n) g(n) h(n) g(n) g(n) 从n到n的实际一步代价 h(n) ≥ g(n)h(n) f(n)节点首次被扩展时g(n)已是初始到 n 的最小实际代价无需重复更新目标节点首次被扩展时其f(n)g(n)h (目标)0必为最小总代价即最优路径。注意仅满足“可采纳性”h (n)≤h*(n)h*(n) 为 n 到目标的实际最小代价不足以保证图搜索最优因可能重复扩展节点导致错过最优路径但 “一致性” 是更强的约束 ——一致的 h (n) 必可采纳可同时满足图搜索的最优性与效率。*一致性证明我认为不会考即证明保证f(n)沿路径单调不减: f(n) f(n)符号定义与推导如下不再过多赘述:f(n) g(n) h(n) g(n) g(n) 从n到n的实际一步代价 h(n) ≥ g(n)h(n) f(n)证明树搜索 A * 算法在 h (n) 可采纳时最优证明该问题前需要由如下概念引入可采纳性启发函数h(n) ≤ h*(n)其中h*(n)是节点 n 到目标节点的实际最小代价即 n 到目标的最短路径代价。最优路径代价设C*为初始节点到目标节点的实际最小总代价G*为最优目标节点即沿最优路径到达的目标节点其g(G*)C*。子最优目标节点设G2为任意非最优的目标节点即沿非最优路径到达的目标节点其g(G2) C*即路径代价大于最优值。f (n) 的定义f(n) g(n) h(n)其中g(n)是初始节点到 n 的实际路径代价。A*算法会根据f(n)的值来选择下一个节点我们需要证明当 h (n) 可采纳时树搜索的 A*会优先扩展最优路径上的节点最终找到最优目标节点 G而非次最优节点 G2。即f(n) f(G2)恒成立。步骤 1最优路径上始终存在未扩展节点初始时初始节点在最优路径上且是未扩展节点。假设某一时刻最优路径上的节点n被 A * 扩展由于树搜索的后继函数会生成n的相邻节点其中必有一个节点n仍在最优路径上否则该路径不是最优因此n会被加入待扩展队列成为新的未扩展节点。结论在 A * 终止前最优路径上必然存在至少一个未扩展节点。步骤 2最优路径上未扩展节点的 f (n) ≤ C*设n是最优路径上的任意未扩展节点需证明f(n) ≤ C*由于n在最优路径上g(n)是初始节点到 n 的实际代价而g*(n)是初始到 n 的实际最小代价因 n 在最优路径上故g(n)g*(n)。由 h (n) 的可采纳性h(n) ≤ h*(n)h*(n)是n到 G * 的实际最小代价。因此f(n)g(n)h(n)g∗(n)h(n)≤g∗(n)h∗(n)而g*(n) h*(n)正是初始节点经 n 到 G * 的实际最小总代价即C*最优路径代价。结论f(n) ≤ C*。步骤 3次最优目标节点的 f (G2) C*设G2是任意次最优目标节点g(G2) C*需证明f(G2) C*目标节点的h(G2)0已到达目标无需再估计代价因此f(G2)g(G2)h(G2)g(G2)由于G2是次最优节点g(G2) C*因此f(G2)g(G2)C∗步骤 4A会优先扩展最优路径的节点最终找到 GA * 的扩展规则是每次选择待扩展队列中 f (n) 最小的节点。结合步骤 2 和步骤 3 的结论最优路径上未扩展节点的f(n) ≤ C*子最优目标节点的f(G2) C*。因此次最优目标节点 G2 的 f 值必然大于最优路径上未扩展节点的 f 值。这意味着A * 会优先扩展最优路径上的节点而不会先扩展子最优节点 G2。随着最优路径上的节点不断被扩展最终会扩展到最优目标节点 G*此时f(G*) g(G*) h(G*) C* 0 C*是当前最小的 f 值算法终止。例如PPT中的例子最优目标节点 G 指 “通过最优路径到达的 Bucharest”次最优节点 G2 指 “通过非最优路径到达的同一个 Bucharest”最优路径Arad→Sibiu→Rimnicu Vilcea→Pitesti→BucharestC*418。最优路径上的节点Sibiug(Sibiu)140h(Sibiu)253可采纳因253 ≤ 实际到Bucharest的代价故f(Sibiu)140253393 ≤ 418。子最优路径如Arad→Timisoara→Lugoj→Mehadia→Drobeta→Craiova→Pitesti→Bucharest其目标节点的g(G2) 418故f(G2) 418。A * 会优先扩展f393的Sibiu而非f418的子最优节点最终找到最优路径。局部搜索局部搜索不关心从初始状态到目标的 “路径”只关心 “找到最好的状态”1. 爬山搜索“贪心爬楼梯”通俗理解从当前状态出发选 “最好的邻居状态”比如 8 拼图中离目标布局更近的一直往上爬直到 “没有更好的邻居”到顶了。优点简单、省内存。缺点容易困在 “局部最高点”比如爬了个小土坡以为是山顶其实旁边有更高的山不完备、不最优。2. 模拟退火“允许偶尔下坡的爬山法”通俗理解像金属退火时 “先高温软化再低温定型”搜索初期允许 “选差一点的邻居”下坡避免困在局部最高点后期慢慢不允许下坡专注找全局最优。优点比爬山法更容易找到全局最优。例子找函数最大值爬山法可能卡在小山峰模拟退火会偶尔 “往下走一步”再找到更高的山峰。3. 遗传算法“模拟生物进化”通俗理解把每个 “状态” 看成 “生物个体”比如 8 皇后的布局是一个个体多个个体组成 “种群”。通过 “繁殖交叉、变异” 产生新一代个体再留下 “适应度高”比如不冲突的皇后对多的个体逐代进化直到找到最优个体。核心步骤编码把状态变成 “染色体”比如 8 皇后用 8 位数字表示每列皇后的行号。适应度函数判断个体好不好比如 8 皇后中不冲突的皇后对数量。遗传操作交叉两个优秀个体交换部分 “基因”比如两个布局交换后 4 列的皇后位置。变异偶尔改变一个 “基因”比如随机改一列皇后的行号。优点适合复杂的优化问题比如卫星天线设计、高铁车头形状优化能找到全局最优。所有搜索算法核心对比表例题w 0f(n) 2 * g(n) 此时相当于只关注当下w 2f(n) 2 * h(n) 此时相当于只关注目标。1、可采纳admissible小于等于即B到G的最短路程2、一致consistent当前节点到目标的估计代价不能比 “先到相邻节点的实际代价 相邻节点到目标的估计代价” 还大。3、