前言
前兩節課蒟蒻君給大家講解了dfs的基本用法，蒟蒻君來給大家講一下它的時間復雜度優化~
鋪墊一下
1.搜索樹和狀態
我們可以根據搜索狀態構建一張抽象的圖，圖上的一個節點就是一個狀態，而圖上的邊就是狀態之間轉移的關系，包括繼續dfs或者回溯，
搜索樹里每個節點上記錄的就是執行到這個狀態時的值，對于每個數，我們都有幾種選擇，都會使目前的狀態產生分支，
簡單來說，剪枝后的搜索樹每個狀態有k種選擇時，它就是一個完全k叉樹（不會的小伙伴可以把這句話當空氣），
2.舉個栗子
接下來蒟蒻君現編一道題…
- 題目
蒟蒻君今天想吃x斤食物（蒟蒻君是吃貨沒錯），現在有n盤食物，第i盤食物有a[i]斤，蒟蒻君想知道有幾種吃法， - 分析一下
對與每個食物，我們都有選和不選兩種選擇（即k=2），我們在每次搜索中都要嘗試這兩種選擇，達到條件計數器+1. - 植樹~
讓我們來看一下這道題的搜索樹叭（蒟蒻君畫得不咋地）
我們用S來記錄當前總斤數和，用N來記錄選擇的食物的個數，
- 代碼
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15; // n的最大值，這里設它為15
int x, n, sum; // 輸入資料
int res; // 總方案數
int a[MAX_N];
void dfs(int i, int N, int S) {
// 遞回終止條件：所有數都搜索完了（也可以是找到n盤食物了，同理）
if (i == x) {
if (N == n && S == sum) { // 如果食物數量和重量都符合要求，就把答案+1
++res;
}
return ;
}
dfs(i + 1, N, S); // 如果不選當前菜
dfs(i + 1, N + 1, S + a[i]); // 如果選當前菜
}
int main() {
cin >> x >> n >> sum;
for (int i = 0; i < x; ++i) {
cin >> a[i];
}
dfs(0, 0, 0); // 從編號為0的菜開始搜索，最開始有0個菜，重量和為0
cout << res << '\n';
return 0;
}
當前，目前的時間復雜度為O(2^n)，明顯有點太慢了，
一會我們會講到四種剪枝優化，其中有一些就是針對這種噠，
知識梳理
剪枝，顧名思義就是從搜索樹上剪掉一些沒用的子樹，讓時間復雜度降低，
一、可行性剪枝
還是剛才的問題，
當n=2的時候，如果當N=2時，已經選了2個數，再繼續選就是沒有意義了，所以我們可以直接減去這個搜索分支，也就是：
再比如，一旦現在的值已經>sum了，也沒必要繼續搜索了，
- 代碼
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15; // n的最大值，這里設它為15
int x, n, sum; // 輸入資料
int res; // 總方案數
int a[MAX_N];
void dfs(int i, int N, int S) {
if (N > n) { // 剪枝1
return ;
}
if (S > sum) { // 剪枝2
return ;
}
// 遞回終止條件：所有數都搜索完了（也可以是找到n盤食物了，同理）
if (i == x) {
if (N == n && S == sum) { // 如果食物數量和重量都符合要求，就把答案+1
++res;
}
return ;
}
dfs(i + 1, N, S); // 如果不選當前菜
dfs(i + 1, N + 1, S + a[i]); // 如果選當前菜
}
int main() {
cin >> x >> n >> sum;
for (int i = 0; i < x; ++i) {
cin >> a[i];
}
dfs(0, 0, 0); // 從編號為0的菜開始搜索，最開始有0個菜，重量和為0
cout << res << '\n';
return 0;
}
二、最優性剪枝
對于求最優解的問題，有些時候可以用最優性剪枝，
比如求解迷宮最短路徑類的問題，如果當前步數已經大于等于答案了，就可以停止搜索，
此外，在判斷是否有可行解的程序中，只要有一個解，后面的搜索就不用進行啦（可以使用exit(0)），這是最優性剪枝的一種特例，
- 代碼
這里就寫剪枝優化的代碼~
int res = 0x3f3f3f3f; // 答案
int n, m;
......
void dfs(......, int stp) { // stp表示當前步數
if (stp >= res) {
return ;
}
if (符合條件) { // 排除來不是最優解的情況后，此時stp肯定是目前的最優解
res = stp;
return ;
}
......
}
三、重復性剪枝
對于某些搜索方式，一個方案可能會被搜索多次，這樣是沒必要了，
還是那道題…
我們其實不需要像之前那樣每次dfs都把每個都列舉了，因為我們只關注最這串數的和，而不關注順序，所以我們可以使用重復性剪枝，
我們設定選出的數的下標是遞增的，所以我們可以設定一個變數表示上次列舉的下標，這次從上次+1開始列舉就不會有重復的了，
- 代碼
bool eaten[MAX_N]; // eaten[i]表示第i個食物是否被吃過
void dfs(int N, int S, int pos) {
...... // 判斷邊界 + 可行性剪枝
for (int i = pos; i <= n; ++i) {
if (!eaten[i]) { // 沒吃過就吃
eaten[i] = true;
dfs(N + 1, S + a[i], i + 1); // 下一個的位置在這個的后面
eaten[i] = false; // 回溯，把食物吐出來（蒟蒻君還可以繼續吃...）
}
}
}
四、奇偶性剪枝
大家先看一道題（上次農場里那幾只挑剔的小豬又登場了…）：
- 題目
農場主嫌這些小豬又懶又饞（豬豬不都是這樣嗎），決定給它們一個考驗，
他給豬豬們出了一個n * m的迷宮，其中有起點、終點、墻和平地，小豬豬們只能向上下左右走，不能爬墻（它們貌似也不會爬墻），
它們走每步需要一個小時的時間（因為它們實在是太胖了），到第T個小時時，農場主就會不耐煩，把豬糧送給隔壁的老母豬，
豬豬們很餓，想讓你判斷一下是否可以吃到豬糧，
起點：‘A’
終點：‘B’
平地：’.’
墻:’*’ - 分析
這里會的小伙伴可能會想到小學奧數證明題中的染色問題，其中的一個方法就是黑白染色，
如圖，每隔一個格子染成黑色，其余的為白色，
在這個圖中，每走一步就會變一次色，
我們還可以看出來，如果行數+列數為計數，當前格子就為黑色，否則為白色，
從A走到B要奇數次（即A、B兩格不同色），而T為偶數，或者要偶數次，而T為奇數，則可以剪枝，
剪枝例題
- 分析
這道題其實就是很簡單的dfs+剪枝，別的難點都沒用到（蒟蒻君好不容易挑噠），
本題思路分為以下幾步：
- 預處理所有木棍的總長度，保證列舉答案的值能被總長度整除，
- 每根木棍的長度可用hash存盤，預處理最長的和最短的木棍的長度，dfs時從最大長度到最小長度列舉，
- 記錄當前長度，下次dfs從當前長度-1來列舉（重復性剪枝），
- 若某組拼接不成立，且此時已拼接的長度為0或當前已拼接的長度與剛才列舉的長度之和為最終列舉的答案時，則可直接跳出回圈（可行性剪枝），
- 代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 70;
int n;
int res;
int maxn, minn = N;
int box[N]; // step2
void dfs(int pre, int sum, int x, int y) {
if (pre == 0) { // step4
cout << x << '\n';
exit(0);
}
if (sum == x) { // step3
dfs(pre - 1, 0, x, maxn);
return ;
}
for (int i = y; i >= minn; --i) { // step2 & step3
if (box[i] > 0 && i + sum <= x) {
--box[i];
dfs(pre, sum + i, x, i);
++box[i]; // 回溯
if (sum == 0 || sum + i == x) { // step4
break;
}
}
}
}
int main() {
cin >> n;
while (n--) {
int t;
cin >> t;
if (t > 50) { // 過濾
continue;
}
++box[t];
res += t;
maxn = max(maxn, t); // step1
minn = min(minn, t);
}
int en = res >> 1; // 由于res一直在改變，所以需要在回圈前定義一個變數存盤
for (int i = maxn; i <= en; ++i) {
if (res % i == 0) {
dfs(res / i, 0, i, maxn);
}
}
cout << res << '\n';
return 0;
}
dfs的課程到此結束，接下來蒟蒻君將為大家講解bfs~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261812.html
標籤：其他