回溯法是一种比较中庸的算法，效率不一定是最高的，但理解起来比较直观，看下图：
回溯法
橙色的小方格每个有3种选择：1，2，3
当第一个小方格选择1的时候，也就是左边的图，这时对应的节点就是其连线的那个，旁边的
橙色的小方格也有3种选择，它选择了3，对应节点就是其连线的那个。
当第一个小方格选择2的时候，也就是右边的图，原理类似。
每个节点都代表某种特定的选择状态。
容易写出如下的回溯遍历算法：
i,j表示小方格的行列号
search(i,j)
{
k=0,1,2对应三种选择
for(int k=0;k<=2;k++)
{
选择一种0/1/2
sel(i,j,k);
ni,nj是[i,j]的下一个小方格
next(i,j,out ni,out nj);
递归搜索下一个小方格，深度优先
search(ni,nj);
}
}
从[0,0]开始深度优先搜索
search(0,0)
就是这么直观，你已经完成了一个回溯法，尽管看上去有点简陋，但它是很多复杂算法的基础哦。
可以看出，每个小方格有3种选择，二个小方格就是3*3的选择，也就是一共有3的N次方的状态，N为小方格的数量，上图就是3的9次方：
1 2 3
1 2 3 一种可能的状态
1 2 3
3 2 1
3 2 1 又一种可能的状态
3 2 1
...一共有3的9次方种
因此，算法的时间复杂度并不少
算法时间复杂度：可以看数据结构里面对应的讲解，
大概意思就是算法执行所需的时间和问题的规模之间的关系，
比如线性复杂度就是3*N，指数复杂度就是3的N次方，N为问题的规模，
一般来说，最好的是线性时间，算法时间不会被规模影响。
而指数时间就会因为问题规模扩大而变得难以求解。
当然，具体问题还是具体分析的。
回溯法的实际问题中，某些状态很明显是不符合当前的最优解的，直接跳过即可
因此回溯法一般都有优化的空间，使得实际算法的时间复杂度降低一些。
大家在后面的实际问题分析中就能深刻体会。
下面是：
美女上+美女下
网友评论