首页 > 编程语言 >算法总结--搜索

算法总结--搜索

时间:2023-03-27 17:24:06浏览次数:56  
标签:point -- nf BFS int 算法 que ans 搜索

声明(叠甲):鄙人水平有限,本文为作者的学习总结,仅供参考。


1. 搜索介绍

搜索算法包括深度优先搜索(DFS)和广度优先搜索(BFS)这两种,从起点开始,逐渐扩大寻找范围,直到找到需要的答案为止。从时间复杂度来说这与一般的暴力枚举来说没来太大的区别,这样的话我们为什么要使用搜索算法,而不直接使用暴力法呢?首先,搜索算法是暴力法一种优雅的写法,即优雅的暴力,可以为我们的代码减少冗长的嵌套 for 循环。其次搜索通过剪枝操作可以跳过一些无效状态,降低问题规模,从而使效率比直接的枚举所有答案要高。


2. DFS 与 BFS 的区别

类别 DFS BFS
搜索类型 试探搜索 地毯搜索
所用的数据结构 栈(vector也是可以的) 队列
适用的题目 求方案总数 求最短路径
实现方法 一般结合回溯算法一同实现 将可行行方案放入队列,然后一一遍历

3. 举些栗子

3.1 BFS--马的遍历

题目描述

有一个 $ n * m $ 的棋盘,在某个点 $ (x, y) (x,y) $上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

这是一道经典 BFS 题,可说使模板题了,在解题前先介绍一下 BFS 的实现思路如下:

【1】 构建对应结构体与队列
【2】 初始化数据和初始点
【3】 根据初始点与遍历关系遍历其它符合要求的点
【4】 查询答案

根据 BFS 的实现思路可以容易的得到该题的代码如下

#include <bits/stdc++.h>
#define N_MAX 400
using namespace std;
int mp[N_MAX][N_MAX]; // mp[i][j] 表示马到(i,j)点所需的最少次数
int n,m,x,y;
// 定义 dx dy 便于运算
int dx[] = {-1,1,2,2,1,-1,-2,-2};
int dy[] = {-2,-2,-1,1,2,2,1,-1};
// [1] 定义数据结构体与duilie
struct point{
    int x,y; // 点的坐标
    int t;   // 马到该点的最少次数
};
queue<point> que;

int main()
{
    // [2] 初始化数据
    memset(mp,-1,sizeof(mp));
    cin >> n >> m >> x >> y;
    mp[x][y] = 0; // 初始点为 0

    // [3] 搜索
    que.push((point){x,y,mp[x][y]}); // 先向队列中压入初始点
    while(!que.empty())
    {
        // 从队列中一个一个的遍历
        point p = que.front();
        que.pop(); // 记得弹出
        // 寻找满足条件的点,并压入队列中
        for(int i = 0;i < 8;i++)
        {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            // 判断是否合法
			if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == -1)
			{
				mp[nx][ny] = p.t + 1;
            	que.push((point){nx,ny,mp[nx][ny]});
			} 	
        }
    }
    // 输出结果
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {    
            cout << mp[i][j] << " ";
        }
        cout << endl;
    }
        
    return 0;
}

3.2 BFS--奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 \(i\) 层楼(\(1 \le i \le N\))上有一个数字 \(K_i\)(\(0 \le K_i \le N\))。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: \(3, 3, 1, 2, 5\) 代表了 \(K_i\)(\(K_1=3\),\(K_2=3\),……),从 \(1\) 楼开始。在 \(1\) 楼,按“上”可以到 \(4\) 楼,按“下”是不起作用的,因为没有 \(-2\) 楼。那么,从 \(A\) 楼到 \(B\) 楼至少要按几次按钮呢?

这题也是一道 BFS 的模板题了,算是用于巩固了,具体 AC 代码如下

#include <bits/stdc++.h>
using namespace std;
#define N_MAX 201
struct point{
	int f;  // 所在层数
	int ki; // 拥有的数字
	int t;  // 需要按的次数 
};
queue<point> que;
int ans[N_MAX];
int n,a,b;
int k[N_MAX];

int main()
{
	memset(ans,-1,sizeof(ans));
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++)
	{
		cin >> k[i];
	}
	ans[a] = 0;
	// bfs
	que.push((point){a,k[a],ans[a]});
	while(!que.empty())
	{
		point p = que.front();
		que.pop();
		int nf = p.f + p.ki; // 上 
		if(nf <= n && ans[nf] == -1)
		{
			ans[nf] = p.t+1;
			que.push((point){nf,k[nf],ans[nf]});	
		}
		nf = p.f - p.ki;    // 下  
		if(nf >= 1 && ans[nf] == -1)
		{
			ans[nf] = p.t+1;
			que.push((point){nf,k[nf],ans[nf]});	
		}		
	}  
	cout << ans[b] << endl;
	return 0;
}

3.4 DFS--数的组合

题目描述

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

这是一到典型的 DFS 题,DFS 组要就是利用回溯算法进行解决,回溯的具体思路如下,其难点在于确定递归参数的确定

【1】 写递归出口(收果子)
【2】 循环遍历搜索,并进行剪枝优化
【3】 处理节点
【4】 递归
【5】 回溯,即取消处理节点时的朝左
该题代码如下:

class Solution {
public:
    vector<vector<int>> ret; // 用于存储最后的结果
    vector<int> path;       // 用于存储中间的结果
    
    void bnf(int st,int n,int k)
    {
        // 收果子 (中止条件)
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        // 循环,并进行剪枝优化
        for(int i = st;i <= n - k + path.size() + 1;++i)
        {
            // 处理节点
            path.push_back(i);
            // 递归
            bnf(i+1,n,k);
            // 回溯
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        bnf(1,n,k);
        return ret;
    }
};

4.参考

代码随想录
洛谷搜索算法推荐题库
马的遍历的洛谷题解
本文到此结束,希望对您有所帮助。

标签:point,--,nf,BFS,int,算法,que,ans,搜索
From: https://www.cnblogs.com/luokeIT/p/17262242.html

相关文章

  • SpringBoot多数据源(自定义注解,动态数据源,事务实现)
    一、数据库配置文件(这里用的是阿波罗配置中心,也可以是application.yml文件)#mysql本地数据源1spring.datasource.db1.driver-class-name=com.mysql.cj.jdbc.Driverspr......
  • 【原型设计工具】​​上海道宁为您提供Justinmind,助力您在几分钟内形成原型,并现场测试
     Justinmind是用于Web和应用程序的原型制作工具在几分钟内形成原型并在现场进行测试无需编写任何代码单击一下即可轻松在线获取您的设计并与整个团队共享享受......
  • 500报错:ReflectionException: There is no setter for property named 'sicon' in 'cl
    报错信息:"timestamp":"2023-03-27T09:07:50.958+00:00",出错原因:首先看报错信息中这么写到:"message":"nestedexceptionisorg.apache.ibatis.reflection.Reflecti......
  • python 实现 average pooling 和 max pooling
    pooling的主要作用1.首要作用:下采样,降维,去除冗余信息。同时扩大感受野,保留了featuremap的特征信息,降低参数量。2.实现非线性,一定程度上避免过拟合。3.可以实现特征......
  • 模块化-更新已经存在的模块的内容
    1.以BasicModule为例,更新BasicModule的部分内容必须要将更新的内容放在BasicModule的Classes文件中版本号+12.提交到BasicModule的远端仓库提交代码并打tag(注意......
  • MySQL数据库用户管理
     一、用户管理1.1新建用户CREATEUSER'用户名'@'来源地址'[IDENTIFIEDBY[PASSWORD]'密码'];‘用户名’:指定将创建的用户名‘来源地址’:指定新创建的用......
  • 单元测试
    单元测试Android开发中如何进行单元测试和UI测试?在Android开发中,单元测试和UI测试是非常重要的,可以保证代码的质量和稳定性。以下是Android开发中常用的测试框架......
  • Go接入kafka
    需要借助的库github.com/Shopify/sarama//kafka主要的库*github.com/bsm/sarama-cluster//kafka消费组生产者packageproducerimport( "fmt" "github.com/Ha......
  • 使用copilot生成vue响应式原理
    //生成vue的响应式原理functiondefineReactive(obj,key,val){//递归observe(val);//创建Dep实例constdep=newDep();Object.defineProperty(obj......
  • Haproxy集群
      一、Haproxy简介Haproxy 是一个使用C语言编写的自由及开放源代码软件,其提供高可用性、负载均衡,以及基于TCP和HTTP的应用程序代理。1.1Haproxy应用分析LVS......