回溯算法(一)

回溯算法详解
回溯算法是一种经典问题求解方法，通常被应用于在候选解的搜索空间中，通过深度优先搜索的方式找到所有可行解的问题。

回溯算法的本质是对一棵树的深度优先遍历，因此也被称为树形搜索算法。

回溯算法的基本思想是逐步构建候选解，并试图将其扩展为一个完整的解。

当无法继续扩展解时，则回溯到上一步并尝试其他的扩展，直到找到所有可行的解为止。

在回溯算法中，通常会维护一个状态向量，用于记录当前已经构建的解的情况。

通常情况下，状态向量的长度等于问题的规模。

在搜索过程中，我们尝试在状态向量中改变一个或多个元素，并检查修改后的状态是否合法。

如果合法，则继续搜索；如果不合法，则放弃当前修改并回溯到上一步。

在实际应用中，回溯算法通常用来解决以下类型的问题：
1. 组合问题：从n个元素中选取k个元素的所有组合；
2. 排列问题：从n个元素中选择k个元素，并按照一定顺序排列的所有可能；
3. 子集问题：从n个元素中选择所有可能的子集；
4. 棋盘问题：在一个给定的n x n棋盘上放置n个皇后，并满足彼此之间不会互相攻击的要求。

回溯算法的时间复杂度取决于候选解的规模以及搜索空间中的剪枝效果。

在最坏情况下，回溯算法的时间复杂度与候选解的数量成指数级增长，因此通常会使用剪枝算法来尽可能减少搜索空间的规模，从而提高算法的效率。

总之，回溯算法是一种非常有用的问题求解方法，在实际应用中被广泛使用。

同时，由于其时间复杂度较高，对于大规模的问题，需要慎重考虑是否使用回溯算法以及如何优化算法。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。
【问题】 组合问题
问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：
（1） a[i+1]>a[i]，后一个数字比前一个大；
（2） a[i]-i<=n-r+1。
例如n=5，r=3的所有组合为：
（1）1、2、3 （2）1、2、4 （3）1、2、5
（4）1、3、4 （5）1、3、5 （6）1、4、5
（7）2、3、4 （8）2、3、5 （9）2、4、5
（10）3、4、5
则该问题的状态空间为：
E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5}
【程序】
# include <stdio.h>
# define N 12
void write(int a[ ])
{ int i,j;
for (i=0;i<3;i++)
{ for (j=0;j<3;j++)
printf(“%3d”,a[3*i+j]);
printf(“\n”);

基本算法-回溯法（迷宫问题）作者：翟天保Steven版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处前言本文介绍一种经典算法——回溯法，可作为迷宫问题的一种解法，以下是本篇文章正文内容，包括算法简介、算法应用（迷宫问题）、算法流程和C++代码实现。

一、回溯法简介回溯法（Backtracking）是枚举法的一种，可以找出所有或者一部分的一般性算法，且有效避免枚举不对的解。

当发现某个解的方向不准确时，就不再继续往下进行，而是回溯到上一层，减少算法运行时间，俗称“走不通就回头换路走”。

特点是在搜索过程中寻找问题的解，一旦发现不满足条件便回溯，继续搜索其他路径，提高效率。

二、算法应用（迷宫问题）1.问题描述迷宫问题是回溯法的一种应用。

迷宫问题的描述为：假设主体（人、动物或者飞行器）放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。

主体可以通过遍历所有可能到出口的路径来到达出口。

当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。

主体需遵从如下三个原则：1.一次步进只能走一格；2.遇到路径堵塞后，退后直到找到另一条路径可行；3.走过的路径记录下来，不会再走第二次。

2.解题思路首先创建一个迷宫图，比如用二维数组人为定义MAZE[row][col]，MAZE[i][j]=1时表示有墙无法通过，MAZE[i][j]=0时表示可行，假设MAZE[1][1]为入口，MAZE[8][10]为出口，创建如下初始迷宫图：图1 初始迷宫图当主体在迷宫中前行时，有东南西北（即右下左上）四个方向可以选择，如下图所示：图2 方向示意图视情况而定，并不是所有位置都可以上下左右前进，只能走MAZE[i][j]=0的地方。

通过链表来记录走过的位置，并将其标记为2，把这个位置的信息放入堆栈，再进行下个方向的选择。

若走到死胡同且未到达终点，则退回到上一个岔路口选择另一个方向继续走。

回溯法一、回溯法：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。

问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

换句话说，这个结点不再是一个活结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：procedure try(i:integer);varbeginif i>n then 输出结果else for j:=下界 to 上界 dobeginx[i]:=h[j];if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;end;end;说明：i是递归深度；n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；二、习题：1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=302、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。