回溯算法思想

‘壹’ 五大基本算法——回溯法

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

基本思想：将问题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-皇后问题

具体问题可网络详细内容。

‘贰’ 常见算法思想6：回溯法

回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。

下面是影响算法效率的因素：

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：

把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：

执行：

‘叁’ 回溯法的基本思想是什么

回溯法又称试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
当我们遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花宏历滑费的时间比较长。
对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。
回溯法中，首先需要明确下面三个概念：
（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在深度优先搜索中，烂乱只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
利用回溯法解题的具体步骤
首先，要通过读题完成下面三个步骤：
(1)描述解的形式，定义一个解空间，它包含问题的所有解。
(2)构造状态空间树。
(3)构造约束函数（用于杀死节点）。

然后就要通蔽腊过深度优先搜索思想完成回溯，完整过程如下：
(1)设置初始化的方案（给变量赋初值，读入已知数据等）。
(2)变换方式去试探，若全部试完则转(7)。
(3)判断此法是否成功（通过约束函数），不成功则转(2)。
(4)试探成功则前进一步再试探。
(5)正确方案还未找到则转(2)。
(6)已找到一种方案则记录并打印。
(7)退回一步（回溯），若未退到头则转(2)。
(8)已退到头则结束或打印无解

‘肆’ 简述回溯法的2种算法框架,并分别举出适合用这两种框架解决的一个问题实例

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束

一般表达
可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

规律
我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<=i）元组（x1，x2，…，xj）一定也满足d中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反d中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反d中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集d具有完备性的问题p，一旦检测断定某个j元组（x1，x2，…，xj）违反d中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题p的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

‘伍’ pascal 回溯 拼木条 问题 求解析 要详细

一、回溯法的基本思想
回溯法又称试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
具体说,就是：在搜索(依次用各种方法一一去试探)的过程中，当在P点有N种选择，则从第一种开始尝试，若第K种可行，即这一步搜索成功，打上标记，再向前(即 P+1点)搜索；如在P点搜索失败(所有的方法都宴羡试探过，没有一种可行)，为了摆脱当前的失败，就返回搜索进程中的上一点(即P-1点)，再用第K+1种方法(假设上次在P-1点用第K种方法搜索成功，必须明确以前用过的方法不能再用，否则会陷入死循环)再去搜索，重新寻求解答。这样搜索回溯，再搜索再回溯，如能搜索到终点，问题有解，如最后回溯到出发点，问题就无解。

这种在搜索的过程中，先对深度大的点进行扩展的算法，叫深度优先搜索法。
设搜索深度指针为P，搜索方法指针为I，可把深度优先搜索算法写成如下形式：
P:=0;I:=0;
repeat
I:=I+1; (搜索到一种方法)
IF 搜索方法有效 THEN
begin
试探产生临时新结点
IF 符合条件 THEN
begin
P:=P+1;(深入一步)，新结点记录，I:=0，再全方位搜索
IF到达终点 THEN 结束搜索，输出结果;
End;
End
ELSE (搜索的方法无效)
begin
I:=上次搜索的方法(下一轮将用I的下一方法去搜索);P:=P-1(后退一步返回上结点);
END;
UNTIL P=0;
IF P=0 THEN {深度饥祥岩指针P为0，表示已退到起始状态，是本题无解的标}
无解
ELSE
输出烂御结果;
END.

太长了，放不下。要的话可以吧课件给你。

‘陆’ 回溯算法的基本思想

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

‘柒’ 四皇后问题求解

本章内容来自《妙趣横生的算法》蠢做一书中。

回溯法是一种非常有效，适用范围相当广泛的算法设计思想。许多复杂的问题，规模较大的问题都可以使用回溯法求解。因此回溯法又有“通用解题方法”的美称。

回溯法的基本思想是：在包含问题的所有解的解空间树中，按照氏档烂深度优先搜索的策略，从根结点出发深度 探索 解空间树。当 探索 到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续 探索 下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含“剪枝”操作。

如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被 探索 到才结束。如果只要求歼漏解问题的一个解，问题的最终解，因此要跳过对以该结点为根的子树的系统 探索 ，逐层向其祖先结点回溯。这个过程叫做解空间树的那么在 探索 解空间树时，只要搜索到问题的一个解就可以结束了。

应用回溯法的思想求解四皇后问题

分析：

上面一节中已经详细介绍了回溯法解决四皇后问题的基本过程。在这里将给出具体的算法描述和程序清单。

其实在解决四皇后问题时，并不一定要真的构建出这样一棵解空间树，它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构来真实地创建出一棵解空间树，不过那样会比较浪费空间资源。

运行结果：

‘捌’ 回溯算法的基本思想及其在软件开发中的应用

回溯算法其实就是简单的枚举，只不过是加猜亏了一点技巧者笑。回溯算法一般是已经完成的都是合法的，后续的操作不需要考虑先前已经完成的。短时间内通过文字也说不太明白，建议从一些题目去体会，八皇后、全排列。并综合递归去理解这样的话应该会有比较深刻的理解。
至于在软件开发中的应用，算法思想可以用在任首兆含何方面，最近甚至比较流行，将一些算法用到硬件中，算法提供的是一种思想，认真体会就会发现它会应用在任何方面。
希望能帮助到你。

‘玖’ 回溯算法的基本思想

回溯算法也叫试探法，它是慎枯一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。