Brute Force Algorithm

--- tags: 2023-winterTraining type: slide slideOptions: # transition: fade --- <style> .reveal .slides { text-align: left; font-size:30px; } </style> # Brute Force Algorithm ## 暴力演算法 Introduction to Competitive Programming 2/6 ---- ## 暴力演算法 ? - 可以暴力幹嘛要學其他演算法 - 或許題目只有暴力解 - 對拍用拿來 debug - 用來打表觀察題目性質 ---- - Bitmask Enumerate Subset - Complete search - Backtracking - State‐space search - Meet In the Middle --- ### Bitmask Enumerate Subset 使用位元運算窮舉子集合 --- 有 n 個數字，要判斷可以組合出幾種不同的總和? 子集合有 $2^n$ 種 (每個數字要選或不選) 可以使用二進位表示每個數字要不要選，以 $0\sim 2^n-1$ 表示以 n = 3 為例，以 0(000)~7(111) 表示 010 代表選第 2 個數字 110 代表選第 1, 2 個數字 ---- ## 使用迴圈窮舉 ```cpp= set<int> s; // 使用 set 紀錄出現過的總和 void enumerate(){ for(int i = 0; i < (1<<n); i++){ // 0 ~ 2^n-1 int sum = 0; for(int j = 0; j < n; j++){ // 窮舉每個位元判斷是否為 1 if(i>>j&1){ // 判斷第 i 個位元 sum += arr[i]; } } s.insert(sum); } cout << s.size() << endl; } ``` 複雜度為 $O(N\times 2^N)$ 如果看到題目 $N\le 20$ 都可以直接暴力窮舉子集合 --- ## Complete search 選擇選項較少的維度窮舉答案 ---- ## [UVa 725 – Division](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=666) 給你一個數字 $N$，你要輸出所有正整數 pair(a, b) 使得 a/b = N， a, b 為五位數，且所有數字不能重複以 N = 62 為例答案有兩組 79546 / 01283 = 62 94736 / 01528 = 62 而 N = 61 沒有任何符合的解 ---- ### 想法一窮舉所有 a, b 可能的範圍去判斷有沒有符合的而可能出現的範圍為 00001 ~ 99999 因此 C 約為 10^5 複雜度 $O(C^2) \to 10^{10}$ TLE ---- ### 想法二由於每種數字會出現剛好一次因此窮舉所有排列 0123456789 ~ 9876543210 再去判斷分出來的 a, b 所得到的 a/b 會不會等於 n 複雜度 O(N!) 10種數字，因此 $10! = 3,628,800$ 複雜度是好的 AC! ---- 生成所有排列可以使用 c++ STL 的 next_permutation() ```cpp= for(int i=0;i<10;i++){ vec.push_back(i) } do{ if(check(vec)){ ans.push_back(vec); } }while(next_permutation(vec.begin(),vec.end())); ``` ---- ## 想法三只窮舉 b 去判斷 b * n 是否等於有相對應的 a ```cpp= for(int b=0;b<100000 && b*n<100000;b++){ if(different_digit(a,b)){ ans.push_back(make_pair(a, b)); } } ``` ---- 只窮舉 b 複雜度為 b 的範圍大小 $10^5$ ---- ## [UVa 11565 - Simple Equations](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2612) 給你三個數字 $A, B, C (1 \le A, B, C \le 10000)$ 已知 $x + y + z = A$ $x * y * z = B$ $x^2 + y^2 + z^2 = C$ 求出 $x, y, z$，如有多組解則輸出 tuple($x, y, z$) 字典序最小的如果直接窮舉所有可能的 $x, y, z$ 複雜度 $O(10000^3) \to 10^{12}$ TLE ---- $A, B, C (1 \le A, B, C \le 10000)$ 而如果只看第三個式子 $x^2 + y^2 + z^2 = C$ 會發現當 $x, y, z$ 超過$\sqrt{10^5}$ 之後就會出過 $C$ 所以 $x, y, z$ 的範圍只會在 $[1, \sqrt{10000}]$ 之間因此可以直接窮舉 x, y, z 在 $[1, \sqrt{10000}]$ 的範圍複雜度 $O(\sqrt{C}^{3}) = 10^6$ ---- 有興趣的可以挑戰 [UVa 11571 - Simple Equations - Extreme!!](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2618) 題目的值域變成 $6 \cdot 10^{18}$ --- ## Backtracking ### 回溯法枚舉多維度數值的方法。遞迴窮舉所有維度，並且在過程中避免不必要的窮舉(剪枝)，以降低複雜度。由於回溯法是窮舉所有維度，複雜度通常為指數如 $O(a^b)$ 因此如果是暴搜提通常題目的範圍都很小，像是 $n\le 50$ 之類 ---- ## 剪枝 (pruning) 遞迴找答案時，中間有可能遇到很多不合理的狀態(超出邊界) 而如果當下狀態不合法或者不可能走到答案，則可以直接跳過當下狀態，以避免不必要的窮舉以 $O(2^n)$ 為例，會發現在適當的地方剪枝可以減去很多不必要的可能 ![](https://i.imgur.com/qMfCPbu.png =600x) ---- ## [UVa 750 – 8 Queens Chess Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=691) 給你一個 8X8 的棋盤，要放 8 個皇后而要讓這 8 個皇后彼此都不會攻擊到而皇后可以攻擊同行同列以及同左右斜線的棋子問你有幾種擺法 ? ![](https://i.imgur.com/QMZfw1g.png) 上圖為一組合法解 ---- ## 窮舉所有可能總共 64 格，每次選 8 格判斷合法性總共 $\binom{64}{8}$ 種 = 4,426,165,368 $\to$ TLE ---- ## backtracking 所有皇后彼此不能攻擊到，代表同一行最多只能有一個皇后因此可以窮舉每一行放一個皇后，並且避免不必要的窮舉 ---- 如果已經有同一列或者對角線有放皇后，則同一列、左右斜線不能再放以第三行為例，能放的位置為下面四格，上面都會被其他皇后攻擊 <div style="position: absolute; right: 65%;"> ![](https://i.imgur.com/JmJ47De.png =300x) </div> <div style="position: absolute; right: 10%;"> ![](https://i.imgur.com/ZiT7JWb.png =300x) </div> ---- ## 複雜度總共 8 行，每行能放的位置隨著前面已經放的會越來越少第一行可以放 8 個，第二行 7 個 ... 複雜度 O(N!) 8! = 40,320 ---- 因此用陣列紀錄是否同一列、左右斜線是否有放過斜線總共有 2N-1 條同一條左上到右下的斜線，則x+y會是同一個值同一條右上到左下的斜線，則x-y會是同一個值 ```cpp= bool row[N], add[15], sub[15]; void backtracking(int x){ if(x == 8){ ans++; // 遞迴到最後結束 return; } for(int i=0;i<8;i++){ if(!row[i] && !add[x+i] && !sub[(x-i+15)%15]){ row[i] = add[x+i] = sub[(x-i+15)%15] = 1; //標記放置的位置 backtracking(x+1); // 換下一行 row[i] = add[x+i] = sub[(x-i+15)%15] = 0; //移除放置的位置 } } } int main(){ backtracking(0); } ``` ---- ## 例題 [CSES - Grid Paths](https://cses.fi/problemset/task/1625) 給你 7X7 的矩陣，一開始在左上角 (0, 0) 的位置給你一條部分未知的路徑，從起點開始要走到右下角，問你有幾條路徑可以使得每個點都剛好走一次? ### sample input ```txt ??????R??????U??????????????????????????LD????D? ``` ### sample output ```txt 201 ``` ---- ### 暴力遞迴搜索遞迴每格判斷是否為未知路經，是未知路徑的話窮舉四個方向最差的情況每格都是 `?` 複雜度為 $O(4^{49} \times 49)$ // 49格窮舉四種方向, 每次遞迴傳下去字串 path 長度為 49 ```cpp= int ans = 0; bool calc(string path){} void dfs(int x, string path){ if(x == 49) ans += calc(path); if(path[x] != '?') dfs(x+1, path); else{ for(char i : "LRUD"){ path[x] = i; dfs(x+1, path); } } }; int main(){ cin >> path; dfs(0); cout << ans << endl; } ``` ---- ## 剪枝哪些部份可以省略 ? ```cpp= void dfs(int x, string path){ } ``` 會發現字串 path 可以放全域變數不用每次遞迴都重新傳一次直接修改全域變數的值，遞迴後記得要改回來原本的值 ```cpp= string path; void dfs(int x){ if(x == 49) ans += calc(); if(path[x] != '?') dfs(x+1); else{ for(char i : "LRUD"){ path[x] = i; dfs(x+1); path[x] = '?'; } } } ``` 複雜度減少了每次傳參數的時間變成 $O(4^{49})$ ---- ## 剪枝走到甚麼情況可以不用繼續往下走 - 超出邊界 - 撞牆 - 使得連通塊分成兩半好好剪枝以上情況就會過了 ---- ## 超出邊界走的時候順便紀錄當前位置，如果超出邊界則不為合法解 ```cpp= void dfs(int x,int y,int d){ if(x<0 || x>=7 || y<0 || y>=7){ return; } } ``` ---- ## 撞牆紀錄每個點是否走過，走過視為牆壁可以用一個 bool 陣列紀錄是否走過 ```cpp= bool vis[10][10]; void dfs(int x,int y,int d){ if(vis[x][y]) return; vis[x][y] = 1; ... } ``` ---- ## 使得連通塊分成兩半當走到的格子前面那格為牆壁，但左右都還沒走過時，代表會將還沒走過的區域分成兩塊，則代表會無解不必繼續走下去 ![](https://i.imgur.com/OwZiQOx.png) ---- 有以上四種剪枝理論上就會過了，通常這種爆搜的題目總狀態數都不會太大以這題為例 $7\times 7$，最多只有 49 種狀態所以當題目 $n$ 很小就要想想看是不是爆搜題接著就是想要怎麼剪枝，避免所有不必要的窮舉 --- ## State‐space search 把每種狀態都當成一個節點，從狀態轉移當成一條邊轉換成圖論問題去 BFS/DFS 求解 ---- ## [UVa 11212 – Editing a book](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2153) 給你一段長度為 $n (n \le 9)$ 的 permutation 每次操作可以選擇一段連續區間剪切到其他位置，求最少需要幾次可以讓序列變成升序序列 sample input 2 1 5 3 4 6 sample output 2 1 剪下移到最前面 [2, (1), 5, 3, 4, 6] $\to$ [(1), 2, 5, 3, 4, 6] (3,4) 剪下移到最前面 [1, 2, 5, (3, 4), 6] $\to$ [1, 2, (3, 4), 5, 6] ---- 總共 $n! (n \le 9)$種狀態，代表節點數 362,880 個節點每次可以選一段區間，移到另一個地方，總共有 $\binom{n+1}{2}$ 個不同的區間且每次可以插入到 n-2 種不同的位置，邊數量為 $n!\binom{n+1}{2}(n-2)$ 轉換圖論 BFS 找最近距離複雜度 $O(V+E) = 114,307,200$ 可以再搭配一些剪枝 ---- ## 剪枝用當前步數判斷是否可能達到最佳答案先定義非連續數量 h ：對於一個序列 $a$ 有幾個 $i (1\le i < n)$ 符合 $a[i]+1 \ne a[i+1]$ 序列 [1,4,2,3] 的 h 為 2 最終要使得序列為升序，也就是 h = 0(序列[1, 2, 3, 4, 5, 6, 7, 8, 9]) 而對於一次的操作， h 最多減少 3 ![](https://i.imgur.com/isGmPDW.png) 改變 A,B,C 區塊結尾的後繼 ---- ## 剪枝不會更好的答案而最差的情況下最多需要做 8 個操作(序列[9, 8, 7, 6, 5, 4, 3, 2, 1]) 每次最多可以讓 h 減少 3 假設我們做需要做最多的次數為 maxd，而當前做的次數為 d 若還可以做的次數 (maxd - d) * 3 < h 代表每次改變最多的非連續數量也就是3次，而用剩下的次數還做不完的話則沒必要繼續做下去，因為一定不可能比答案小則可以直接剪枝掉 ```cpp= void dfs(int x,int d){ if((maxd - d)*3 < calc_h()) return; } ``` ---- ## 紀錄當前序列是否有遞迴過可以用一個 map 把整個序列存起來，紀錄當前序列最少要幾次可以走到如果比原本的次數還要多那就沒必要繼續走下去了否則更新原本的答案 ```cpp map<vector<int>, int> dis; void dfs(vector<int> arr, int d){ if(dis.count(arr) && dis[arr] <= d) return; dis[arr] = d; } ``` ---- ## 狀態壓縮對於狀態我們通常會壓縮後再存起來以上面題目為例，狀態為一個序列 [ 2, 1, 5, 3, 4, 6 ] 則其實我們可以直接把他壓成一個整數變成 215346 去代表這個狀態 n! 種可能的序列，每個序列有 n 個數字原本要花 n! * n 的空間去儲存，現在只需要儲存 n! 個整數即可 ---- 而在每次BFS/DFS會判斷是否走過，如果狀態是用序列儲存需要花 $O(N)$ 時間去比對是否相同，而轉成數字儲存只需要花 $O(1)$ 即可比對是否相同 map<vector<int>,int> $\to$ map<int,int> 題單可以用到此技巧來儲存 ---- ## 狀態壓縮以八皇后為例，原本是用陣列去儲存是否走過也可以改成用整數 {0,1,0,0,0,1,1,0} 代表第1,5,6 (0-base) 格有走過而直接用一個整數存起來 mask $=70_{10} = 01000110_{2}$ 空間複雜度存原本 $O(N)$ 變成 $O(1)$ 要查詢第 $i$ 格是否被用過則直接位元運算判斷 (mask>>i&1) 是否為 $1$ int 可以存 32 個位元 long long 可以存 64 個位元 ---- ## time pruning ### 時間剪枝有些很難的題目有時可能沒辦法在時限內AC，有一個毒瘤的技巧是時間剪枝在程式一開始記錄時間，當在執行遞迴過程中判斷執行時間，當快到Time Limit 時，則直接回傳最佳值當作答案 ---- ```cpp= #define SECs ((double)clock() / CLOCKS_PER_SEC) double startTime; void dfs(int x){ if(SECs - startTime > 0.95) return; } int main(){ startTime = SECs; dfs(0); } ``` ---- 通常不會用到時間剪枝而且時間剪枝每次要判斷時間所以會增加運算成本 --- ## meet in the middle ### 中間相遇法 (折半枚舉) 把所有可能分兩半，分別暴力枚舉所有可能 ---- ## 例題 [UVa 12911 - Subset sum](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4776) Given a set $s$ of integers $s_i$, your task is to determine how many different non-empty subsets sum up to a target value $T$. $1 \le N \le 40$ $-10^9 \le s_i, T \le 10^9$ ---- ### sample input ``` 6 0 -1 2 -3 4 -5 6 ``` ### sample output ``` 4 ``` (2, 4, -1, -5), (2, 6, -5, -3), (4, -1, -3), (6, -5, -1) sum up = 0 ---- ## 遞迴窮舉窮舉第 x 個數字要不要使用，複雜度 $O(2^N)$ ```cpp= void dfs(int x, int sum){ if(x == n) ans += sum == target; dfs(x+1, sum) // 不用第 x 個數字 dfs(x+1, sum+value[x]); // 用第 x 個數字 } ``` ---- ## 使用迴圈窮舉 ```cpp= for(int i = 0; i <(1<<n); i++){ int sum = 0; for(int j = 0; j < n; j++){ if(i>>j&1) sum += arr[j]; } ans += sum == target; } ``` ---- 每個數字選或不選，總共有 $2^N$ 種可能 N 的大小為 40 $2^{40} = 10^{12} >> 10^8$ TLE ---- 把每種數字選或不選轉換成圖以前三個數字 -1,2,-3 為例 ![](https://i.imgur.com/rHMFxwq.png =500x) ---- 狀態數會隨著 n 越大呈現指數成長 ![](https://i.imgur.com/hUDczFh.png =500x) ---- 而如果我們把狀態拆兩半，一半重頭開始窮舉，一半從尾巴則狀態數會從 $2^n$ 變成 $2 \cdot 2^{\frac{n}{2}}$ <div style="position: absolute; right: 65%;"> ![](https://i.imgur.com/hUDczFh.png =350x) </div> <div style="position: absolute; top:200%;right: 60%;"> $\to$ </div> <div style="position: absolute; right: 20%;"> ![](https://i.imgur.com/6mPgNUC.png =350x) </div> ---- N = 40 $2^{\frac{40}{2}} = 10^6$ 分別算完兩邊 subset 的答案儲存起來後，判斷兩邊算出來的答案能不能加起來剛好等於 target value ---- ## 實作 (有部分細節沒處理) ```cpp= map<int,int> mp; for(int i=0;i<(1<<(n/2));i++){ //iterate all subset of first half int sum=0; for(int j=0;j<n/2;j++){ if(i>>j&1) sum += arr[j]; // sum up all selected element } mp[sum]++; // save the sum to the STL map } for(int i=0;i<(1<<(n-n/2));i++){ //iterate all subset of second half int sum=0; for(int j=0;j<n-n/2;j++){ if(i>>j&1) sum += arr[n/2+j]; } if(mp.count(t-sum)) ans += mp[t-sum]; } ``` ---- 此題為2021-12-21 CPE第七題了解概念就可以 10 分鐘AC了(X ![](https://i.imgur.com/aeka3TT.png) --- ## Practice 建議上面題目也做過一遍 [Link](https://vjudge.net/contest/541272)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.