dw怎么做秋季运动会网站,中信建设有限责任公司营业执照,wordpress生成卡密,贵阳网站建设设计公司哪家好文章目录 回溯法迷宫游戏 N皇后问题基本概念解空间4后问题的解空间 可行解和最优解回溯法回溯法术语回溯法的关键问题回溯法的基本思想4后问题的约束条件n后问题生成问题状态的基本方法 子集和问题一个朴素的求解方法回溯回溯法的剪枝技术 地图填色问题 回溯法
迷宫游戏 深度优… 文章目录 回溯法迷宫游戏 N皇后问题基本概念解空间4后问题的解空间 可行解和最优解回溯法回溯法术语回溯法的关键问题回溯法的基本思想4后问题的约束条件n后问题生成问题状态的基本方法 子集和问题一个朴素的求解方法回溯回溯法的剪枝技术 地图填色问题 回溯法
迷宫游戏 深度优先遍历。某一条线路卡死了就回溯回来。
这种回溯思想和一个完全蛮力的蛮力法相比它的好处
1不用遍历所有的路线
2不用每次都从起点开始。 它只是回溯到分叉点的地方再去选另一条路走而不是每次都从迷宫起点开始。 不过说白了回溯法其实就是蛮力法的一种说白了回溯法也就是个蛮力法。 主要思想 用于发现所有或者部分解的一种通用策略逐步构建部分备选解partial candidates to the solutions如果备选解不能成为一个有效的解则立即放弃该分支 求可行解问题 八皇后问题子集和问题 求最优解问题 0/1背包问题 回溯法只能用于问题可以分解为部分备选解partial candidate solutions并可以快速检验部分备选解是否能够成为一个有效的解。 如果可行回溯法一般比蛮力法要快得多因为回溯法可以排除一群备选解。
N皇后问题 皇后指的就是国际象棋里面那个叫皇后的棋子。 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后任何2个皇后不放在同一行或同一列或同一斜线上。n1显而易见。n2、3问题无解。n4时问题才有意义。
以4后为例 蛮力法 把所有的情况全部列出来。 比如第一个皇后放在第一行第一列那么第二个皇后能够放在哪些位置、第三个皇后继而能够放在哪些位置、第四个皇后继而能够放在哪些位置。 第一个皇后放在第一行第二列时第二、三、四个……放在什么位置。 感觉没说太清楚但是就是这个意思通过蛮力法求出所有可能的摆放情况。 总之可见n比较小的时候也许蛮力法还可以比如七八个皇后蛮力法勉强也行。但是数量大了以后就很困难了。 4皇后问题采用回溯法求解过程图示 采用深度优先遍历DFS。 你如果要说BFS行不行也没啥问题只不过是另一种方式了 啥意思呢比如 第一行在第一列摆一个皇后。 那么第二行的那个皇后总共有4种摆法分别为1、2、3、4。 第二行摆在1——不可行回退。 第二行摆在2——不可行回退。 第二行摆在3——可行进一步讨论 ——第三行摆在1不可行回退 ——第三行摆在2不可行回退 ——第三行摆在3不可行回退 ——第三行摆在4不可行回退 第二行摆在4——可行进一步讨论 ——第三行摆在1不可行回退 ——第三行摆在2可行进一步讨论 ————第四行摆在1不可行回退 ————第四行摆在2不可行回退 ————第四行摆在3不可行回退 ————第四行摆在4不可行回退。 ——第三行摆在3不可行回退 ——第三行摆在4不可行回退 至此对于第一行摆在第一位的所有“进一步讨论”的结果均无法得到最终可行方案均回退。 所以之后又该讨论“第二行摆在位置2”下面所有的可能情况同理可行的就进一步讨论不可行的就排除并回退。 这个问题和走迷宫本质是同样的走不通就回退并排除最终找到一个可行的解。 可见它其实也是在蛮力。只不过它和蛮力还是有区别的 什么是蛮力法就是我即使这个方法已经不可行了但是我还是要把它下面所有的分支遍历一遍并且讨论一下。 回溯法是当我这里不可行了它下面的是什么东西我根本就不去看它了。 所以回溯法其实就是一种蛮力法而不是什么高级的办法。只不过是说回溯法当我发现这个情况不可行了那我在它后续的所有结点就不需要去找了。 回溯法就是一种“剪枝”的蛮力法。而纯粹的蛮力法是不剪枝的。 思路大致明白了再思考一些问题
问题
1、解怎么表示
2、解如何组织
3、怎么找到最优解 除了找到的这1个解还有没有其他解——肯定有。因为“对称”的情况和它是一样的肯定也是它的解。 而我只搜索到一个解就结束了。后面不管还有没有其他的解都不看了。 如果找到一个可行解之后还想找其他的解。 继续使用回溯法查找就可以得到问题的其他解。 n皇后问题——n-Queens Problem
在做4皇后问题时有没有什么办法可以优化一下问题搜索呢 刚才也说了找到一个可行解之后我们最起码可以用“对称性”再找另外几个解出来。 基本概念
解空间可能解可行解最优解
解空间
问题的解向量 X ( x 0 , x 1 , . . . , x n − 1 ) X(x_0,x_1,...,x_{n-1}) X(x0,x1,...,xn−1)——解的表达形式。 x i x_i xi的取值范围 S i S_i Si S i { a i . 0 , a i . 1 , . . . , a i , m i } S_i\{a_{i.0},a_{i.1},...,a_{i,m_i}\} Si{ai.0,ai.1,...,ai,mi}。问题的解空间由笛卡尔积 A S 0 × S 1 × . . . × S n − 1 AS_0×S_1×...×S_{n-1} AS0×S1×...×Sn−1构成。
4后问题的解空间
例如4皇后问题 解向量 x ( x 1 , x 2 , x 3 , x 4 ) x(x_1,x_2,x_3,x_4) x(x1,x2,x3,x4)4维的向量。 x i x_i xi表示第 i i i行皇后的列位置取值范围 S i { 1 , 2 , 3 , 4 } S_i\{1,2,3,4\} Si{1,2,3,4}。 解空间——4维向量的全部组合。 可行解和最优解
可行解满足约束条件的解解空间中的一个子集。 区分“可能解”与“可行解”。 最优解使目标函数取极值极大或极小的可行解一个或少数几个。 达到“最优”时的可行解。可能有1个也可能有少数的几个。 找可行解一般找到就可以但是找最优解一般要遍历整棵树。 打个比方比如一个男的要找个女朋友。 解空间所有女的。男的就不在我解空间里面了 可能解所有女的里面哪些跟我是有可能成功的。比如那些已婚的就不是可能解 可行解有一些条件比如年龄之类的——满足约束条件的解。虽然可能但是得符合我规定的一些条件 最优解能够让一些条件达到极值此时就是最优解。 实际上由此可见在“可行解”和“最优解”之间还会有一种“满意解”。 最优解可能不是那么好找但是光是可行解还感觉不够可以找一个满意解尽量能贴近最优解我就比较满足了。 回溯法 有“通用解题法”之称将所有的解问题的解空间按照一定结构排列再进行搜索。
一般解空间构造成树状结构用深度优先的策略搜索。两种方式 只需要一个解的话找到解就停止。需要求所有解则需做“树的遍历”找到所有解。 通常用排除法剪枝减少搜索空间。 如果不考虑最后一条不剪枝它就是纯蛮力法了。 给定问题有一个约束集合以及目标函数。 可以用状态空间树state space tree来表示解空间。 状态空间树的根代表了0个选择的状态。深度为1的节点代表第1次选择后的状态。深度为2的节点代表第2次选择后的状态。……状态空间树上一条从根到叶子的路径代表了备选解。 可行问题Feasibility problem一些选择可以到达可行的解一些选择不能达到可行解。 回溯法术语
树由节点组成 有三种节点 回溯法就是搜索树中某个特定目标节点。 一些特征
树中每个非叶子结点都是一个或是多个其他结点的父结点。树中结点除了根结点都只有一个父结点。
回溯法的关键问题
结点的含义是什么根据问题确定结点在树中的关系是什么根据问题确定如何产生新的结点树的遍历算法如何判断结点是否是所求解 这四点实际上不仅仅是回溯法的关键它其实也是蛮力法的关键。 当然回溯法实际上还有个第五点剪枝。 回溯法的基本思想
针对所给问题定义问题的解空间。定义结点确定易于搜索的解空间结构。定义结点关系以深度优先方式搜索解空间产生新结点并在搜索过程中用剪枝函数避免无效搜索尽量少产生新结点。
常用剪枝函数用约束函数在扩展结点处剪去不满足约束的子树。 4后问题的约束条件 4后问题状态空间树4叉完全树 约束方程 1 ≤ i ≤ 4 1 ≤ j ≤ 4 i ≠ j 1≤i≤41≤j≤4i≠j 1≤i≤41≤j≤4ij 不在同一列第i行皇后列位置与第j行皇后列位置不同即 x i ≠ x j x_i≠x_j xixj。 不在同一个斜线上 ∣ x i − x j ∣ ≠ ∣ i − j ∣ |x_i-x_j|≠|i-j| ∣xi−xj∣∣i−j∣。
则求解过程
向量 x ( x 1 , x 2 , x 3 , x 4 ) x(x_1,x_2,x_3,x_4) x(x1,x2,x3,x4)表示皇后的布局。分量 x i x_i xi表示第i行皇后的列位置。 x i x_i xi的取值范围 S i { 1 , 2 , 3 , 4 } S_i\{1,2,3,4\} Si{1,2,3,4} n后问题
解向量 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1,x2,...,xn)显约束 x i 1 , 2 , . . . , n x_i1,2,...,n xi1,2,...,n隐约束 不同列 x i ≠ x j x_i≠x_j xixj不处于同一正、反对角线 ∣ i − j ∣ ≠ ∣ x i − x j ∣ |i-j|≠|x_i-x_j| ∣i−j∣∣xi−xj∣
bool Queen::Place(int k) { //检查前k行是否合法for(int j1; jk; j) {if( abs(k-j)abs(x[j]-x[k]) || (x[j]x[k]) )return false;}return true;
}void Queen::Backtrack(int t) { //对第t行放置皇后if(tn) //当层数大于n时说明前n行都放好了。可行解的个数1sum;else {for(int i1; in; i) {x[t] i;if(Place(t))Backtrack(t1); //如果可以放置继续找下一行位置}}
}这样一个递归地遍历的过程实际上就是一个深度优先的遍历。
生成问题状态的基本方法
扩展结点一个正在产生儿子的结点称为扩展结点。活结点一个自身已生成但其儿子还没有全部生成的结点称作活结点。死结点一个所有儿子已经产生的结点称作死结点。深度优先的问题状态生成法如果对一个扩展结点R一旦产生了它的一个儿子C就把C当做新的扩展结点。在完成对子树C以C为根的子树的穷尽搜索之后将R重新变成扩展结点继续生成R的下一个儿子如果存在。宽度优先的问题状态生成法在一个扩展结点变成死结点之前它一直是扩展结点。回溯法为了避免生成那些不可能产生最佳解的问题状态要不断地利用限界函数bounding function来处死那些实际上不可能产生所需解的活结点以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。
子集和问题
问题给定n个正整数 w 1 , . . . w n w_1,...w_n w1,...wn集合一个正整数 S S S找到所有子集使其和等于 S S S。 举例 n 3 , w 1 2 , w 2 4 , w 3 6 , S 6 n3,w_12,w_24,w_36,S6 n3,w12,w24,w36,S6. 解 { 2 , 4 } a n d { 6 } \{2,4\}and\{6\} {2,4}and{6} 蛮力法找出集合所有的子集合。——时间复杂度 O ( 2 n ) O(2^n) O(2n)因此问题规模很大时不适用。
为了更好解决问题利用回溯法。 向量 x ( x 1 , x 2 , . . . , x n ) x(x_1,x_2,...,x_n) x(x1,x2,...,xn)表示节点每个 x i x_i xi的取值范围 { 0 , 1 } \{0,1\} {0,1}。使用二叉状态空间树binary state space tree进行回溯 深度为0的根结点表示0个元素的集合的和深度为1的结点是包括元素1或者不包括元素1对每个深度为 i − 1 i-1 i−1的结点左分支包括 w i ( ′ y e s ′ ) w_i(yes) wi(′yes′)右分支包括 w i ( ′ n o ′ ) w_i(no) wi(′no′)。 每个结点赋予一个值表示当前求和大小。 但是至此这说的还是纯粹的穷举法啊。 一个朴素的求解方法 构造二叉状态空间树 检查每个叶子结点该结点的值是否是 S S S如果是返回从根到叶子结点的路径。 检查可以在构造树的时候进行也可以在树构造好之后进行。 问既然可以在构造树的时候进行那为什么还要在树构造好之后进行答也许我们想求得对于 S S S不同的子集。 要找到所有的解我们要用一种方法来系统地遍历整个树。 注意叶子结点之间没有指针相连。 我们先对这些正整数做一个排序这样对我们之后的工作有好处。
把整个树已经构建出来了这个就是我们的状态空间树。
接下来我们对这棵树做深度优先搜索。 深度优先搜索
使用深度优先搜索Depth First SearchDFS以找到所有的正确的解。DFS 开始从根搜索。搜索从最近访问的结点v到下一个新的结点 如果该结点的左子结点还没有被访问访问该左子结点否则如果该结点的右子结点还没有被访问访问该右子结点否则如果v是叶子结点或者v的所有子树都已经被访问返回v的父结点 直到所有结点都被访问。 深度优先搜索的算法此处就不展开讲了应该是会的。 DFS(v)if v NILreturnexplore(v)DFS(left(v))DFS(right(v))初始调用 D F S ( T . r o o t ) DFS(T.root) DFS(T.root)。 那好我对这棵树做深度优先搜索我找到为6的结点了那这个结点再往下的任何子结点我都不需要再去看了。 然后继续深度优先遍历其余的地方一直找找找……。后面的遍历过程中可能又找到了一个为6的结点。 **注意**这里就体现刚才所说的检查每个叶子结点该结点的值是否是 S S S如果是返回从根到叶子结点的路径。**检查可以在构造树的时候进行也可以在树构造好之后进行。**这个道理了。 如果你是在构建树的过程中检查就会导致我构建的过程中构建了一个6出来我就结束了其他的我全都不管了。 而如果我是在构造完毕整个树之后才去做深度优先进行检查就能找到所有的情况了。 用DFS找到子集和问题的所有解 在DFS中检查结点v是否是叶子结点如果是叶子结点检查当前和是否是S 问题非常慢 有n个输入项的树有 2 n 2^n 2n叶子结点。 比如上面那个例子 我每次判断sum S若符合则继续向下面去深度遍历否则就不必继续。 但即使这样我仍旧会有大量的路要走所花费的代价还是很高。 这个时候我们就运用我们的回溯法加速它。
回溯 用回溯法加速DFS算法以避免访问没有希望的结点。 如果该结点不能产生一个可行解那么该结点是没有希望的non-promising。否则该结点就是有希望的promising。 主要思路 在状态空间树上做深度优先搜索检查该结点是否是有希望的如果该结点是没有希望的返回其父结点 包含被访问结点的子树被称为被剪枝状态空间树pruned state space tree。
回溯法的剪枝技术 因为我们可供选择的数字是经过递增排序过了的。 所以对于第四层的12来说它再往下不可能加出13来它就是没有希望的。其他结点同理。 Checknode(v) //v is a nodeif(promising(v))if(aSolutionAt(v))output the solutionelse //expand the nodefor each child u of vChecknode(u)promising(v)检查v代表的部分解是否还有可能产生有效的解。aSolutionAt(v)检查v代表的部分解是否解决了问题。 那具体到底是如何判断有没有希望的 地图填色问题 我们要想办法让这个树的规模变小提高效率。
