回溯算法

介绍

加入你要在许多不同的选择中做一系列的决策，那么
你没有足够的信息来帮助做出选择
每个决策都将产生一些新的选择
一些决策的序列（可能不只一个）也许就是问题的解
回溯算法系统的尝试搜索各种决策序列知道找到一个令你满意的决策序列

术语

一个有节点构成的树

根节点（开始节点）
内部节点（既有孩子节点，又有父节点）
叶子节点（没有任何的孩子节点）

活动节点（当一个节点被考察到了，意味着我们下一次会搜索他）
扩展节点（当前我们正在访问的节点，要扩展他的所有的孩子节点）
死节点（不扩展它的孩子节点）
回溯算法可以看作是为了找某个特定的叶子节点而进行系统搜索的一种方法

在一棵树种，非叶子节点是其他一个或更多节点的父节点（它的子节点）
树种的每个节点（除了根节点）：都有一个父节点
通常我们都从下画树

回溯法是一个即带有系统性又带有跳跃性的搜索算法
系统性----搜索整颗空间树
跳跃性----算法搜索至解空间树的任意节点时，判读该节点为根的子树是否包含问题的解，如果肯定不包含，则跳过改节点为跟的子树的搜索，逐层向其祖先节点回溯。否则，进入该子树，继续深度优先的策略进行搜索

如果都是整体的判断，不能称为回溯
对于每个根节点的判断，有这个的才能称为回溯

回溯的思想

回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式(x1x2`````xn)来表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间，逐步确定xi的值，直到解被找到。

回溯法列举出解空间中所有可能的情形来确保解的正确性

假设我们已经确定部分分解的集合，在此基础上通过增加解元素x(i+1)来扩展解，确定x(i+1)的值后，我们要测试x1x2````x(i+1)是否仍是可行解

回溯算法的基本步骤如下

1.定义问题的解空间。（定义一个数据结构）这个空间必须包含一个问题的最优解
####解的空间
如果Si是xi的范围，那么S1S2S```SN的问题的解空间
例如掷骰子一次就有两种可能，要扔5次，就是22222

通常这个解空间是非常巨大的，所以搜索一个目标解的代价是很难想象的。为了使回溯算法更有效率我们必须缩小搜索空间

2.组织好解空间以便使搜索更容易
典型的组织方式是利用图或树的结构
3.以深度优先方式搜索解空间，利用剪枝函数来避免搜索进入不可能得到解的子空间

解空间树

在每一个时刻只保留了一个路径，其他路径都回溯了，释放了

生成问题状态的基本方法

深度优先搜索的活节点，是马上就扩展
广度优先搜索的活节点，并不是马上就扩展，而要把所有的中间节点出来之后再进行扩展

子集合的结构或者排列的结构

子集树
当我们要解决的问题是要求一个使问题最优的n个元素的子集，问题的解空间常可以组织成一棵子集树
构造所有的子集
n个元素的集合有多少个子集？
如果每个Si的子集是k，有n个，所以有k^n

子集树的程序模板
为什么？因为只要我的解释分量构成的解
Backtrack(i)//表示我们解的程度，表示第i层

if i>n then Update(x)//当i到与n，表示已经走到了叶子节点，是大于n,而不是等于n，所以已知叶子节点已经被接受了，当前的这个节点所在的路径已知的解一定是这个问题的可行解，已经是最优解，这是当前的最优解，不是全局的，update可以是记录解的过程，或者我们的最佳值
else//否则，在中间节点的时候
	for each a∈Si do//对于每一个Si,在这个程度上做出的可能的决策，一一赋值给Si的分量
		xi←a
		ifC(i) and B(i) then	//C（i）B(i)限制函数，如果没有这个内容，他就是深度框架
			Backtrack(i+1)

排列树

当问题是求n个元素一个排列以使问题的最优化时，解空间常可以组织成一棵排列树
构造所有的排列
n个元素的集合有多少种的排列？
n!
排列树

x1表示第一个所做出的决策
当x1选择的1节点时，x2会受到影响，所以只能在剩下的节点里面选，

Backtrack(i)//i代表当前第i个分量

if i>n then Updata(x)  //安全到达叶子节点
else
	for j ← i to n do  追从i到n，第i到n个，剩下的去找
		xi	把xn赋值给xi
		

剪枝函数

有两种：约束函数和限界函数
利用剪枝函数，剪枝无效分支，集中搜索有用的分支
为了改变搜索，应用回溯法至少需要注意一下四点
（1）怎样选择约束函数
（2）怎么计算上界（对最大化问题）
（3）怎么计算下界（对最小化问题）
（4）怎么利用约束函数和限界函数来进行剪枝
约束函数在于是否可以找到可行解或者不可行解
限界函数在于找到是否可以找到最优解的描述

B（i）下界函数，B（i）找到了我们找到的更大，所谓下界一定找到的这个值更大

听取的是厦门大学《算法设计与分析》这门课