私人建设网站,好业宝微商城,技术优化seo,个人网站 logo 版权 备案 没用深度优先算法#xff08;Depth-First Search, DFS#xff09;
深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点#xff0c;尽可能深地搜索树的分支。当节点v的所在边都已被探寻过#xff0c;搜索将回溯到发现节点v的那条边的起始节点。这一过程…深度优先算法Depth-First Search, DFS
深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点尽可能深地搜索树的分支。当节点v的所在边都已被探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程直到所有节点都被访问为止。深度优先搜索是一个递归算法它利用了后进先出的栈结构在图的遍历中特别有效。
特点与应用
内存消耗较小由于只需存储一条从根节点到当前节点的路径。 找到解后停止在搜索到解后可以立即停止不需要遍历整个图。 可能陷入死循环在遍历图时如果不记录已经访问过的节点可能会陷入无限循环的情况。 不保证最短路径深度优先搜索不保证找到的路径是最短的。 应用场景如解决迷宫问题、排列组合问题、拓扑排序、解决连通性问题等。
在栈内完成先进后出探索完的节点入栈当完成这一次的探索重新进入到这个节点时出栈再次探索另一个节点时再次入栈
广度优先算法Breadth-First Search, BFS
广度优先搜索是最简便的图的搜索算法之一属于盲目搜寻法目的是系统地展开并检查图中的所有节点以找寻结果。它从图的某个顶点V0开始依次访问V0的各个未被访问过的邻接点然后从这些邻接点出发再依次访问它们的未被访问过的邻接点直到图中所有已被访问过的顶点的邻接点都被访问到。这一过程类似于树的按层次遍历。
特点与应用
找到最短路径在无权图中广度优先搜索可以保证找到从源点到目标点的最短路径。 遍历顺序确定按层次依次访问各层访问顺序是唯一的。 应用场景如编写国际跳棋AI、计算最少编辑多少个地方就可将错拼的单词改成正确的单词、根据你的人际关系网络找到关系最近的医生等。
先进先出访问的节点完全展开访问后出队以此展开后边的节点已经访问的节点不再继续访问
Hill Climbing爬山算法
爬山算法是一种局部择优的方法属于启发式搜索算法。它从当前的节点开始和周围的邻居节点的值进行比较如果当前节点不是最大的就用最高的邻居节点来替换当前节点从而实现向“山峰”的高处攀爬的目的。如此循环直到达到最高点。
特点
局部最优容易陷入局部最优解而非全局最优解。 避免遍历通过启发选择部分节点提高搜索效率。 应用场景适用于对最优解要求不是非常严格且搜索空间不是很大的情况。
贪心搜索Greedy Search
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法策略。它不保证会得到最优解但在某些问题中贪心算法的解足够接近最优解或者确实是最优解。
特点
简单直观通常直接且易于实现。 效率高在很多情况下贪心算法的运行时间较短。 无记忆每次选择都是独立的不依赖于之前的状态。 不保证最优解在某些问题中贪心选择可能导致非最优的全局解。
背包问题
A*算法
A算法是一种启发式搜索算法它结合了最佳优先搜索和Dijkstra算法的特点。A算法通过维护一个优先队列通常是最小堆并根据启发式函数如g(n) h(n)其中g(n)是从起点到当前点的实际距离h(n)是从当前点到目标点的估计距离来评估节点的优先级。A*算法能够找到从起点到终点的最短路径并且比纯粹的启发式搜索算法如爬山算法更加可靠和高效。
特点
找到最短路径在多数情况下A*算法能够找到从起点到终点的最短路径。 启发式搜索利用启发式函数来评估节点的优先级提高搜索效率。 应用场景如路径规划、游戏AI、图形学中的光照计算等。 启发式搜索算法Heuristic Search Algorithm 是一种利用启发性信息来指导搜索过程的算法。这种启发性信息通常是有利于尽快找到问题解的有价值信息能够显著减少搜索空间的大小提高搜索效率。
启发式搜索算法的基本特点
启发性信息启发式搜索算法利用启发性信息来评估搜索过程中每个节点的价值从而决定搜索的方向和顺序。这种信息可以是节点与目标节点之间的估计距离、代价或其他相关指标。 节点选择在启发式搜索中节点的选择不是盲目的而是基于启发性信息进行的。算法会优先扩展那些看起来更有可能通向目标节点的节点。 效率提升由于利用了启发性信息启发式搜索算法能够省略大量无用的搜索路径从而显著提高搜索效率。
与一般搜索算法的区别
搜索策略 一般搜索算法如深度优先搜索、广度优先搜索等通常采用确定性的搜索策略即按照固定的规则如先深后广或先广后深进行搜索。 启发式搜索算法则采用启发式的搜索策略即根据启发性信息来指导搜索过程使搜索更加灵活和高效。 节点评估 一般搜索算法在搜索过程中通常不对节点进行特别的评估只是简单地按照搜索策略进行遍历。 启发式搜索算法则会对每个节点进行评估并根据评估结果来决定节点的扩展顺序和搜索方向。 搜索效率 一般搜索算法在搜索空间较大时可能会遇到搜索效率低下的问题因为它们可能会遍历大量无用的节点。 启发式搜索算法由于利用了启发性信息来指导搜索过程因此能够显著减少搜索空间的大小提高搜索效率。 结果质量 一般搜索算法在找到解时通常无法保证解的质量如是否最优因为它们只是按照固定的规则进行搜索。 启发式搜索算法虽然也无法保证总是找到最优解这取决于启发性信息的准确性和问题的复杂度但在很多情况下能够找到接近最优的解或高质量的解。 适用性 一般搜索算法适用于搜索空间较小或问题结构较简单的情况。 启发式搜索算法则更适用于搜索空间较大、问题结构较复杂或需要快速找到高质量解的情况。 综上所述启发式搜索算法通过利用启发性信息来指导搜索过程显著提高了搜索效率和质量是现代优化算法和人工智能领域中的重要工具之一。
