AKSZ-DFS
2024-05-19 14:04:56
发布于:广东
13阅读
0回复
0点赞
深度优先搜索
排列组合
加法原理:加步骤
乘法原理:乘步骤
排列:排列是指从给定的一组元素中,按照一定的顺序选择部分或全部元素所形成的线性排列(位置不同算不同)
公式:
组合:组合是指从给定的一组元素中,选择部分或全部元素所形成的组合,不考虑元素的顺序(位置不同算同)
公式:
回溯
以下为排列输出
#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[20], vis[20];
void dfs(int x){
if(x == n){
for(int i = 1; i <= n; i++){
cout << a[i] << " ";
}
cout << endl;
return;
}
for(int i = 1; i <= n; i++){
if(!vis[i]){ //回溯
vis[i] = 1;
a[x + 1] = i;
dfs(x + 1);
vis[i] = 0;
}
}
}
int main(){
cin >> n;
dfs(0);
return 0;
}
剪枝
可以剪掉一些状态,避免重复
减少搜索量
类型
可行性剪枝:得不到答案的去掉
最优性简直:更坏的去掉
连通性问题
走迷宫
八皇后
全部评论 1
少了连通性判断 和 八皇后 以及排列组合的代码实现
2024-05-15 来自 广东
0
有帮助,赞一个