搜索
搜索, 其实就是在一堆东西中找到自己想要的那个.
在知识爆炸的现在, 难的不是获取知识, 而是找到自己需要的知识.
❝1998年8月底的一天，两位斯坦福大学毕业生佩奇和布什当着Sun联合创始人安迪·贝克托 斯海姆(Andy Bechtolsheim)的面点击了几下鼠标，就获得了后者10万美元的投资。他们当时向贝克托斯海姆演示了一项新型互联网搜索技术。后来他们创立了 google, 是最大的搜索引擎.❞
定义
搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
在算法竞赛中，枚举、深度优先搜索（DFS）、广度优先搜索（BFS）是最常使用的搜索方法.
用好搜索算法, 基本上可以拿到提高组省一.
基本步骤演示
（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
（2）从stack中访问栈顶的点；
（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；
（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；
（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
例子：输出全排列
洛谷P1706 全排列问题
- 「题目描述」
输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
- 「输入格式」
一个整数 n。
- 「输出格式」
由 1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。
- 「输入输出样例」
- 输入
3
- 输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1说明/提示
1≤n≤9
- 「分析」
全排列的方案数是
3个数, 有3个位置, 第一个位置有3种选择, 第二个位置有2种选择, 最后一个位置有1种选择.
设3个位置分别是 i j k, 每个位置一开始有3个选择, 前面得选中后, 后面的位置选择的数就会减少.
暴力枚举的程序:
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= 3; j++)
for(int k = 1; k <= 3; k++) {
if(_) //程序填空
printf("%d %d %d\n", i, j, k);
}暴力枚举的过程其实就是3个位置可选数的枚举. 可以看成是给每个位置寻找一个合适的数.
n个数时, 我们可以枚举n个位置, 每个位置选择不同的数. 怎么知道哪个数被选了, 哪些数没被选呢? 可以开一个vis[]数组, 记录选/没选的情况.
每个位置的选择方法是一样的, 写成一个函数:
// ans存放选择的数 vis记录是否被选过了
int ans[N];
int vis[N];
void select(int pos) // 给pos位置选个数吧
{
for(int i = 1; i <= n; i++){
if (vis[i] == 0) {
ans[pos] = i;
vis[pos] = 1;
break; // 选中 i 这个数, 退出.
}
}
}for(int pos = 1; pos <=n ; pos++) {
//给每个位置选个数
select(pos);
}上述代码可以查找出一种方案. 可是其他方案怎么办? 怎么记录哪种方案选过, 哪种没选呢?
以前学过的for循环实现的暴力枚举就不太容易实现上述功能了(当然可以模拟栈, 或者二维数组).
这时就得用到递归 + 回溯了.
dfs(int now)表示查找第now个位置可以放哪个数字（从小到大选取）。
ans[i]表示第i个位置选取的数字。
vis[i]表示数字i是否被选取，值为1表示选取， 0为未选取
void dfs(int pos)
{
int i;
if(pos == n + 1) { // 找到了n个数, 输出. 递归出口
for(i = 1; i <= n; i++) {
printf("%5d", ans[i]);
}
printf("\n");
return;
}
for(i = 1; i <= n; i++) {
if(vis[i]) // 如果被选过了, 找下一个
continue;
ans[pos] = i; //选中 i
vis[i] = 1; // 记录选中
dfs(pos + 1); // 继续下一个位置的选择
vis[i] = 0; //回溯, 下一个排列
}
}深度优先搜索(Depth-First-Search — dfs)
深搜定义
深度优先搜索(Depth-First-Search)它的思想是从一个顶点 V0 开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
dfs框架
void dfs()//参数的个数根据实际情况确定
{
if(到达终点状态)
{
//根据题意添加
return;
}
if(越界或不合法状态)
return;
if(特殊状态) // 剪枝
return;
for(扩展方式)
{
if(扩展方式所达到状态合法)
{
修改操作;
标记；
dfs()；
(还原标记)；
//是否还原标记根据题意
}
}
}Q1.组合的输出
和前面讲的全排列很像, 很典型的一道深搜，一路搜到底得到一种方案，本次方案排列完毕后，回溯搜索下一方案.
如何寻找下一个数?
那么怎么保存方案呢?
需要恢复现场吗?
和全排列有什么不一样呢?
算法分析：1、开两个数组，使用a[]记录排列的数据，b[]记录数字是否已经被用过了；
2、从第1个位置从小到大尝试放数据，假设第k个数据放好了，那么放第k+1个数据。如果已经放了r个数据，就输出a[]中已经记录的数据；接着往前回溯一个位置，试试后面的数据是否可以摆放在第k个位置。
3、以此反复，直到所有的数据和所有的位置全部试过。
#include <iostream>
#include <iomanip>
using namespace std;
int a[30]={0},n,r;
bool b[30]={0};
void search(int k){
int i;
for(i=1;i<=n;i++){
if(!b[i]){
b[i]=true;
a[k]=i;
if(a[k]<a[k-1]){ //不能降序排列
b[i]=false;
continue;
}
if(k==r){ //排列的数据个数达到r个，则输出这组数据
for(int j=1;j<=r;j++){
cout<<setw(3)<<a[j];
}
cout<<endl;
}else{
search(k+1); //尝试摆放第k+1位
}
b[i]=false; //回溯一位，进入下一轮循环会尝试i+1能否满足排列要求
}
}
return;
}
int main(){
cin>>n>>r;
search(1); //从第1个位置开始尝试摆放数字
return 0;
}Q2.自然数的拆分
算法分析：1、使用数组a[]记录排列数据；
2、从第1个位置开始尝试放数据，当第k个数据放好后，尝试放第k+1个数据；如果已经摆放的数据之和==n则输出，
然后往前回溯一个位置，试试后面的数据是否可以摆放第k个位置；如果已经摆放的数据之和已经>n，那么也要往前回溯一个位置，试试后面的数据是否可以摆放第k个位置。
3、以此反复，直到所有的数据和所有的位置全部1试过。
ace std;
int a[101]={0},n,sum=0;
void search(int k){
int i;
for(i=1;i<n;i++){
a[k]=i;
sum+=a[k];
if(a[k]<a[k-1]){ //不能降序排列
sum-=a[k];
continue;
}
if(sum>n){
sum-=a[k]; //和不能超过n，超过n，那么回溯一个数字
break; //如果和超过n,那么比i大的数字显然都不合适，所有直接跳出循环即可。
}
if(sum==n){ //满足和==n，则输出这组解
cout<<n<<'=';
for(int j=1;j<=k;j++){
if(j>1){
cout<<'+';
}
cout<<a[j];
}
cout<<endl;
}else{
search(k+1);
}
sum-=a[k]; //回溯一个数字
}
return;
}
int main(){
cin>>n;
search(1);
return 0;
}Q3.LETTERS
算法分析：1、使用a[][]存放输入的矩阵，使用b[][]记录试探过的地方，使用c[]记录走过的字母，sum记录走过的字母数量，mx记录最大数量。
2、从起始位置(0,0)位置开始，尝试向右走到底，不行再向下走到底，不行再向上走到底，不行再向左走到底，如果走不通则回溯一步。
3、以此反复，直到所有可以走的点全部被走过。
#include <iostream>
#include <iomanip>
using namespace std;
char a[25][25];
bool b[25][25]={0},c[128]={0};
int sum=0,r,s,mx=0;
void search(int x,int y){
//cout<<x<<','<<y<<endl;
if(y!=s-1){ //向右探索
if(b[x][y+1]==0&&c[a[x][y+1]]==0){
b[x][y+1]=1;
c[a[x][y+1]]=1;
sum++;
if(mx<sum) mx=sum; //mx记录最大经过字母数
search(x,y+1); //走通了，则尝试下一个节点
b[x][y+1]=0; //当走不通的时候，回溯
c[a[x][y+1]]=0;
sum--;
}
}
if(x!=r-1){ //向下探索
if(b[x+1][y]==0&&c[a[x+1][y]]==0){
b[x+1][y]=1;
c[a[x+1][y]]=1;
sum++;
if(mx<sum) mx=sum;
search(x+1,y);
b[x+1][y]=0;
c[a[x+1][y]]=0;
sum--;
}
}
if(x!=0){ //向上探索
if(b[x-1][y]==0&&c[a[x-1][y]]==0){
b[x-1][y]=1;
c[a[x-1][y]]=1;
sum++;
if(mx<sum) mx=sum;
search(x-1,y);
b[x-1][y]=0;
c[a[x-1][y]]=0;
sum--;
}
}
if(y!=0){ //向左探索
if(b[x][y-1]==0&&c[a[x][y-1]]==0){
b[x][y-1]=1;
c[a[x][y-1]]=1;
sum++;
if(mx<sum) mx=sum;
search(x,y-1);
b[x][y-1]=0;
c[a[x][y-1]]=0;
sum--;
}
}
return;
}
int main(){
cin>>r>>s;
for(int i=0;i<r;i++){
cin>>a[i]; //读入矩阵的每一行
}
sum++; //边界值是第一个节点，第一个节点肯定可以走
mx=sum; //如果只有第一个点可以走，那么最大字母数就是1
b[0][0]=1;
c[a[0][0]]=1;
search(0,0); //从0,0位置开始向上、下、左、右四个方向试探
cout<<mx;
return 0;
}Q4.八皇后问题
算法分析：1、首先从第一行的皇后开始尝试放置，放置的位置分别尝试1-8列；
2、假设前面k-1个皇后已经摆放好了，尝试第k个皇后的摆放位置，分别尝试1-8列，同一列上和两个对角线上
不能有皇后冲突，即可摆放；
3、当第k==8的皇后已经摆放好的时候，输出这一组解，然后回溯一步，收回一个皇后。