{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> - 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不是很好的方法) ---- ### 建立朋友 ```cpp= // 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 ```cpp= 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 ```cpp= 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元去換，則最少能拿到多少個代幣。 ---- ### 思路 因為代幣的數量希望要最少,直覺貪心的想法就是要盡量使用面額大的硬幣,代幣由大 面額的往小的考慮,能換盡量換,剩下不足的再考慮比較小的面額。 ---- ### 實作 ```cpp= 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/%E6%8E%92%E7%8F%AD%E5%95%8F%E9%A1%8C ---- ### 練習 - G003 - G004 - G005