[科普中国]-回溯法操作

回溯法操作的基本思想

回溯法也称为试探法，该方法的基本思想是：从一条路往前走，能进则进，不能进则退，换一条路再试，直到所有的路径都试到。它的求解过程实质上是一个先根遍历一棵“状态空间树”的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中的。当试探过程中出现的状态和问题所求解产生矛盾时，不再继续试探下去，这时出现的叶子结点不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先根遍历，并在遍历过程中剪去那些不满足条件的分支。为了应用回溯法，所要求的解必须能表示成一组约束条件，通常要求所有的解满足一组综合的约束条件1。

多约束条件下的合理分配问题在网络规划、模式识别及多目标优化等众多领域有着广泛的应用。这些问题往往涉及多个约束的同时优化，但各约束间常存在冲突，因此寻求多约束条件下的合理分配问题的最优解或可接受解一直是数学及计算机领域中重要的研究课题。回溯法是解决联合搜索问题的一个重要方法，算法的基本策略之一，是在问题的解空间中，按照深度优先的策略从根结点出发搜索解空间树，在搜索的过程中，根据实际问题的基本要求和优化规则，确定相应的选优条件和优先权，由此对解空间进行剪枝，以提高搜索速度，得到最优解或可接受解。

回溯法操作思路简单描述回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。基本思想类同于：图的深度优先搜索和二叉树的后序遍历。当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。它有“通用解题法”之美誉2。

详细描述详细的描述则为：回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：

（1）使用约束函数，剪去不满足约束条件的路径；

（2）使用限界函数，剪去不能得到最优解的路径。

问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

回溯法的实现方法回溯法的实现方法有两种：递归和递推（也称迭代）。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。

递归思路简单，设计容易，但效率低，其设计范式如下：

递推算法设计相对复杂，但效率高。其设计范式如下：

子集树和排列树子集树所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。

如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。

回溯法搜索子集树的算法范式如下：

排列树所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。

如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。
回溯法搜索排列树的算法范式如下：

实例应用利用回溯法解决问题的几个经典问题如下：

（1）装载问题

（2）0-1背包问题

（3）旅行售货员问题

（4）八皇后问题

（5）迷宫问题

（6）图的m着色问题

（7）宿舍分配问题

0-1背包问题**问题：**给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
**分析：**问题是n个物品中选择部分物品，可知，问题的解空间是子集树。比如物品数目n=3时，其解空间树如下图，边为1代表选择该物品，边为0代表不选择该物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入。回溯搜索过程，如果来到了叶子节点，表示一条搜索路径结束，如果该路径上存在更优的解，则保存下来。如果不是叶子节点，是中点的节点（如B），就遍历其子节点（D和E），如果子节点满足剪枝条件，就继续回溯搜索子节点。

学生宿舍分配问题学生宿舍分配问题，其简化数学模型可概括为一个资源分配模型，即将某种定量资源分配给不同的需求个体， 同时满足一定的约束条件。具体讲，学生宿舍分配就是按一定的分配方法，根据学生的基本特征，分配合适的宿舍。作为资源分配模型的实例，学生宿舍分配问题应符合下面几个基本要求 ：

（1）需求集:需求集合中包含的元素个数是有限的;每个元素具有一系列特征；正是这些特征使不同的需求个体相互区别；对于学生宿舍分配问题而言，需求集就是某一类需要分配宿舍的学生集合，其特征有姓名、性别、成绩、来源地等；

（2）资源集：资源的总数是有限的， 不同资源是可以区分的；对于学生宿舍分配问题而言， 资源集合中的元素就是学生公寓的房间，其特征有所在楼号、所在层数、应住人数、实住人数、宿舍类别等；

（3）约束条件群：需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系，构成了约束条件群。对于学生宿舍分配问题而言，最主要的约束条件是：每个公寓房间可以对应若干个学生， 但一个学生只能对应一个房间；在此基础上，还可以依据一定的特征定义其它软约束， 如：同一班级的所有宿舍,，学生的学习情况尽可能均衡；同一宿舍的学生尽可能来源地不同等等；

（4）解集：符合约束条件的一组解， 实质就是需求集与资源集之间的对应关系，也就是宿舍分配结果。

学生宿舍分配的基本要求与任务就是为每个在校生选择一个宿舍。此外，在论证学生个体之间及与宿舍集体之间的关系和相互影响的基础上， 在学校条件允许的前提下，遵从科学化、合理化、人性化的原则， 还应该依据下列因素对学生宿舍分配方法进行优化：

（1）不同宿舍学生的学习情况尽可能均衡；

（2）同一宿舍的学生尽可能来源地不同；

（3）同一院系、年级、专业、班级的男生或女生， 住宿尽可能集中；

（4）提供不同的宿舍类别供学生选择。

以上基本要求和优化规则就是学生分配宿舍问题的约束条件群，也是分配问题过程中的选优条件；这些宿舍分配的基本要求和优化规则，其优先权是递减的；如果在分配过程中不满足约束条件群， 该选择即为不优或达不到目标；当遍历该步骤的所有可能仍未满足约束条件群，该状态就满足了回溯条件，则从该回溯点退回去重新选择，这就是宿舍分配问题回溯算法的基本思想。其操作步骤如下图：