课程教学目标 针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程中加以介绍。 课程内容安排 本课程的内容分成两大部分：算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识，约占20%，主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法，主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
066回溯算法的设计思想和适用条件
Loading...
Do curso por Peking University
算法设计与分析 Design and Analysis of Algorithms
34 classificações
Na lição
回溯算法的设计思想
回溯算法是一种基本的搜索技术，通过n后放置、0-1背包、货郎旅行、图的着色等问题介绍了回溯算法的设计思想、适用条件和实现方法，并给出了估计算法运行时间的一种抽样方法。
Conheça os instrutores
Wanling QuProfessor
School of EECS, Peking University
这一讲介绍回溯算法的设计思想和适用条件。
我们先看一下上一讲的那几个例子。
一个是n皇后的问题，一个是0-1背包的问题，还有一个是货郎问题。
我们比较一下它们的共同特点。
首先解的表示，解的表示呢，它都是
可行解，最优解，最优解。
我们先分析一下上一讲的三个例子。
包括n皇后问题，0-1背包问题和货郎问题。
先看看它们要找的解是什么样的解。
n皇后问题是可行解，0-1背包问题和货郎问题都找的是最优解。
它们解的描述都是用向量描述。
n皇后问题是一个n维向量， 每一个维度代表相应的行的列号。
0-1背包问题它是一个0，1的向量， 每个向量刚好对应了一个子集。
而这个货郎问题它也是一个n维的向量， 它代表的是1到n的一种排列顺序。
这是它们解的描述，全都是向量的描述。
搜索空间都是树的结构，n皇后问题是n叉树，
0-1背包问题是子集树，货郎问题是排列树。
搜索方式可以是深度优先或者是宽度优先。
通过这样的搜索裁减掉一部分搜索空间，来加快速度。
在中间遍历的一些个结点，都要做约束条件的判定。
满足约束条件就继续向前搜索，
不满足约束条件从这个结点回溯到它的父节点，相当于以这个节点，
它为根的前面的子树就被剪裁掉了。
那么约束条件对于n皇后问题是要求彼此不攻击。
那么前面可选的列号得在这个条件满足下来进行选择。
0-1背包问题条件是不超重， 如果装了超重的话那个方向就不能选。
货郎问题要选没有经过的城市，走过的城市不能选。
所以我们看到这三个例子它的共同特点， 都是要找解。
解是一个向量表示我们是通过不断的扩张
部分的向量最后达到n，达到问题 解的这个相量要求。搜索空间都是树结构，
它的搜索方式都是跳跃式的遍历，要裁剪。
它的每一个结点要进行约束条件的判定。
看看是不是回溯，这是它的共同特点。
下边我们看一下这两种 索的方式。一个叫做深度优先，一个叫宽度优先。
我们以这棵树为例来看一看深度优先和宽度优先的区别。
所谓深度优先就是说在所有的方向里面， 我们都规定假定从最左的方向开始进行搜索。
如果能够向前走就尽量地向前走， 在前面没有方向可走的时候再回头。那么它的搜索顺序
就是由1号结点到2号结点，然后再回到1号，3号，
然后5号，8号，再回到5号，9号再回到5号，
3号，6号，回到3号，7号，回到3号再回到1号，再回到4号。
那么不同的结点的遍历顺序呐就是这个顺序， 123到5，到8，
再到9，然后再到6， 再到7，最后到4，这是深度优先的顺序。
宽度优先呐就是从每个节点先访问它第一层的儿子，
然后我们再从这些儿子，再从这个儿子再访问它的
下一层的儿子。那么
这个遍历顺序呢就是1，2，3，4，
然后2人没有儿子，不再做了，3有5，6，7访问完了。
然后再看4，4没有儿子不再做了。
然后5，5有两个儿子，8和9，所以它的遍历顺序是这个顺序。
这个叫做宽度优先，尽量向宽了走，把这个同一层的都走完了再到下一层。
所以深度优先和宽度优先是两种不同的访问顺序，
在回溯算法中都可以用到。下面我们把回溯算法的基本思想小结一下。
它适用于求解搜索问题和优化问题。
那么它的搜索空间呐都是树，
树中的结点对应了部分解向量。可行解在树叶上。
搜索过程是采用系统的方法，隐含着遍历搜索树。
所谓系统方法就是我们讲的深度优先，宽度优先，
或者还有其他的系统的方法。这个方法一定保证它所有的，
位置的结点都被看到，不一定完全访问到。
那么你裁剪的过程中呢把有些结点裁剪了，它没有完全的访问，
但是那里面是保证没有解的，我已经看过了，它没有解，
所以我才回头。所以这种叫做系统的方法而且是隐含的，
遍历这搜索树，并不是真正的每个节点都走过，而是都看到过。
搜索策略可以有深度优先，宽度优先，
也有的是按某种函数计算，选择一个方向优先， 或者是我宽度优先进行搜索，
到某一层以后后边的遍历我们采用深度优先的方法，这样相结合也可以。
结点分支的判别条件就是约束条件。
如果满足约束条件向前继续搜索，
我们就扩张这个解向量，不满足约束条件就回溯到该结点的父结点。
结点的状态采用动态生成的方法。
白颜色表示没有访问过的结点，如果结点是灰颜色，
正在访问这个结点为根的子树，就是这个结点已经访问过了，
但是以这个结点为更根的子树还没有访问完， 因此还在下边继续遍历这个结点就是灰颜色。
当这个结点是黑颜色的时候，表示以这个结点为根的子树全部遍历完成了。
那么从这个结点就该回溯到他的父结点，这个结点以后再也不会访问了。
所以用这三种状态来表示它。
那么它的存储呢就存储当前的路径，这是它的基本思想。
下面我们看一下结点状态的例子。
这是一棵深度优先的搜索树，
我们看到1访问2然后回到1，
这个时候这个2号结点是再也不会被访问到了，它就是黑色了。而一号结点是灰色的，
因为它已经访问过了，但是它为根的子树尚没有访问完成。
由1访问到3，3到5， 5再到8，由8再回到5，它是这样的一个过程。
那么我们现在假定已经进行到1，2， 3，5，8，现在访问到这儿了，
到这个时刻2号结点是黑的， 1号，3号，5号都是灰的，
8号结点是黑的，因为从这一回去以后，再也不会 见到8号结点了，所以这个是黑的了。
那么下边再回到5号，回到5号以后， 那么我们到8这个结点，如果进行到这个位置的时候，
它是变成黑的了，而后边的这些个是在回到5号以后，
才可能被访问到的后续的这些个结点。
这些个结点一次都没有碰到过，所以它们都是白色的，这就是三种颜色的状态。
我们看到已经完成访问的2，8是黑的， 已经访问但没有结束的1，3，5是灰颜色的，
尚没有被访问的9，6，7，4，这4个结点是白色的。
回溯算法适应的条件可以把它总结一下。
也就是说我们现在访问到第k维的部分向量， 就是前K维已经赋了值了，
而且它是满足约束条件的，我们可以用这样一个位词。
来表示它，就是P(x1,x2,...xk)为真，
就是说这k为分量的赋值使得约束条件成立，
就是它的含义。比如说，对于n个皇后的问题，
前面放了k个皇后，她们彼此都不攻击，我们就可以 用这样一个谓词为真，来表示这件事情。
那么所谓多米诺性质呢是回溯算法的适用条件，
这个性质我，我们可以用下边的公式来表达出来。
这是P(x1,x2,...xk+1)为真，
蕴含P(x1,x2,...xk)为真，
这是什么意思呢？就是如果k+1维的向量都满足约束条件，
那么k维的向量一定满足约束条件，就是这样的含义。
把这个命题 写成它的逆否命题的形式，就是如果结论不对了，
就是k+1维的向量不满足约束条件了，就是前面这个
则，写成它的逆否
命题的形式，如果k维的向量不满足约束条件了，写成这个公式，
则它k+1维的向量也不满足约束条件。
这个命题是上面这个命题的逆否命题， 它们的真值是等价的。那么我们考虑下面这个命题的含义。
就是如果k皇后放完了以后， 它都有攻击的现象，有两个皇后在同一行，同一列
或者是在同一条斜线的情况出现，你再对k+1维的皇后找她的放置位置，
没有意义了。你就把这个皇后放上以后，这k+1个皇后仍旧是 存在着攻击的现象。这就是这个命题的含义。
因此我们从这个结点回头，它如果不满足了，我们就回头
前边没有意义搜索，你再扩张它的解，也不会找到可行的解。
这就是回溯算法不丢解的依据，也就是它的适用条件。
下边我们看一个反例。
这个例子它如果使用回溯算法，你来设计一个 约束条件，设计不好的话就会出错。
这是一个不等式，其中x1,x2,x3都是1到3之间的整数，
我们要找所有满足这个不等式的解，把它找出来。
这个是一个三维的向量，就是x1,x2,x3三个数都取什么值，
如果那些个值取了以后，使得这个不等式成立，就是它的一个解。
下面我们设计一个条件，约束条件的判定。
就是把如果是x1到xk， 把它们对应的代入左半部，
都使得它们对应的那部分 表达式的值不超过10，就叫做满足这个条件，
比如说，P(x1)就是5x1这一部分，不超过10，
P(x1,x2)是什么呢？就是5x1加4x2不超过10，
那么P(x1,x2,x3)是什么呢？就是5x1 加4x2再减掉x3也不超过10，
这是这个谓词所表达的含义。
那么下边我们看看如果按照这个约束条件来判定的话，
不断地扩张解会不会出问题。它不满足多米诺性质，
就是说如果 3个分量代进去满足条件的话，
不能推出两个分量代进去也满足条件。
由于它不能推出，所以它不满足多米诺的性质。
为什么呢？因为当3项代进去满足的话， 你不能判定前两项加起来一定小于等于10，
如果你x3取得大一点，前边超过了10，我再减掉一个x3以后 反而三个代进去它可能小于等于10，
但是你不能判定前两项的和一定小于等于10。
那么你按照这个约束条件，来做回溯不断扩张地减向量， 这个算法就会出错，它会丢解。
那么下边我们要做一个变换。变换就是说 把这一项本来是个减的，我要变成一个加的项，
如果这是一个加上一个大于等于0的数， 前两项超过10了，我再加上一个大于等于0的数，肯定超过10了。
所以这样就满足了多米诺的性质。怎么变呢？我们做一下变换。
令x3=3-x3'， 把这个3-x3'代到这x3的位置，
这儿有一个减号，这儿有一个减号，两个就抵消掉，变成加了。
那么代进去以后，化简以后变成这样一个公式， 右边就变成13了。那么这个x3'的范围是多少呢？
因为x3是在1和3之间，x3'呢就在0和2之间，
它是一个大于等于0的数。那如果前两项已经超过 13了，我再加上一个大于等于0的数，它肯定超过13，
这个时候就满足多米诺性质了，对于它就可以使用回溯算法。
当然使用回溯算法，把对应的解，就是x1,x2和x3'都找到了，
那么利用这个公式，可以把x3也解出来，所以相当于原始问题的解也找到了。
这就是说，一定要有合适的约束条件， 使得它满足多米诺性质我们才可以使用回溯的算法。
把这一讲内容小结一下。
回溯算法的适用条件是多米诺性质。
回溯算法的设计步骤，首先我们要定义解向量
和每个分量的取值范围。比如说，我们把解向量设计成一个n维的
分量，其中的Xi是什么含义呢？ 把它定义出来，然后把它的取值范围给确定，就是原始的取值范围。
下边就是我们要确定在它的部分向量
已经做到了k-1维的时候， 第k维的这个取值会有什么变化。
因为在约束条件下，前边有了一些值以后， 第k维的取值不再是原始的这个Xk集合，它可能会缩小，因此
我们要计算在当前它可能的取值范围，就叫做大Xk，
把这个计算出来。然后我们要确定 结点儿子的排列顺序。这里边有这么多种可能的值，
这些个值就代表了下面分支的那么多个方向， 我们这个方向是从左到右是怎么排的，比如说
Sk中从小到大来进行排列，就是确定这个排列规则。
然后我们判断这个问题是不是满足多米诺性质， 如果满足的话，才可以使用回溯算法。
确定每个结点的 约束条件，就是它下一步继续分支是按照什么条件来
分支，如果不满足约束条件，就从这个结点 向父结点回溯。确定搜索策略。
深度优先还是宽度优先，或者其他的搜索策略。
确定存储它的数据结构，
我们存储的就是这条路径，那么用一个链表一般就可以做到了。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
