搜索
DFS
就是通过递归来搜索,枚举所有情况来求解。
搜索相对于多个for循环嵌套来说肯定效率更高,在数据会很大时更容易实现,但有时避免不了TLE,所以需要进行优化:
剪枝
1.最优性剪枝 再求解时如果当前情况比已知的解差,或无法优于已知解,然后return,所以就可以先搜索容易成为最优解的方案,避免去搜索较差的解。
2.可行性剪枝 就是当前情况不可行就return。
记忆化搜索
就是将已经计算出来的结果保存起来,当之后的计算用到的时候直接取出结果,避免重复运算,因此极大的提高了效率。
例题:
Luogu 1706 全排列问题
题目描述
按照字典序输出自然数1到n所有不重复的排列,即n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
注释及代码:
#include<bits/stdc++.h>
using namespace std;
int n;
bool st[10];//标记每个数是否用过
int path[10];//用来记录答案
void dfs(int step)
{
if(step==n+1)//有n个数时输出
{
for(int i=1;i<=n;i++)
{
cout<<setw(5)<<path[i];//setw(5)能输出时每个数的长度为5;
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(st[i]==0)//如果没被用过
{
st[i]=1;//先标记一下,防止重复
path[step]=i;//记录答案
dfs(step+1);//进入下一次递归
st[i]=0;//再把它标记为未被用,也就是回溯操作
}
}
}
int main()
{
cin>>n;
dfs(1);
}
以上为通过搜索实现的代码,但强大的c++有个next_permutation函数,它能把当前的排列直接变成下一个字典序,但仅在全排列中有用,以下是其应用:
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) a[i]=i;
do{
for(int i=1;i<=n;i++) cout<<setw(5)<<a[i];
cout<<endl;
}while(next_permutation(a+1,a+n+1));
}
标签:剪枝,排列,int,7.19,搜索,include
From: https://www.cnblogs.com/Glw-/p/17566610.html