owned this note   changed a year ago  
Published Linked with GitHub
  • DFS/BFS
  • Greedy

經典搜尋演算法

  • DFS (深度優先搜尋 Depth-First-Search)
  • BFS (廣度優先搜尋 Breadth-first search)

DFS 深度優先搜尋

DFS 是一種用來搜尋一個樹或圖的演算法，每當走到一個節點，就會以那個節點為新起始點，往其中一邊搜尋到到底或下一個節點。當已經走遍節點其中一邊的所有可能，才會開始走節點的另外一邊。

圖示

BFS 廣度優先搜尋

BFS 也是一種用來搜尋一個數或圖的演算法，但不同於 DFS 的是遇到節點時，會同時往節點的各個方向走相同的單位搜尋，不像 DFS 會優先走完其中一邊才走另一邊。

圖示

迷宮問題

問題

假設 0 代表可以走的路， 1 代表牆壁，我們想要從左上角(入口)走到右下角(出口)。
常問，輸出最短步數/隨意一個解/所有解

DFS 思路

在使用 DFS 的時候，是用特定的走法去走，而因為這個迷宮只有四個方向，可以隨意預設前方有路就直走，前方沒路，看左邊，左邊沒路看右邊，右邊也沒路就退一格。 (這些方向誰先誰後隨意) 不過要注意，是判斷到有路就直接前進，沒路再回來繼續判斷。

注意

  • 要記得走過的路要記錄起來，不然可能會一直繞圈圈
  • 邊界判斷問題

迷宮程式碼請看

https://hackmd.io/@HIPP0/ryDjVSBco

練習

  • G001 好朋友問題

(PS: 其實用DFS不是很好的方法)

建立朋友















// input n, m q
vector<vector<int>> vec(n);
while (m--) {
    int a, b;
    cin >> a >> b;
    vec[a].push_back(b);
    vec[b].push_back(a);
}
while (q--) {
    vector<int> ch(n, 0);
    int x;
    cin >> x;
    dfs(x, vec, ch);
}

DFS












vector<int> ans; // 記得每個回答前要先 clear
void dfs (int x, vector<vector<int>> &vec, vector<int> &ch) {
    ans.push_back(x);
    ch[x] = 1;
    for (int i = 0 ; i < vec[x].size() ; i++) {
        if (ch[vec[x][i]] == 1) continue;
        dfs(vec[x][i], vec, ch);
    }
    return;
}
// 記得對 ans sort

注意

  • ans 如果放全域 每次需要 clear
  • function 丟入的 vec 請不要用 reference，因為會被 pop 掉，但問題很多個
  • 因為自己也會被放進去，所以這樣可以 sort


sort(ans.begin()+1, ans.end());
// output ans[i] i from 1 to ans.size() - 1

BFS 思路

在使用 BFS 的時候，很像用倒水進去迷宮的方式，所以當下能走的路走完，才會再往可以進一步的地方往前邁進。做法就是先把上下左右的格子都走一遍，在把可行的節點放進隊列中，慢慢擴大搜索路徑。

同時用這個可以算最短路 (PS: 正常情況下效率不好)

迷宮程式碼請看

https://hackmd.io/@HIPP0/ryDjVSBco

練習

  • G002

Greedy

貪婪演算法（英語：greedy algorithm），又稱貪心演算法，是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，類似於模擬一個「貪心」的人，這個人目光短淺，只看眼前利益，不考慮可能後果，所以可想而知，並不是所有時候都可以得到最優解，使用貪心演算法時，請要確保自己可以「證明」其正確性

核心原理

在每一個階段選擇當前最佳解，並以此達到整個問題的最佳解。

最優子結構

問題能夠分解成子問題解決，子問題的最優解可以推到最終問題的最優解，而貪婪演算法在最優子結構的問題很有效果

證明

一般有兩種證明方式，反證法或歸納法。

  • 反證法：如果任意交換兩個元素後，答案不會變的更好，可以確定目前解是最好的。
  • 歸納法：先算出邊界情況的最優解(例如 n = 1)，在證明對於每個 n，\(F_{n+1}\) 都可以由 \(F_n\) 推出。

題型

常見的有兩種

  • 將XXX按照某種方式排序，然後按照某種順序選擇
  • 每次從XXX取最大/小的東西，更新XXX

兩者區別在於，第一個是離線的，先處理完再選擇，另一種是在線，邊處理邊選擇。

後悔解法

把當前選擇都當成最優解來看，然後進行比較，如果之後選擇不是最優就反悔，捨棄，如果一樣是最優，就接受，以此類推。

換硬幣問題

假設能換代幣的幣值有 [1,10,100,1000] ， 今天河馬拿了x元去換，則最少能拿到多少個代幣。

思路

因為代幣的數量希望要最少,直覺貪心的想法就是要盡量使用面額大的硬幣,代幣由大
面額的往小的考慮,能換盡量換,剩下不足的再考慮比較小的面額。

實作









int coin[4] = {1,10,100,1000};
int x, total = 0;
cin >> x;
for (int i = 3 ; i > 0 ; i--) {
    total += x / coin[i];
    x %= coin[i];
}  
cout << total << '\n';

需要證明?

你可能會認為這小學生也會的問題，不需要證明

那麼請看看下面的狀況 : 假設代幣的面額是 [1, 4, 5] 三種，上面的貪心方法會找到正確答案嗎？ 假設 x = 8，貪心的方法會先換一個 5 元，然後剩下 3 元，在換 3 個 1 元，所以總共換4個硬幣，不過若是全部換成 4 元的只需要 2 個硬幣。

證明

(歸納法) 首先幣值為 [1,10,100,1000]

如果 1 元的代幣總額不小於 10 ， 一定可以拿出 10 個換成一個 10 元，所以 1 元代幣的個數不會超過 9 個，同樣的你可以證明 10 元， 100元不會超過9個。也就是說，對任意第 i 種代幣 coin[i]，小於 coin[i] 的代幣總額不會超過 coin[i] , 所以 Greedy 是對的。 在[1, 4, 5]的狀況，就沒有這個性質了。

排班問題

https://hackmd.io/@5568KE/排班問題

練習

  • G003
  • G004
  • G005
Select a repo