泉州暑假集训Day 5 && 6

c++

编程语言学习记录 c++

发布日期: 2023-07-28

文章字数: 723

阅读次数:

PS: This is a note.

深搜(DFS)和宽搜(BFS)

搜索算法

搜索算法是计算机程序设计中一种最基本、最常用的算法。

当我们面对一个程序设计问题时，如果能找到数学方法（如递推法、构造法）或者类似贪心、动态规划求最优值的方法时，那么对于这道题而言，已经基本解决。

如果没有找到行之有效的方法，搜索便成了唯一的选择。

搜索算法又被称为通用解题法，想不到正解的题目总是可以通过搜索算法来获取一部分分数(骗分)。搜索题也往往是普通选手和高手之间拉开差距的关键所在。
所以我们常说：**搜索不是万能的，没有搜索是万万不能的。**

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。

由于搜索策略的不同，搜索算法可以分为两种基本情况，即: 深度优先搜索和宽度优先搜索。

深搜和宽搜的区别

	深度优先搜索	宽度优先搜索
数据结构	栈	队列
使用场景	求可行解或全部解	求最优解
时间和空间	需要较少的空间,但容易超时,需要优化	能最快求得解,但需要与状态数成正比的空间

深度优先搜索(Depth-first-Search)

深搜的基本框架(回溯)

void dfs(int dep){
    if(当前状态==目标状态)
        输出解或者作计数、评价处理;
    else
        for(int i=1;i<=状态的扩展可能数;i++){
            if(第i种状态扩展可行){
                保存现场(断点,维护参数表);
                dfs(dep+1);
                恢复现场(回溯，回到上一个断点继续执行)
            }
        }
}

深搜例题

e.g. 全排列问题(洛谷P1706)

#include <bits/stdc++.h>
using namespace std;
int n,a[11],p[11];
void dfs(int t)
{
	if(t>n)
	{
		for(int i=1;i<=n;i++)
		{
			printf("%5d",a[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1;i<=n;i++)//每位都有n种可能
	{
		if(!p[i])	//如果i没被用过
		{
			a[t]=i;	//该位的数是i
			p[i]=1;	//i被用过了
			dfs(t+1);	//继续下一位
			p[i]=0;	//返回到上一位时，回溯
		}
	}
}
int main() {

	cin>>n;
	dfs(1);
	return 0;
}