算法之------搜索篇
生活随笔
收集整理的這篇文章主要介紹了
算法之------搜索篇
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
搜索
- 前言
- 深度優先搜素
- 如何搜索
- 迭代加深
- 加成序列
- 導彈防御系統
- BFS 變形
- 雙端隊列BFS
- 優先隊列BFS
- 雙向BFS
- 噩夢
- 字串變換
前言
人人都說搜素搜素有手就行，我聽起來啥感覺自己沒手呢！
在看這個前言之前，讀者應該學過基本的算法和數據結構了。
通過這個題目來進行講解生日蛋糕 下邊附有代碼：
有一篇文章將，領悟了二叉樹的前、中和后序遍歷后你就能理解搜索這個東西了。那么我們就依據這個來進行討論一下。 在搜索的時候我們知道，搜索的狀態 搜索樹就是一顆多叉樹 ， 當前節點的所有決策就是該節點節點的孩子。 因為二叉樹只有左右兩個孩子。 下面這個dfs 其實就是前序遍歷的變形。 二叉樹的前序遍歷是這樣:
void dfs( BiTree T){ if(T){ vist(T); if(T->lchild) dfs(T->lchild); if(T->rchild) dfs(T->child); } }// 可能感覺不太想，不過我們修改一下。 void dfs( BiTree T){ if(T){ vist(T); for(int i = 0 ; i < 2 ; ++i){ if(i == 0 && T->lchild) dfs(T->lchild);if(i ==1 && T->rchild) dfs(T->rchild); } } }之所以我們不寫成下面的形式是因為，1是二叉樹的下一個狀態是已知的。2是二叉樹直接通過左右孩子dfs即可，不用通過遍歷來引出狀態。3是同一個節點訪問的結果是一樣的所有訪問一次就好。
還有一個問題是什么時候需要恢復現場什么時候不用呢?
好比下邊這個代碼我們在dfs結束后不需要恢復現場，而且也沒有必要恢復現場。我們的的每一個路徑上的節點都是相互獨立的。 而有些題目需要就好比八皇后或者圖的最短路徑等。我們在遍歷的時候以這個節點開始去遍歷的點，我們通過別的節點也能到達，那么如果我們不恢復，那么別人就無法訪問了。
判斷是否DFS是否需要恢復現場
代碼：
深度優先搜素
如何搜索
這是最重要的一步，也就是說我們要以什么樣的順序搜索才能不重不漏的將每一個情況都能枚舉到。只有先做到這一步才能想著如何剪枝等優化技巧。
下面以一道題來進行說明。
蟲食算
題目大意：
題目是讓我們對每一個字母進行賦值，使得符合該加法等式。
解題思路：
就是爆搜。重點是如何進行搜索，即如何對每一個字母進行賦值所有的情況。首先第一點我們可以規定一個搜索順序，我們可以對字母進行編號，而編號的話我們可以按照從右往左依次對字母進行編號。而因為我們這樣編號的話那么是不符合字母表順序的因此我們可以用一個數組q來存下這個映射關系。然后我們從第一個字母開始進行遍歷 ， 在每一次中字母有 n 種選擇，在這n種中選出沒有被挑選的。
代碼：
#include<iostream> #include<algorithm> #include<cstring>using namespace std;const int N = 30; char g[N][N]; int st[N] , path[N] , q[N]; int n ; bool check(){// 遍歷每一列for(int i = n - 1 , t = 0; ~i ; --i){int a = g[0][i] - 'A' , b = g[1][i] - 'A' , c = g[2][i] - 'A'; // 獲取字母在序列中的位置if(path[a] != - 1 && path[b] != -1 && path[c] != -1){a= path[a] , b = path[b] , c = path[c];if(t != -1){ // 前一列是確定的了if((a + b + t) % n != c)return false;if(!i && a + b >= n)return false; // 最高位t = (a + b + t) / n; // 當t 確定了 那么這個t的進位再能確定}else{if( (a + b ) % n != c && (a + b + 1) % n != c)return false;if(!i && a + b >= n)return false;}}else t = - 1 ;}return true; }// 這個u 第幾個字母，所以是依次對字母進行賦值 bool dfs(int u ) {if(u == n )return true;//沒一個path 位置遍歷 n 中 可能 ， 那每一個為值為一個字母的值// 所以就相當于對每一個字母符 n 個值for(int i = 0 ; i < n ; ++i){if(!st[i]){st[i] = true;path[q[u]] = i; // 找到u 位置if(check() && dfs(u + 1))return true;st[i] = false;path[q[u]] = -1;}}return false; } int main(){scanf("%d",&n);for(int i = 0 ; i < 3 ; ++i)scanf("%s",g[i]);for(int i = n - 1 , k = 0 ; ~i ; -- i)for(int j = 0 ; j < 3 ; ++j){int x = g[j][i] - 'A';if(!st[x]){st[x] = true;q[k++] = x;}}memset(path , -1 , sizeof path);memset(st , 0 , sizeof st);dfs(0);for(int i = 0 ; i < n ; ++i)cout<<path[i] << " ";return 0; }迭代加深
加成序列
這個迭代深度就有點想 ，答案解的長度。
加成序列
解題思路：
看到最短的一個解，首先想到的應該都是BFS不過這題不好用BFS ， 因此我們可以采用DFS中的迭代加深的方法。 其中迭代深度就是求解序列的長度。在沒一次dfs中我們的狀態是 當前要填的空，和序列的長度。 搜索結束是當 填的空已經為序列長度了就返回 ， 當序列最后一個為n時（條件）返回true ，否則返回false 。 當前這個空 由條件 知 我們可選的集合 會前邊 數兩兩想加的和 。同時這個和我們要滿足比前一個大 ， 同時不能大于n 。 在這里我們可以利用一個bool 數組來進行剪枝 ， 避免對 和 一樣的進行搜索。
代碼：
#include<iostream> #include<algorithm> #include<queue> using namespace std;const int N = 110;int n ; int path[N];bool dfs(int u, int depth){if(u == depth) return path[u-1] == n;bool st[N] = {false};for(int i = u - 1 ; i >=0 ; --i)for(int j = i ; j >= 0 ; --j){int s = path[i] + path[j];if(s > path[u-1] && s <= n && !st[s]){st[s] = true;path[u] = s;if(dfs(u+1 , depth)) return true;}}return false; }int main(){while(cin>> n , n){int depth = 1;path[0] = 1 ;while(!dfs(1 , depth)) depth++;for(int i = 0 ; i < depth ; ++i)cout<<path[i]<< " ";cout<<endl;}return 0; }導彈防御系統
- 小知識：對于DFS來求最短的問題我們一般有兩個思路 ， 一個是定義一個全局變量然后更新，二就是迭代加深
導彈防御系統
解題思路：
我們的搜索順序就是依次遍歷每一個數字的情況，而每一個數字都有兩種選擇，一個是上升，一個是下降。不過在兩個序列中又有很多個上升或者下降序列。這會導致我們搜索空間太大，不過我們由一個性質類似單調隊列的思路，我們在選上升序列的時候選擇第一個小于的就好，因為當這個數x加入后有一個序列的下一個數一定是x結尾這個是固定的了，不過其余序列的結尾是變得，我們要想達到最優的情況，那么選擇一個里其最近的一個小于它的是最優的。下降序列同理。
關鍵點：
代碼：
```cpp #include<iostream> #include<algorithm>using namespace std;const int N = 51;int n ; int h[N] , up[N] , down[N];bool dfs(int depth , int u , int su , int sd){if(su + sd > depth )return false;if(u == n)return true;bool flag = false;for(int i = 0; i < su ; ++i){if(up[i] < h[u]){int t = up[i];up[i] = h[u];if(dfs(depth , u + 1 , su , sd))return true;up[i] = t;flag = true;break;}}if(!flag){up[su] = h[u];if(dfs(depth , u + 1 , su + 1 , sd))return true;}flag = false;for(int i = 0; i < sd ; ++i){if(down[i] > h[u]){int t = down[i];down[i] = h[u];if(dfs(depth , u + 1 , su , sd))return true;down[i] = t;flag = true;break;}}if(!flag){down[sd] = h[u]; // 從0開始存if(dfs(depth , u + 1 , su , sd + 1))return true;}return false; }int main(){while(cin>>n , n){for(int i = 0 ; i < n ; ++i)scanf("%d",&h[i]);int depth = 1 ;while(!dfs(depth , 0 , 0 , 0))depth++;cout<<depth<<endl;}return 0; } # 深度搜索（BFS）## 權值相同的多源最短路問題 [矩陣距離](https://www.acwing.com/problem/content/175/)問題描述： >問題是讓我們求出 ， 每個數字到最近的1的曼哈頓距離。解題思路： > 該題可以轉化為最短路問題 ， 只不過邊的權重都為1 。 邊指的是相鄰點才連邊。由于邊權都相同，那么我們就可以用BFS來求出最短路，這個就相當于一個簡化版的dijkstra算法，隊頭一定是最小的節點。 由于這題是一個多源最短路問題，我們不可能遍歷每一個節點。這題的巧妙之處是利用寬搜的性質，先將距離為0的點放入隊列中 ，然后依次拓展， 那么我們就可以在O（n）的時間內解出。關鍵問題：1. 如何記錄距離：一般BFS我們都會用一個數組(dist)來存儲距離 ， 同時 這個數組還可以用來記錄這個節點是否被訪問過。代碼：```cpp #include<stdio.h> #include<iostream> #include<algorithm> #include<queue> #include<cstring>using namespace std;typedef pair<int , int >PII;const int N = 1000; int g[N][N] , n , m; int dist[N][N];queue<PII>q;void bfs(){int dx[4] = { 1, -1 , 0 , 0 } , dy[4] = { 0,0,1,-1};while(q.size()){auto t = q.front();q.pop();for(int i = 0 ; i < 4 ; ++i){int x = t.first + dx[i] , y = t.second + dy[i];if(x < 0 || x >= n || y >= m ||y < 0)continue;if(dist[x][y] == -1){dist[x][y] = dist[t.first][t.second] + 1;q.push({x,y});}}}}int main(){memset(dist , -1 , sizeof(dist));cin>>n>>m;getchar();for(int i = 0 ; i < n; ++i){ for(int j = 0 ; j < m ; ++j){char ch;ch = getchar();g[i][j] = ch - '0';if(g[i][j] == 1)dist[i][j] = 0 , q.push({i , j});}getchar();}bfs();for(int i = 0 ;i < n ; ++i){for(int j = 0 ; j < m ; ++j)cout<<dist[i][j] <<" ";cout<<endl;}return 0; }BFS 變形
雙端隊列BFS
在最基本的廣度優先搜索中，每次沿著分支的擴展都記為“一步”，我們通過逐層搜索，解決了求從起始狀態到每 的最少步數的問題。這其實等價于在一張邊視均為1的圖上執行廣度優先遍歷，求出每個點相對于起點的最短距離(層次)。在第021節中我們曾討論過這個問題，并得到了“隊列中的狀態的層數滿足兩段性和單調性”的結論。從而我們可以知道，每個狀態在第一次被訪問并入隊時，計算出的步數即為所求
然而，如果圖上的邊權不全是1呢？換句話說，如果每次擴展都有各自不同的“代價“ ， 我們相求出起始狀態到每一個轉態的最小代價？ 下面通過一題來解決0和1的時候
電路維修
參考：出處
小技巧：
代碼：
#include<stdio.h> #include<algorithm> #include<iostream> #include<cstring> #include<deque>using namespace std;const int N = 501; typedef pair<int ,int > PII;int n,m; char g[N][N]; int d[N][N] ;int bfs(){memset(d, 0x3f , sizeof(d));deque<PII> dq;dq.push_back({0,0});d[0][0] = 0;int dx[4] = {-1 , -1 , 1,1} , dy[4] = {-1,1,1,-1 }; // 坐標的偏移量int ix[4] = {-1,-1,0,0} , iy[4] = {-1,0,0,-1}; // 找到該坐標對應的字符的位置char cs[] = "\\/\\/"; // 正確的字符位置while(dq.size()){auto t = dq.front();dq.pop_front();int x = t.first , y = t.second;for(int i = 0 ; i < 4 ; ++i){int xx = x + dx[i] , yy = y + dy[i];if(xx >=0 && xx <= n && yy >=0 && yy <= m ){int a = x + ix[i] , b = y + iy[i];int w = 0 ;if(g[a][b] != cs[i]) w = 1 ;if(d[xx][yy] > d[x][y] + w){d[xx][yy] = d[x][y] + w;if(w) dq.push_back({xx,yy});else dq.push_front({xx,yy});}}}}if(d[n][m] == 0x3f3f3f3f)return -1;else return d[n][m];}int main(){int t ;cin>>t;while(t--){cin>>n>>m;for(int i = 0 ; i < n ; ++i)scanf("%s",g[i]);int ans = bfs() ;if(ans == -1) cout<<"NO SOLUTION\n";else printf("%d\n",ans);}return 0; }優先隊列BFS
相對于上一個問題，對于更加普遍的情況，也就是每次擴展的代價是不一樣的，求出初始狀態到每一個狀態的最小代價。就相當在一張帶權圖上求出起點到每一個點的最短路。那么這種情況我們就可以進行廣搜了。下面以一道題來舉例。
裝滿的油箱
題目大意：
題目就是求出從開始城市到終點城市的最小花費。
解題思路：
和最短路不一樣的是，這里油的數量是在變化的。 面對這種情況我們可以將城市與油量拆分成一個點對<城市，當前剩余油量> 通過這個點對來進行深搜。我們用一個二維數組dist[N][C]來記錄最小花費。因此我們最終要求得急速dist[S][0] -- > dist[E][0] 的最小代價。為了方便建立優先隊列，我們會以 代價也放入隊列中，每次去出代價最少的進行擴展。對于每一個狀態有兩個可以進行轉移的狀態， 一 是 (如果加一升油沒滿)就加一升油 ， 二、是遍歷所有能去的城市。 因此我們需要建圖。
代碼：
#include<cstring> #include<iostream> #include<queue> #include<algorithm> #include<stdio.h>using namespace std;const int N = 1010, C = 110, M = 20010;struct ver{int d , u , c;bool operator < (const ver & a)const{return d > a.d;} };int h[N] , E[M] , W[M] , ne[M] , tot; int price[N] ; bool st[N][C]; int dist[N][C]; int n, m ;void add(int u , int v ,int w){E[tot] = v , W[tot] = w , ne[tot] = h[u] , h[u] = tot++; }int bfs(int s , int e, int cab){priority_queue<ver> heap;heap.push({0 , s , 0});memset(dist , 0x3f , sizeof dist);memset(st , false , sizeof st);dist[s][0] = 0;while(heap.size()){auto t = heap.top();heap.pop();if(t.u == e) return t.d; // 到達終點城市if(st[t.u][t.c])continue; // 訪問過了 ， 避免重復訪問st[t.u][t.c] = true;// 加一升油if(t.c < cab){if(dist[t.u][t.c + 1 ] > t.d + price[t.u]){dist[t.u][t.c + 1] = t.d + price[t.u];heap.push({dist[t.u][t.c + 1] , t.u , t.c + 1});}}// 遍歷能走的邊for(int i = h[t.u] ; ~i ; i = ne[i]){int y = E[i];if(t.c >= W[i]){ // 剩余的油能走這條邊if(dist[y][t.c - W[i]] > t.d){dist[y][t.c - W[i]] = t.d;heap.push({dist[y][t.c - W[i]] , y , t.c - W[i]});}} }}return -1; }int main(){memset(h , -1 , sizeof h);scanf("%d%d", &n , &m);for(int i = 0 ; i < n ;++i )scanf("%d", &price[i]);for(int i = 0 ; i < m ;++i){int u , v, w;scanf("%d%d%d",&u, & v, & w);add(u,v,w) , add(v,u,w);}int query;scanf("%d" ,&query);while(query --){int c, s ,e;scanf("%d%d%d",&c ,&s, &e);int ans = bfs(s,e,c);if(ans == -1) cout<<"impossible\n";else cout<<ans<<endl;}return 0; }雙向BFS
基本思路：
我們只需要從起始狀態、目標狀態分別開始，兩邊輪流進行 ， 每次各次擴展，當兩邊各自有一個狀態在記錄數組中發生重復時，就說明這兩個搜索過程相遇了。
如何實現的我們以下邊這一題來講解
噩夢
噩夢
題目大意：
題目是讓我們求男孩和女孩是否能相遇，如果能相遇求出最短時間
解題思路：
我們各自對男孩和女孩進行bfs ， 如果 記錄數組中有交集 就說明能相遇并返回當前所用時間。
關鍵點:
代碼：
#include<stdio.h> #include<queue> #include<iostream> #include<cstring>using namespace std;typedef pair<int, int>PII;const int N = 800;char g[N][N]; PII ghost[2] , boy , girl; int st[N][N]; int dx[4] = { 1,-1,0,0} , dy[4] = { 0,0,1,-1}; int m ,n;bool check(int x , int y , int tm){if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 'X')return false;for(int i = 0 ; i < 2 ; ++i)if(abs(x - ghost[i].first) + abs(y - ghost[i].second) <= 2 * tm) return false;return true; }int bfs(){memset(st , 0 , sizeof(st));memset(st, 0, sizeof st);int cnt = 0;PII boy, girl;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )if (g[i][j] == 'M') boy = {i, j};else if (g[i][j] == 'G') girl = {i, j};else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};queue<PII> qb, qg;qb.push(boy);qg.push(girl);int step = 0;while(qb.size() || qg.size()){step ++ ;for(int i = 0 ; i < 3 ; ++i)for(int j = 0 , len = qb.size(); j < len ; ++j){auto t = qb.front();qb.pop();int x = t.first , y = t.second;if(!check(x,y , step))continue;for(int k = 0 ; k < 4 ; ++k){int xx = x + dx[k] , yy = y + dy[k] ; if(!check(xx,yy , step))continue;if(st[xx][yy] == 2) return step;else if(!st[xx][yy]){ st[xx][yy] = 1 ;qb.push({xx,yy});}}}for(int i = 0 ; i < 1 ; ++i)for(int j = 0 , len = qg.size() ; j < len ; ++j){auto t = qg.front();qg.pop();int x = t.first , y = t.second;if(!check(x,y,step))continue;for(int k = 0 ; k < 4 ; ++k){int xx = x + dx[k] , yy = y + dy[k] ; if(!check(xx,yy , step))continue;if(st[xx][yy] == 1) return step;else if(!st[xx][yy]){st[xx][yy] = 2 ;qg.push({xx,yy});}}}}return -1;}int main(){int T ;scanf("%d" ,&T);while(T--){scanf("%d%d" , &n , &m);for(int i = 0 ; i < n; ++i)scanf("%s" , g[i]);printf("%d\n" , bfs());}return 0; }字串變換
子串變換
題目大意：
題目給了起始字符和終止字符和變換規則，讓我們求出10步以內能否從起始狀態變換到終止狀態。
解題思路：
我們從起始和終止狀態兩邊進行BFS ， 如果它們在某一層有相交的那么就說明能變化。 注意的點：因為規則只能轉換一部分字符，因此，對于沒一個都是擴展一層，不是多層也不是單個節點。
關鍵點:
代碼：
#include<iostream> #include<queue> #include<string> #include<unordered_map>using namespace std;const int N = 6; string A,B; string a[N] , b[N]; int n;int extend(queue<string>&qa, unordered_map<string,int> &da , unordered_map<string,int> & db ,string a[N] , string b[N]){int d = da[qa.front()];while(qa.size() && d == da[qa.front()]){auto t = qa.front();qa.pop();for(int i = 0 ; i < n ; ++i)for(int j = 0 ; j < t.size() ; ++j){if(t.substr(j , a[i].size()) == a[i]){string r = t.substr(0 , j ) + b[i] + t.substr(j + a[i].size());if(db.count(r)) return da[t] + db[r] + 1;if(da.count(r)) continue;da[r] = da[t] + 1;qa.push(r);}}}return 11; }int bfs(){if(A == B )return 0;queue<string>qa,qb;unordered_map<string,int>da,db;da[A] = db[B] = 0;qa.push(A) , qb.push(B);int step = 0 , t;while(qa.size() && qb.size()){if(qa.size() < qb.size()) t = extend(qa,da,db,a,b);else t =extend(qb , db,da, b,a);if(t <= 10)return t;if(++ step == 10)return -1;}return -1; }int main(){cin>>A>>B;while(cin>>a[n]>>b[n]) n++;int ans = bfs();if(ans == -1)puts("NO ANSWER!");else cout<<ans<<endl;return 0;}總結
以上是生活随笔為你收集整理的算法之------搜索篇的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 一般项目中是如何调bug的 ------
- 下一篇： 高阶数据结构