搜索 深度优先搜索 DFS
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了搜索 深度优先搜索 DFS,现在分享给大家,供学习和参考。文章包含2031字,纯文字阅读大概需要6分钟。
教程信息
深度优先搜索 DFS
通过题目解题认识深度优先搜索DFS
题目来源:
https://www.luogu.com.cn/problem/P1605
题目内容:
一、问题的解空间
问题的解空间指的是一个问题可能存在的所有解的集合,通常是由基于分步计数原理和分类计数原理构成的树形图。深度优先搜索DFS和广度优先搜索BFS就是用不同的方式遍历问题的解空间,从而找到所期望的答案。
问题的解空间可能非常大,在某些情况下,甚至可能是无限大的,而且可能包含许多不可行或无效的解。而DFS和BFS与枚举最大的区别,就是在试探的过程中,可以更有针对性地进行优化,缩小解空间的范围。
如下图就是例题的部分解空间。
二、深度优先搜索
(一)核心思想
1、深度优先
深度优先的思想从一个起始节点开始,尽可能深地访问其相邻节点,直到到达一个没有未访问节点的节点为止。在搜索算法中,指通过函数递归的方法,不断向下、尽可能深地搜索解空间的每一条路径,并且判断当前路径构成的“可能解”是否是一个“正确解”。
2、回溯
在探索过程中,记录上一次搜索的位置(“存档”),一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。因此总是需要一个判断位置是否被访问过的数组。
(二)两种框架
int dfs(int k) { for (i = 1; i <= 选择种数; i++) if (满足条件) { 保存修改 if (到目的地) 输出解; else dfs(k + 1); 恢复修改 } }
int dfs(int k) { if (到目的地) 输出解; else for (i = 1; i <= 选择种数; i++) if (满足条件) { 保存结果; dfs(k + 1); 恢复修改 } }
(三)走迷宫代码
实现代码:
#include<bits/stdc++.h> using namespace std; int G[15][15]; //迷宫图 int d[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; //每一行表示一个方向偏移量,{0,1}往上,{0,-1}往下,{1,0}往右,{-1,0}往左 int n, m, t, nx, ny, ex, ey, zx, zy; //迷宫长和宽,障碍数,起点终点,障碍坐标 int countt = 0; //存储答案 void dfs(int x, int y) { if (x == ex && y == ey) { //如果走到终点 countt++; //方案数+1 return; } for (int i = 0; i < 4; i++) { //遍历四个方向 int xx = x + d[i][0], yy = y + d[i][1]; //下一个位置的坐标 if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && G[xx][yy] == 0) { //如果坐标合法 G[xx][yy] = 1; // 标记为访问过 dfs(xx, yy); // 从下一个位置开始再走,不断索引,只要索引到终结点,就算一条成功路径。 G[xx][yy] = 0; // 回溯 } } return; } int main() { cin >> n >> m >> t >> nx >> ny >> ex >> ey; G[nx][ny] = 1; //不能再访问起点了 for (int i = 0; i < t; i++) { cin >> zx >> zy; G[zx][zy] = 1; //不能再访问 } dfs(nx, ny); cout << countt; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供搜索 深度优先搜索 DFS的全部内容,希望教程文章能够帮你了解学习搜索 深度优先搜索 DFS,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-286.html