|
·搜索，是通过穷举一个问题的所有或部分可能的情况来确定问题的解。
·穷举，奠定了搜索，特别是深度优先搜索的基调，使它成为了—种复杂度通常较大的算法，例如:
·求全排列，复杂度为O(n!)
·求从一个数列选择任意个数的所有情况，复杂度为0(2")
全排列:
全排列就是一个数列的所有可能的排列情况。例如对于数列[i,2,3]，它的全排列为:
[1,2,3],[1,3.2],[2,1,3],[2,3,1],[3,1,2],[3, 2,1]我们如何做到对所有情况不重不漏的枚举呢?
想要不重不漏，我们需要制定枚举的规则:对于三个空位_? _? _我们从左至右依次填数，对于每一个位置，优先枚举填入1的情况，其次是2和3，当这个数字被用过时跳过这个数。
用递推循环表示这个过程:
for (int i = 1; i <= 3; i++) i
vis[i] = 1;
a[1] = i; ///填入第一个数，标记已经使用过
for(int j = 1; j <= 3; j) i
if (vis[j])continue; // 如果已经用过则跳过
vis[j] = 1;
a[2] = j; illl11ll11 // 填入第二个数，标记已经使用过
for(int k = 1; k <= 3; k++) {
if (vis[k])continue; // 如果使用过则跳过
a[3] = k;
print(a); // 所有数已经填完，输出
vis[j] - 0; //这一次枚举结束，将标记去除
}
vis[i] = e; //同上 重点!!!
)
·在只有三个数时，递推固然简单，可当数字越多，需要写的循环也变得越来越多，递推的写法显然不够优雅。
·观察可以发现，每次填数的过程是一模一样的。那我们面对完全一样的算法过程，用什么方法可以让我们的代码变得简洁呢?
·函数。
·我们可以利用函数不断调用自己来实现这个重复的过程。·这就是递归。
?
void dfs(int now) {// now即当前要填的是第几个数
if (now == 4){ // 递归边界
print(a);
return;
//当所有数都填完后输出
for (int i = 1; i <= 3; i++) {//寻找一个没被使用过的数字
if (vis[i])continue;
vis[i] = 1;
a[now] = i; //同递推过程
dfs(now + 1); // 相当于递推过程的下一层循环
vis[i] = 0; // 回溯
}
return;
}
边界和回溯
为什么要有递归边界
递归边界为递归过程设置了一个终止条件，这个终止条件一般是一种情况的答案已经求得，也有可能是这种情况不可能成为最终答案(这就是之后要讲的剪枝)。
例如求全排列时的递归边界就是所有数都填完。而没有递归边界的递归就像一个无数层嵌套的循环。
·回溯法就像递推的循环结束时将标记清除的过程。
·当dfs(now +1)的套娃到达递归边界返回时，注意这里返回的是上层函数（即前一个位置)，并在这里执行visi]=o将标记清除。
?
void dfs(int now) {
// now即当前要填的是第几个数
if (now == 4) //递归边界
print(a);
return;
}// 当所有数都填完后输出
for (int i = 1; i <= 3; i++)//寻找一个没被使用过的数字
if (vis[i])continue;
vis[i] = 1;
a[now] = i; // 同递推过程
dfs(now + 1); // 相当于递推过程的下一层循环
vis[i] = 0; // 回溯
}
return;
?上面递归求全排列的过程其实就是深度优先搜索。?
dfs的基本框架如下:
void dfs(...) i //递归参数:当前故举到哪一步
if (到达终点) {
记录答案
return;
}
if (当前状态不合法)return;
if (达到剪枝条件).return这两行是等效的，只用存在其一for(...) i //枚举状态
if (将要访问的状态不合法)continue; 操作
标记已经访问
dfs(下一步);
(还原标记)回溯法
}
}
例题:八皇后问题
在一个8x8的国际象棋棋盘上摆放8个皇后，使它们互相不能吃掉对方，即这8个皇后互相不同行不同列，也不在同一条对角线的平行线上。
要求按字典序输出所有可能的摆放情况，每种情况一行，按行号从小到大的顺序输出每个皇后的列号。
首先要确定枚举规则。题目要求按行号从小到大的顺序输出，就告诉了我们要按每一行来进行枚举。
递归参数:行号。
递归边界:所有边都枚举完成。要枚举的状态:每一列。
不合法状态:当前位置的行或列或对角线的平行线上有其他皇后。思考如何标记，如何判断当前列可不可用。
注意回溯。
明天继续写
|