做网站需要专业,品牌网站建设小8a蝌蚪,做网站做手机app要学什么软件,厦门网站建设公司哪家好目录 一、穷举搜索二、图的遍历算法#xff08;一#xff09;深度优先搜索#xff08;DFS#xff09;#xff08;二#xff09;广度优先搜索#xff08;BFS#xff09; 三、回溯法#xff08;一#xff09;回溯法的定义#xff08;二#xff09;回溯法的应用 四、分… 目录 一、穷举搜索二、图的遍历算法一深度优先搜索DFS二广度优先搜索BFS 三、回溯法一回溯法的定义二回溯法的应用 四、分支限界法一 上界与下界二 分支限界法的定义三分支限界法的应用 五、回溯法与分支限界法的对比 一、穷举搜索
穷举搜索法也被称为穷举法其基本思想是将问题的所有的候选解都枚举出来然后对候选解按照某种顺序进行逐一枚举和检验并从中找出符合问题要求的候选解作为问题的解。其优点是实现简单且易于理解适合规模较小的问题但当问题的规模较大时由于需要运行问题所有的候选解消耗大量的时间从而导致算法的效率大大降低。
二、图的遍历算法
图的遍历算法适合无向图和有向图有两种方法可分为深度优先搜索DFS和广度优先搜索BFS。
一深度优先搜索DFS
深度优先搜索的定义 简单地说图的深度优先搜索可概括为尽可能深地去搜索一个图是一个递归的过程需要用到栈存储通过遍历邻接表或邻接矩阵的方式深入搜索一个图直到访问完所有连通的顶点若当前分支已经访问过则会回溯到上一个顶点继续搜索其他分支顶点直到所有顶点被访问。
递归这一点就类似树的先序遍历先访问结点然后递归向外层结点遍历尽可能深地搜索一个图都采用回溯算法。 图的深度优先搜索首先选取图中某一顶点vi访问后任意选取一个与vi邻接的顶点且该顶点未被访问……继续重复该过程直到图中所有与vi连通的顶点都被访问到若还有顶点未被访问到则另外选取一个未被访问的顶点再次作为起始点重复以上步骤继续直至图中所有结点被访问。 例如对下面这个图以顶点a为源点对该图进行深度优先遍历求其一个遍历序列 首先选择与a邻接的任一顶点由于与a邻接的顶点有bce可有以下三种访问序列{ab……}或{ac……}或{ae……}如下 然后选择访问顶点d也可以选择还未被访问的顶点。由于先前选择访问的序列是{ad}此时访问与顶点d相邻的顶点f得到序列{adf}再访问与顶点f相邻的顶点c得到序列{adfc}由于此时与c邻接的顶点a和f都被访问过回退到f继续检查d与d邻接的顶点也被访问过……最后直到顶点d还未被访问访问它可得到一个序列{aedfcb}。【序列不唯一】 可看出aedfc这段部分是该图中尽可能深地去搜索一个图的明显体现。 深度优先搜索的空间复杂度和时间复杂度 对于一个图GVE由顶点集V和边集E组成。 1、空间复杂度
由于DFS算法是一个递归算法即递归遍历顶点集V所以通过DFS遍历的空间复杂度为O(|V|)。
2、时间复杂度
时间复杂度取决于图的存储结构若通过邻接矩阵表示图则查找顶点的邻接顶点所需时间为O(|V|)总时间复杂度为O(|V2|)邻接矩阵为方阵n×n若通过邻接表表示图则查找所有顶点的邻接顶点所需时间为O(|E|)访问顶点所需时间为O(|V|)即总时间复杂度为O(|V||E|)。
二广度优先搜索BFS
广度优先搜索的定义 广度优先搜索是通过队列来存储顶点实现遍历队列用于避免重复访问存放已经访问过的各邻接顶点可以采用邻接表或邻接矩阵搜索首先从起始点开始访问将其邻接顶点依次入队直到队列为空从而访问到所有的顶点即逐层遍历所有的顶点直到遍历完所有节点
逐层遍历这一点就类似树的层序遍历一层一层向外遍历。 图的广度优先搜索中首先选取一个起始点顶点vi访问后将其入队并标记为已访问当队列不为空时检查出队顶点的所有邻接顶点访问未被访问的邻接顶点并将其入队……继续重复该过程直到图中所有与vi连通的顶点都被访问到当队列为空时跳出循环则此时遍历完成。 例如如下所示的图从顶点1开始求一个广度优先搜索遍历序列 首先选择与顶点1邻接的所有顶点进行访问有2和3可得序列{123}或{132}然后再访问与2和3邻接的其他顶点直到所有顶点被访问。例如访问顶点2和3后访问其邻接顶点4然后再依次访问顶点4的邻接顶点5和6最后访问顶点7得到{1234567}。【序列不唯一】 广度优先搜索的空间复杂度和时间复杂度 对于一个图GVE由顶点集V和边集E组成。 1、BFS算法的空间复杂度
与深度搜索所需空间一样通过BFS遍历的空间复杂度也为O(|V|)。
2、BFS算法的时间复杂度
时间复杂度取决于图的存储结构若通过邻接矩阵表示图则查找顶点的邻接顶点所需时间为O(|V|)总时间复杂度为O(|V2|)邻接矩阵为方阵n×n这和DFS算法的时间复杂度是一样的若通过邻接表表示图则每个顶点都入队一次即所需时间为O(|V|)搜索顶点的邻接顶点所需时间为O(|E|)其时间复杂度为O(|V||E|)。
三、回溯法
一回溯法的定义
回溯法用到了上面的深度优先搜索DFS的思想首先通过穷举所有可能的解明确搜索范围从初始状态出发以深度优先搜索来搜索问题的解若当前结点不满足则会退一步回溯到上一个结点尝试其他选择直到最后找到包含问题解的结点。同样若问题规模较大时由于需要穷举所有可能的解所以此时回溯法的搜索效率较低。【找出解空间树中满足约束条件的所有解】 注递归算法与回溯法不是同一种思想回溯法是穷举解空间树来找到满足条件的解的搜索算法思想而递归是将大问题划分成小问题然后通过递归以解决小问题来实现最终问题的解运用了分治的思想。 回溯法的算法框架可分为三部分 1、针对所给问题定义问题的解空间
2、确定易于搜索的解空间组织结构
3、以深度优先搜索解空间并在搜索过程中用剪枝函数隐约束避免无效搜索。 隐约束分为两种一种是约束条件用于判断是否能得到可行解二是限界条件用于判断是否能得到最优解。所以从算法上来看回溯法是一种带有约束函数约束条件或限界函数限界条件的深度优先搜索方法。 二回溯法的应用
回溯法常用解决排列问题、组合问题、子集问题、路径问题等等。 1、组合问题组合树/满m叉树 一组元素中有若干个元素若将这些元素组合使其一起满足某种性质该问题的所有组合解空间树是一棵满m叉树或组合树。例如一个满二叉树如下m2 例如一个满m叉树的实例 对于一个有4个交通信号灯的道路每个交通信号灯有3种可能的选择红、黄、绿需要找出一种选择使得该道路满足某活动。该场景可以使用满三叉树来表示每个元素交通信号灯的选择情况在满三叉树的每个节点上有三个子节点每个子节点代表一个元素交通信号灯的选择。如果选择了其中一个元素交通信号灯则可以将其对应的子节点标记为已访问并将该节点加入到结果集中。当遍历完整个满三叉树后可以得到所有可能的交通信号灯的组合其中每个组合都满足某种性质从而找到目标性质满足该活动。
2、排列问题排列树 在若干个元素的排列中确定满足某种性质的一个排列时该问题的所有排列解空间树是一棵排列树。例如n个元素的排列数为n!n的阶乘若n3三个元素为{123}则其排列树如下 其中树的根结点为空表示初始状态。
3、子集问题子集树 在若干个元素组成的集合S确定满足某种性质的一个子集时该问题的所有子集解空间树对应一个子集树。例如0-1背包问题中所要找到满足性质的子集为该子集中物品的重量不超过背包容量且背包内总价值是最大的该问题的解空间树是一棵子集树。子集树通常有2n个叶结点其结点总个数为2(n1)-1是一棵完全二叉树。 在回溯法中解向量x1,x2,…,xn可以表示为分量取值为{0,1}的比特串解空间可以组成一颗完全二叉树这棵搜索树被称为子集树。 四、分支限界法
一 上界与下界
对于一个待求解的问题上界和下界是对问题的可能解进行限制和估计的方法从而用于解决问题。上界相当于当前最高要求指问题中的最优解不会超过某个已知值下界相当于当前最低要求指问题中的最优解不会低于某个已知值。
利用这一点可以用于剪枝搜索树的分支避免对不可能得到最优解的分支进行搜索从而缩小了搜索空间达到提高算法效率的目的。
二 分支限界法的定义
分支限界法也是一种搜索算法简单的来说分支限界法的限界就是利用上界和下界来提高搜索效率。搜索解空间树中利用上界和下界的信息来剪枝搜索树的分支舍弃导致不可行解或导致非最优解的分支。【找出解空间树中满足约束条件的一个解】
分支限界法中通常采用广度优先搜索BFS是以最大收益最小耗费的方式来搜索解空间树其步骤如下 ①首先将根结点加入活结点表然后从其中取出使其成为扩展结点 ②依次生成扩展结点的所有分支即其孩子结点 ③判断每个孩子结点。通过计算孩子结点的上界和下界并根据这些界限来决定是否继续搜索该分支若某个分支的界限满足上界小于或等于下界则可以剪掉该分支否则继续搜索该分支直到找到满足要求的解或搜索完所有分支继续通过扩展结点。
三分支限界法的应用
分支限界法的应用场景有 1、0-1背包问题 2、旅行商问题 旅行商问题指的是在一组给定的城市之间找到最短的路径使得每个城市恰好被访问一次最终回到起点。 3、集装箱装载问题 旅行商问题是一个经典的组合优化问题可以使用分支限界法进行求解。通过搜索所有可能的路径组合找到总距离最短的一条路径。 4、电路设计中的布线问题 电路设计中的布线问题可以使用分支限界法求解通过搜索所有可能的布线方式找到最优解。例如在M×N的方格中指定一个方格的中点为a另一个方格的中点为b找到a到b的最短路径布线时只能走直线或直角边。通过可以把布线的情况剪掉将能布线的方格加入活结点表扩展直到找到目标点或活结点表空为止。
五、回溯法与分支限界法的对比
回溯法的优点在于它能够找出所有可能的解而不仅仅是最优解。而若对于大型问题回溯法的效率可能较低因为它需要穷举所有可能的解分支限界法的优点在于它能够在问题规模较大时通过剪枝有效地减少搜索空间从而快速找到最优解但不能保证找到所有的可能解。
搜索算法名称回溯法分支限界法搜索解空间树方式深度优先搜索DFS广度优先搜索BFS求解解空间树目的找出满足约束条件的所有解找出满足约束条件的一个解活结点成为扩展结点一次或多次一次
回溯法的适用场景有n皇后问题、子集树0-1背包问题、最大团问题、排列树旅行商问题、批处理作业调度问题、组合树图的m着色问题等等
分支限界法的适用场景有0-1背包问题、旅行商问题、集装箱装载问题、电路设计中的布线问题等等。
