第5章回溯法ppt课件.ppt

《第5章回溯法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、回溯算法（一）什么是回溯回溯回溯入口出口回溯迷宫游戏什么是回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。回溯为什么回溯？回溯(Trackback)是什么？怎样回溯？WhatWhyHow一、回溯的概念像走迷宫这样，遇到死路就回头的搜索思路就叫做“回溯”。从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。一

2、、回溯的概念回溯算法是一种有条不紊的搜索问题答案的方法，是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。一、回溯的概念回溯算法常被用来解决自然数排列问题、皇后问题、迷宫问题、数的拆分、0/1背包问题、骑士问题、货船装箱问题和图形覆盖问题等。实例—n皇后问题在一个n×n的棋盘上放置n个国际象棋中的皇后，要求所有的皇后之间都不形成攻击。请你给出所有可能的排布方案数。n45678总数21044092n皇后问题对于n皇后问题而言，我们很难找出很合适的方法来快速的得到解，因此，我们只能采取最基本的枚举法来求解。但

3、我们知道，在n×n的棋盘上放置n个棋子的所有放置方案有种，而这个数字是非常庞大的，直接枚举肯定会超时。n皇后问题考虑到皇后攻击的特性，所有的皇后不能同行、同列，那么不妨我们先人为规定第k个皇后在第k行，这样的话我们只要给出每个皇后所处的列号就可以描述皇后的位置了。如图放置方式就可以被表示为：3、1、4、2即第1个皇后在第3列，第2个皇后在第1列，……n皇后问题既然回溯算法是由一个节点开始逐步扩展的，因此我们采用把皇后一个一个的放到棋盘上的方式来分析问题。n皇后问题首先要把第一个皇后放到棋盘上由于第一个皇后有n列可以放，因此可扩展出n种情况。先选其中一列放下这个皇后

4、；然后开始放第二个皇后。同样第二个皇后也有n列可以放，因此也能扩展出n种情况，但第二个皇后可能会和第一个皇后发生攻击，而一旦发生攻击，就没有必要往下扩展第三个皇后，而如果没有发生攻击，则继续放第三个皇后；依此类推，直到n个皇后全都放下后，即得到一组可行解。扩展全部完成后即可得到结果。n皇后问题123141234123423412341234123412341234123412341234123412341234二、回溯的一般描述可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si，

5、i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且

6、Si

7、有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。二、回溯的一般描述解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，显然，其计算量是相当大的。二、回溯的一般描述对于许多问题，所给定的约束集D具有完备性。即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j

8、2，…，xj的所有约束。二、回溯的一般描述一旦某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解。三、回溯的一般步骤回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。n皇后问题的解空间就应该是1～n全排列的一部分。解空间的长度是n。解空间的组织形式是一棵n叉树，一个可行的解就是从根节点到叶子节点的一条路径。控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线。三、回溯的一般步骤开始节点既是一

9、个活节点又是一个E-节点（expansionnode、扩展节点）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。实例—跳马问题在n×m棋盘上有一中国象棋中的马：马走日字；马只能往右走。请你找出一条可行路径，使得马可以从棋盘的左下角（1，1