五大基本算法——回溯法

回溯法是一种选优搜索法（试探法）。

基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。

通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。

几个结点：

扩展结点：一个正在产生子结点的结点称为扩展结点

活结点：一个自身已生成但未全部生成子结点的结点

死结点：一个所有子结点已全部生成的结点

1、分析问题，定义问题解空间。

2、根据解空间，确定解空间结构，得 搜索树 。

3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。

4、递归搜索，直到找到所要求的的解。

1、子集树

当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。

子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。

遍历子集树时间复杂度：O（2^n）

2、排列树

当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。

遍历排列树时间复杂度：O（n!）

通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。

剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。

常见剪枝函数：

约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）

满足约束函数的解才是可行解。

1、0/1背包问题

2、TSP旅行商问题

3、最优装载问题

4、N-皇后问题

具体问题可百度详细内容。

’新建一程序在窗体上画 “树形框1”和“文本框1” 复制以下代码运行实现（不要往“树形框1”加项目）

.版本 2

.支持库 iext

.程序集 窗口程序集1

.子程序 __启动窗口_创建完毕

树型框1.显示根部线 ＝ 真

编辑框1.是否允许多行 ＝ 真

树型框1.加入项目 (, “原版本下载”, , , , , )

树型框1.加入项目 (0, “SAGA版”, , , , , )

树型框1.加入项目 (0, “黑肉版”, , , , , )

树型框1.加入项目 (, “MOD”, , , , , )

树型框1.加入项目 (3, “PR 蛋疼模组”, , , , , )

树型框1.加入项目 (3, “”, , , , , )

.子程序 _树型框1_项目被选择

.参数 选择方式, 整数型

.局部变量 临时文本, 文本型, , "0"

临时文本 ＝ 分割文本 (“这里是原版,这里是SAGA版,这里是黑肉版,这里是MOD,这里是PR 蛋疼模组,这里是空白”, “,”, )

编辑框1.内容 ＝ 临时文本 [树型框1.现行选中项 ＋ 1]

---