演演算法總結--搜尋

宣告(疊甲)：鄙人水平有限，本文為作者的學習總結，僅供參考。

1. 搜尋介紹

搜尋演演算法包括深度優先搜尋（DFS）和廣度優先搜尋（BFS）這兩種，從起點開始，逐漸擴大尋找範圍，直到找到需要的答案為止。從時間複雜度來說這與一般的暴力列舉來說沒來太大的區別，這樣的話我們為什麼要使用搜尋演演算法，而不直接使用暴力法呢？首先，搜尋演演算法是暴力法一種優雅的寫法，即優雅的暴力，可以為我們的程式碼減少冗長的巢狀 for 迴圈。其次搜尋通過剪枝操作可以跳過一些無效狀態，降低問題規模，從而使效率比直接的列舉所有答案要高。

2. DFS 與 BFS 的區別

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.參考

程式碼隨想錄
洛谷搜尋演演算法推薦題庫
馬的遍歷的洛谷題解
本文到此結束，希望對您有所幫助。