回溯和分支限界
回溯和分支限界
回溯法：
回溯法的解的形式是什么？
一 求的解向量是可行解还是最优解
回溯法的搜索空间是什么？
二 是什么类型的树
三 是否满足多米诺性质
回溯法的搜索策略有哪些？
回溯法是如何进行减枝的？
回溯法的适用条件是什么？
回溯法存储搜索路径的数据结构有哪些？
回溯法实现的方式主要有哪两个？其伪代码如何实现？
搜索树节点数的估计如何实现？
回溯法的适用范围是什么？
优化和搜索问题
6.1 概述
从下至上，进行了逐一讲解
6.2 几个回溯算法的例子
- n后放置
由题意可知，其解为四维向量
其搜索空间为：
4叉树
2. 0-1背包
一定要注意对搜索空间的了解：
为什么只有两个方块呢，因为回溯发现，其他分支内的解没有这两个解好。
- 货郎问题
这里的min函数表示走一圈的距离，d(ck1,ck2)+d(ck2,ck3)+d(ck3,ck4),d(ckn-1,ckn)+d(ckn,ck1)
在此特别强调，解的形式和约束条件是建模中最重要的东西。
对于货郎问题的实例，首先要给出所有的城市两辆之间的距离。
同时易知解向量形式为四维向量（怎么走）
都是可行解，选其中的最优解。在这里假设是从一号城市开始的。所以一开始是一分叉的
总结
1. 解都是向量
2. 搜索空间都是树结构，货郎问题为排列树，0-1背包问题是子集树、n皇后问题是n叉树，其差别在于分叉的规则不一样。n叉树，每次分n个叉，子集树： 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树，分叉规则视具体情况确定，0-1背包问题就是分2叉。
例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有2n个叶节点，其节点总个数为2(n+1)-1。遍历子集树的任何算法均需要O(2^n)的计算时间。
排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。
4. 树的节点是向量的前部分，可行解在叶节点，最优解在可行解中找
5. 搜索算法有：深度优先、宽度优先、…跳跃式遍历搜索算法从而找到解
6.3 回溯算法的设计思想和适用条件
这张图很重要，一般思考问题就是按从左到右的顺序。
先是描述问题，在考虑解的性质。
在了解解向量的形式以后，要画出搜索空间。
然后选择搜索方式，然后开始进行搜索。
在搜索的时候，在结合约束条件进行减枝
如何进行剪枝，要根据约束条件
对回溯法每个部分的特点的了解很重要。
- 回溯法的目的就是搜索解
- 在求解解向量的过程中，是不断扩张部分解向量，最终达到解向量的大小
- 搜索空间都是树
- 搜索方式都是跳跃式遍历，即进行剪枝
- 每一次进行下一个解向量元素的求解，都需要进行约束条件的回溯判定
深度搜索和宽度搜索的区别
上面最重要的就是回溯法的适用范围是：搜索和优化问题 ，还有就是对搜索空间的了解，记住可行解在输叶上。
注：搜索过程：隐含遍历搜索树的意思，没有实际上的完全遍历整颗树
有一个小知识点，就是：树的每一层其实就是解向量中的一个值，所以解向量的位数决定了树的层数，每一个解的种类决定了分的叉数
上面最核心的就是多米诺性质，它是回溯算法不丢弃解的原因，也就是它的适用条件。
下面举个反例：也是极其的重要的：
反例就在于它有减号，在前两项大于10的情况下，在之前的理论上就不需要进行下面的选择，也就下面就不存在解了，然而减号，是下面仍可能有解。
要符合多米诺性质
需要改减为加（改变x3的取值范围，这是一个实用技巧）
小结
下面的总结十分的重要：
像什么搜索策略、和数据结构往往是次要的，都很固定。搜索策略要么是深度优先，要么就是宽度优先，数据结构一般就是链表、栈等
上诉难于理解就是（2）和（3），其就是对反例的思考，需要在求解出k-1维向量的前提下，需要对下一个k维的取值进行计算，Xk，就是k维值可取值的范围。
然后（3）中确定k维取值的排列规则，是从小到打排列还是别的啥
最后进行多米诺性质的判断
6.4 回溯法实现及实例
注意注意：每个xk为每个分量的初始取值范围，把有约束条件的范围的初值也赋成初始范围的值，不懂，再说！
实例
什么是使得c1-W1达到最小的装载方案，其实就是c1尽可能的装，如何装到最多
回溯的过程是最重要的：
回溯就是从左子树转达右子树
直到有装集装箱的节点的右分支，然后进行不装的这样的处理
注：有个事情要讲一讲，其实边才是解向量中的值
实例
图中只是搜索树 的一部分
6.5 图的着色问题
7个顶点3种颜色
这里有一个重点，可以通过对称的办法，节省5/6的 时间
以后再看看，对称性是裁剪搜索树的有效方法
6.6 搜索树节点数的估计
到这里，我心里有点看不下去了，下次再说