首先 讲讲什么是 搜索算法

顾名思义，一个负责找东西的算法

那么找什么呢？

他可以找一个数列，一条从起点到终点的路径，又或是物品的选择方案.还有你弄丢的橡皮

---

就比如说在家里找袜子， 首先进入大门，现在，我们有三个选择：

• 客厅
• 卧室
• 厨房 这三个中，我们先进入客厅，里面又出现了许多可以搜索的地方

就像这样，我们不断缩小寻找范围，直到我们能一眼确定这里没有我们要找的东西

把客厅一切角落都查找完毕后，一切归为原位，退出客厅并继续查找卧室，直到找到物品或是搜完整个家结束

---

那么把上面这个例子总结起来，搜索算法的本质其实就是：

完成一件事分为很多步，每步要做出选择

这个时候，我们就要用到搜索算法

下面来一个简单的例子，我们来走迷宫

我们可以选择上下左右四个方向之一前进，这很显然符合上面的性质（因为显然迷宫从起点到终点要走很多步）

---

下面是dfs和bfs的模板，大部分搜索算法都是基于这两个延伸出来的

这两份dfs区别在于一个判父亲是答案，一个判儿子是答案

dfs1：

void dfs(int k , int s)
{
	for(;;)//1.枚举生成孩子的线索 
	{
		//生成孩子 
		if(孩子合法)//2.判合法性 
		{
			//2.1保存孩子
			//2.2标记孩子
			if(是答案)//2.3判答案 
			{
				print();//输出
			} 
			else//2.4不是答案
			{
				dfs(k + 1);
			}
			//2.5取消标记 
		}
	}
}

dfs2：

void dfs(int k , int s)
{
	if(是答案)//1.判答案
	{
		print();//输出
	}
	else
	{
		for(;;)//2.枚举生成孩子的线索
		{
			//生成孩子
			if(孩子合法)//2.判合法性
			{
				//2.1保存孩子
				//2.2标记孩子
				dfs(k+1);
				//2.3取消标记
			}
		}
	}
}

bfs：

void bfs()
{
	//初始化队列
	queue<int> q;
	q.push(start);//根节点入队
	vis[start]=1;//标记根节点
	while (!q.empty())
	{
		//队首父亲节点出队
		fa=q.front();
		q.pop();
		if(fa是答案)
		{
			//输出答案
			//跳出循环
		}
		for()//枚举fa的所有孩子
		{
			//1.生成孩子
			if()//2.判孩子合法
			{
				//孩子入队
				vis[孩子]=1;
				q.push(孩子);

			}
		}
	}
}

---

下面来一点抽象的例子

接下来讲的东西代码神似，都是在我们上面讲的dfs板子里填数

子集树

代码：

#include <bits/stdc++.h>
using namespace std;
int ans[25];
int n;

void print()
{
	for(int i=1;i<=n;i++)
	{
		printf("%d ",ans[i]);
	}
	cout<<endl;
}

void dfs(int k)
{
	for(int i=0;i<=1;i++)
	{
		ans[k]=i;
		if(k==n)
		{
			print();
		}
		else
		{
			dfs(k+1);
		}
	}
}

int main()
{
	cin>>n;
	dfs(1);
	return 0;
}

当然，子集树也可以不用dfs实现，利用了二进制和循环

具体代码如下，大家可以课后自行研究

for(int i=0;i<(1<<n);i++)
{
	for(int j=n-1;j>=0;j--)
	{
		cout<<(i>>j&1)<<' ';
	}
	cout<<endl;
}

拆分树

代码：

#include <bits/stdc++.h>
using namespace std;

int ans[25];
int n;
void print(int n)
{
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
}

void dfs(int k,int s)
{
	for(int i=1;i<=s;i++)
	{
		if(i>=ans[k-1])
		{
			ans[k]=i;
			s-=i;
			if(s==0)
			{
				print(k);
			}
			else
			{
				dfs(k+1,s);
			}
			s+=i;
		}
	}
}

int main()
{
	cin>>n;
	dfs(1,n);
	return 0;
}

排列树

代码：

#include<bits/stdc++.h>
using namespace std;
int vis[25];//标记
int ans[25];//存储答案
int n;

void print()
{
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
}
void dfs(int k)//第k个数
{
	for(int i=1;i<=n;i++)//枚举第k个数的所有可能
	{
		if(vis[i]==0)//如果孩子合法
		{
			ans[k]=i;//记录答案
			vis[i]=1;//标记孩子
			if(k==n)//如果找到答案
			{
				print();//输出答案
			}
			else
			{
				dfs(k+1);//否则考虑下一个数
			}
			vis[i]=0;//回溯到前一状态
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
	return 0;
}

组合树

可以看出，排列树与组合树的唯一区别就在于一个孩子不等于祖先，一个孩子不等于父亲；

代码：

#include <bits/stdc++.h>
using namespace std;

int ans[25];
int n,r;

void print()
{
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
}

void dfs(int k)
{
	for(int i=1;i<=n;i++)
	{
		if(i>ans[k-1]) 
		{
			ans[k]=i;
			if(k>=r)
			{
				print();
			}
			else
			{
				dfs(k+1);
			}
		}
	}
}

int main()
{
	cin>>n>>r;
	dfs(1);
	return 0;
}

例题：

【例5.2】组合的输出

迷宫

LETTERS