查找演算法應用
1. c++中dfs是什麼意思
C++中的DFS是指深度優先搜索演算法。它是一種用於遍歷或搜索樹或圖的演算法。以下是關於DFS的詳細解釋：
基本概念：DFS是一種從樹的頂端開始，沿著樹的深度一直探索到最左邊的數據，然後回溯到上一個節點，繼續探索未訪問的分支，直到所有節點都被訪問為止的演算法。
搜索策略：以深度為第一標准進行搜索。即，演算法會盡可能深地探索每一個分支，直到達到葉節點或無法繼續為止，然後回溯到上一個節點，繼續探索其他未訪問的分支。
應用場景：DFS廣泛應用於各種領域，如路徑查找、連通性判斷、圖的遍歷等。在C++中，DFS通常通過遞歸或棧來實現。
實現方式：
- 遞歸實現：利用函數的遞歸調用，每次調用都深入一層，直到達到葉節點或無法繼續，然後回溯。
- 棧實現：使用棧數據結構來模擬遞歸過程，通過顯式地維護一個棧來記錄待訪問的節點，從而實現深度優先搜索。
DFS是一種重要的演算法思想，在解決許多問題時都能發揮重要作用。
2. 搜索演算法的應用案例
(1)題目：黑白棋游戲
黑白棋游戲的棋盤由4×4方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構成一個游戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對於給定的初始游戲狀態和目標游戲狀態，編程計算從初始游戲狀態變化到目標游戲狀態的最短著棋序列。
(2)分析
這題我們可以想到用深度優先搜索來做，但是如果下一步出現了以前的狀態怎麼辦？直接判斷時間復雜度的可能會有點大，這題的最優解法是用廣度優先搜索來做。我們就可以有初始狀態按照廣度優先搜索遍歷來擴展每一個點，這樣到達目標狀態的步數一定是最優的（步數的增加時單調的）。但問題是如果出現了重復的情況我們就必須要判重，但是樸素的判重是可以達到狀態數級別的，其實我們可以考慮用hash表來判重。
Hash表：思路是根據關鍵碼值進行直接訪問。也就是說把一個關鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間復雜度可以在O（1）的時間復雜度內搞定。對於這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態出現沒有，這樣可以在O（1）的時間復雜度內解決判重問題。
進一步考慮：從初始狀態到目標狀態，必定會產生很多無用的狀態，那還有什麼優化可以減少這時間復雜度？我們可以考慮把初始狀態和目標狀態一起擴展，這樣如果初始狀態的某個被擴展的點與目標狀態所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數和也就是答案。
上面的想法是雙向廣度優先搜索：
就像圖二一樣，多擴展了很多不必要的狀態。
從上面一題可以看到我們用到了兩種優化方法，即Hash表優化和雙向廣搜優化。一般的廣度優先搜索用這兩個優化就足以解決。
