搜索算法講解

深度優先搜索-DFS

P1219 [USACO1.5] 八皇后 Checker Challenge

一個如下的 $6\times 6$ 的跳棋棋盤，有六個棋子被放置在棋盤上，使得每行、每列有且只有一個，每條對角線（包括兩條主對角線的所有平行線）上至多有一個棋子。

上面的布局可以用序列 $246135$ 來描述，第 $i$ 個數字表示在第 $i$ 行的相應位置有一個棋子，如下：

行號 $123456$

列號 $246135$

這只是棋子放置的一個解。請編一個程序找出所有棋子放置的解。
并把它們以上面的序列方法輸出，解按字典順序排列。
請輸出前 $3$ 個解。最后一行是解的總個數。

思路

首先思考暴力枚舉解法，注意到每一行只能放一個，那就可以一行一行枚舉，然后判斷是否合法即可。

然后會發現暴力枚舉中有很多不必要的操作，比如說我們枚舉到第3行把棋子放在第3列，發現這個位置是非法的，難么其實我們就沒有必要再往下面的層去枚舉了，應該直接把第3行的棋子放到后面的列繼續枚舉即可。

總結一下現在的方法：就是一行一行的放棋子，如果在該行放置的棋子是合法的，就繼續放下一行的；如果枚舉是非法的，就不用繼續枚舉下一行了，而是更換當前行的棋子。

這種方式稱為回溯算法，我們這里使用深度優先搜索來實現。

DFS板子

void dfs(int k) { // k代表遞歸層數，或者說要填第幾個空if (所有空已經填完了) {// 判斷最優解 / 記錄答案return;}for (枚舉這個空能填的選項) {if (這個選項是合法的) {占位dfs(k + 1) // 下一層遞歸取消占位}}
}

接下來還有個難點，就是如何判斷選項合法。首先行上一定不會沖突，因為我們是一行一行枚舉的，每行只能放一個；然后列的話我們可以創建一個名如used_col的bool列表（當然int列表也可以）去存每一行的使用狀態，為true就是用過了，就不能再該行再次使用，false就是沒用過，就可以在該行使用；然后對角線就比較麻煩，而且對角線有兩種，一種是從左往右上升，一種是從左往右下降的，都要判斷清楚。

我們可以發現，從左往右上升的對角線上的點有一個特點，就是x+y的值都一樣，并且除了該對角線上的點都一定不滿足這個條件；另一種對角線則是x-y的值都一樣。這樣我們就可以開2個數組去記錄對角線的使用狀態，首先看x+y為定值的對角線，我們就只需要用數組記錄這個定值對應的使用情況即可，就是開一個bool數組，定值對應數組下標即可；然后看x-y為定值的對角線，思路和前者相同，但是要注意定值可能為負數，就不能作為數組下標，那么就給定值加上一個較大（比x-y的最小值的絕對值大）的固定的整數再作為數組下標即可。

解題代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 100;LL n, ans = 0;
LL arr[N], used_col[N], used_1[N], used_2[N]; void dfs(int k) {if (k > n) {ans++;if (ans <= 3) {for (LL i = 1; i <= n; i++) cout << arr[i] << " ";cout << endl;}return;	}for (LL i = 1; i <= n; i++) {if (!used_col[i] && !used_1[k + i] && !used_2[k - i + 20]) {arr[k] = i, used_col[i] = 1, used_1[k + i] = 1, used_2[k - i + 20] = 1; // 占位dfs(k + 1); // 遞歸下一層used_col[i] = 0, used_1[k + i] = 0, used_2[k - i + 20] = 0; // 取消占位}}
}int main() {cin >> n;dfs(1);cout << ans;return 0;
}

廣度優先搜索-BFS

深度優先搜索會優先考慮搜索的深度。形象點說，就是不找到一個答案不回頭。當答案在整棵解答樹中比較稀疏時，深度優先搜索可能會先陷人過深的情況，一時半會兒找不到解。有時候需要解決連通性、最短路問題時，可以考慮使用廣度優先搜索。

P1443 馬的遍歷

有一個 $n\times m$ 的棋盤，在某個點 $(x,y)$ 上有一個馬，要求你計算出馬到達棋盤上任意一個點最少要走幾步。

思路

這題拿dfs做的話很難寫，因為他沒有一層一層的體現。這道題適合的方法是bfs。

廣度優先搜索會優先考慮每種狀態的和初始狀態的距離，形象點說，與初始狀態越接近的情況會優先考慮。再具體一點：每個時刻要做的事情就是從上個時刻每個狀態擴展出新的狀態。

(開始在圖上模擬)

當輸入是 4 4 1 1時，擴展方向如圖(a)。

廣度優先搜索使用隊列實現：先將初始狀態加人到空的隊列中，然后每次取出隊首，找出隊首所能轉移到的狀態，再將其壓入隊列；如此反復，直到隊列為空。這樣就能保證一個狀態在被訪問的時候一定是采用的最短路徑。

當輸入是4 4 1 1時，隊列變化如圖(b)。

BFS板子

Q.push(初始狀態); // 將初始狀態入隊
while (!Q.empty()) {State u = Q.front(); // 取出隊首Q.pop(); // 出隊for (枚舉所有可擴展狀態) // 找到u的所有可達狀態vif (是合法的) // v需要滿足某些條件，如未訪問過、未在隊內等Q.push(v); // 入隊（同時可能需要維護某些信息）}

就本題而言，先建立一個結構體數組用于存儲擴展的結點。先讓起點人隊，然后在隊列取狀態逐個擴展。容易被證明每個點被擴展到時一定是最少步數，這里對應了上面說的與初始狀態越接近的情況會優先考慮。又因為每個點只被擴展了一次，所以以復合度是O（mn）。

解題代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;struct coord {int x, y;
};queue<coord> Q; LL n, m, x, y, ans[410][410];
LL movee[8][2] = {{2, 1}, {-2, -1}, {1, 2}, {-1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {1, -2}};int main() {memset(ans, -1, sizeof(ans));cin >> n >> m >> x >> y;ans[x][y] = 0;Q.push((coord){x, y});while (!Q.empty()) {coord u = Q.front();LL x = u.x, y = u.y;Q.pop();for (LL i = 0; i < 8; i++) {LL xx = x + movee[i][0], yy = y + movee[i][1];if (xx < 1 || xx > n || yy < 1 || yy > m || ans[xx][yy] != -1) continue;Q.push((coord){xx, yy});ans[xx][yy] = ans[x][y] + 1;}}for (LL i = 1; i <= n; i++, puts("")) {for (LL j = 1; j <= m; j++) {cout << ans[i][j] << " ";}}return 0;
}

總結

對于同一個模型，無論使用dfs還是bfs，其解答樹是一樣的，只是搜索順序不一樣。所以通常能用dfs寫的都能用bfs寫，反之也可以，只是寫起來的復雜程度可能不一。

同樣是尋找目標解，dfs尋找操作步驟字典序最小的解，而bfs可以找到步驟最小的解。需要根據題目的性質來決定使用什么搜索算法。