网站备案登记,推广网站案例,东莞外贸企业做网站,猎头公司前十名有哪些深度优先搜索(DFS)
深度优先搜索就好比走迷宫, 不断顺着一条路走, 直到走不通为止, 然后回退到上一个路口再向另外的方向行走(走过的方向就不会再走了,又不是傻子, 知道走不通,还向走不通的方向走), 不断重复(试过所有路口, 状态转移), 重复直到找到唯一的一条合适的路径; DFS…深度优先搜索(DFS)
深度优先搜索就好比走迷宫, 不断顺着一条路走, 直到走不通为止, 然后回退到上一个路口再向另外的方向行走(走过的方向就不会再走了,又不是傻子, 知道走不通,还向走不通的方向走), 不断重复(试过所有路口, 状态转移), 重复直到找到唯一的一条合适的路径; DFS可以看做是二叉树的先序遍历, 多说无益; 直接上题;
例1: 给定a1, a2, a3,…an个数, 从中选出若干个数, 使他们的和恰好为K 输入: n4; a{1,2,4,7}; K13; 输出: 24713 分析: 当初我看到这道题, 就是懵逼状态, 唉, DFS还没搞清楚就开始做题, 很蠢, 不扯那些没用的, 回归主题: 从给出的例子来看, 既然我们要从1,2,4,7中选出若干个数, 那就可以暴力枚举, 循环列举出a集合的幂集, 找出满足条件的答案; 但是这种方法的复杂度让我瘆得慌, 复杂度为O(n^n), so, 这种做法就果断放弃, 从今天的主题来看势必要用到DFS来解决问题(我这不废话吗, 唉), 从DFS的定义来看就是状态转移, 这里的状态转移表示的是每个数都拥有两个选择的权利, 要么加, 要么不加, 就好比走迷宫有两条路, 要么朝左, 要么朝右, 你把这个过程想象走迷宫, 每种选择都对应着不同的走法, 总有一条路是对的(看成一棵长得像二叉树一样的迷宫), 因此复杂度为2的n次方, 相比前面的n的n次方下降了很多, 尽管下降了很多但是在实际应用需要做剪枝优化, 就题论事有如下代码:
#includeiostream
using namespace std;
int n4,a[4]{1,2,4,7},k13;
bool dfs(int i,int sum){if(in)return sumk;//满足条件然后进行回归if(dfs(i1,sum)) {//在交叉口做选择
// cout a[i]endl;
// 如果没加就不用输出a[i],忽略了这个问题 return true;}if(dfs(i1,suma[i])){cout a[i]endl;return true;}return false;
}
int main(){coutdfs(0,0)endl;return 0;
} 上述整个过程可看做二叉树的前序遍历, 当满足条件便回归 深度优化搜索总是从最开始的状态出发,遍历所有可能到达的状态, 由此可对所有产生的状态进行操作
例2: 这道题是深度优化搜索的一个很好例子, 拿来作为参考 分析: 以第一个题作为启示, 第一个题可看做单连通域进行遍历, 总共只在main函数中使用了一次dfs, 而这道题当遇到积水时就需要使用dfs, 一次dfs就能对相连的’w’进行遍历,直到一个连通域遍历完成, 如图总共有3个连通域, 多说无益看代码:
#includeiostream
using namespace std;
int N10,M12;
char field[10][12]{w.......ww.,.www....ww.,...w.....w.,.........w.,.........w.,wwww.....ww,www.......w,ww........w,ww........w,w..........};
void dfs(int x,int y){field[x][y].;for(int dx-1;dx1;dx){for(int dy-1;dy1;dy){//针对当前w的8个方向使用dfs, 直到一个连通域遍历完成int nxxdx,nyydy;if(0nxnxN0nynyMfield[nx][ny]w)//满足条件开始遍历dfs(nx,ny);}}return;
}
int main(){int res0;for(int i0;iN;i){for(int j0;jM;j){if(field[i][j]w){//针对整个地图使用dfsdfs(i,j);res;}}}coutresendl;
}每个格子至多被调用一次, 所以复杂度O(N*M) 总的来说, 深度优化搜索就是对图结构进行遍历(以二叉树的前序遍历的方式), 直到遇到符合条件的情况
