or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Brute Force Algorithm
暴搜演算法
暴搜演算法 ?
窮舉
\(n\le 20\) (O
\(n\le 30, 50...\) (X
Complete search
選擇合理範圍的的維度,
窮舉所有可能的答案
UVa 725 – Division
給你一個數字 \(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()
把判斷函數寫在外面,程式碼比較乾淨
想法三
只窮舉 b 去判斷 b * n 是否等於有相對應的 a
只窮舉 b
複雜度跟 b 的範圍大小有關 \(10^5\)
UVa 11565 - Simple Equations
給你三個數字 \(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!!
題目的值域變成 \(6 \cdot 10^{18}\)
Backtracking
回溯法
枚舉多維度數值的方法。遞迴窮舉所有維度,並且在過程中避免不必要的窮舉(剪枝),以降低複雜度。
由於回溯法是窮舉所有維度,複雜度通常為指數 如 \(O(a^b)\)
因此如果是暴搜提通常題目的範圍都很小,像是 \(n\le 50\) 之類
剪枝 (pruning)
遞迴找答案時,中間有可能遇到很多不合理的狀態(超出邊界) 而如果當下狀態不合法或者不可能走到答案,則可以直接跳過當下狀態,以避免不必要的窮舉
以 \(O(2^n)\) 為例,會發現在適當的地方剪枝可以減去很多不必要的可能
UVa 750 – 8 Queens Chess Problem
給你一個 8X8 的棋盤,要放 8 個皇后
而要讓這 8 個皇后彼此都不會攻擊到
而皇后可以攻擊同行同列以及同左右斜線的棋子
問你有幾種擺法 ?
上圖為一組合法解
窮舉所有可能
總共 64 格,每次選 8 格判斷合法性
總共 \(\binom{64}{8}\) 種 = 4,426,165,368
\(\to\) TLE
backtracking
所有皇后彼此不能攻擊到,代表同一行最多只能有一個皇后
因此可以窮舉每一行放一個皇后,並且避免不必要的窮舉
如果已經有同一列或者對角線有放皇后,則同一列、左右斜線不能再放
以第三行為例,能放的位置為下面四格,上面都會被其他皇后攻擊
複雜度
總共 8 行,每行能放的位置隨著前面已經放的會越來越少
第一行可以放 8 個,第二行 7 個 …
複雜度 O(N!)
8! = 40,320
因此用陣列紀錄是否同一列、左右斜線是否有放過
斜線總共有 2N-1 條
同一條左上到右下的斜線,則x+y會是同一個值
同一條右上到左下的斜線,則x-y會是同一個值
例題 CSES - Grid Paths
給你 7X7 的矩陣,一開始在左上角 (0, 0) 的位置
給你一條部分未知的路徑,從起點開始要走到右下角,
問你有幾條路徑可以使得每個點都剛好走一次?
sample input
sample output
暴力遞迴搜索
遞迴每格判斷是否為未知路經,是未知路徑的話窮舉四個方向
最差的情況每格都是
?
複雜度為 \(O(4^{49} \times 49)\) // 49格窮舉四種方向, 每次遞迴傳下去字串 path 長度為 49剪枝
哪些部份可以省略 ?
會發現字串 path 可以放全域變數 不用每次遞迴都重新傳一次
直接修改全域變數的值,遞迴後記得要改回來原本的值
複雜度減少了每次傳參數的時間變成 \(O(4^{49})\)
剪枝
走到甚麼情況可以不用繼續往下走
再想想還有什麼其他剪枝?
超出邊界
走的時候順便紀錄當前位置,如果超出邊界則不為合法解
撞牆
紀錄每個點是否走過,走過視為牆壁
可以用一個 bool 陣列紀錄是否走過
使得連通塊分成兩半
當走到的格子前面那格為牆壁,但左右都還沒走過時,
代表會將還沒走過的區域分成兩塊,則代表會無解不必繼續走下去
除了以上四種剪枝,
再想想還有什麼其他剪枝 ?
通常這種爆搜的題目總狀態數都不會太大
以這題為例 \(7\times 7\),最多只有 49 種狀態
所以當題目 \(n\) 很小就要想想看是不是爆搜題
接著就是想要怎麼剪枝,避免所有不必要的窮舉
State‐space search
把每種狀態都當成一個節點,從狀態轉移當成一條邊
轉換成圖論問題去 BFS/DFS 求解
UVa 11212 – Editing a book
給你一段長度為 \(n (n \le 9)\) 的 permutation
每次操作可以選擇一段連續區間剪切到其他位置,求最少需要幾次可以讓序列變成升序序列
sample input
sample output
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
改變 A,B,C 區塊結尾的後繼
剪枝不會更好的答案
而最差的情況下最多需要做 8 個操作(序列[9, 8, 7, 6, 5, 4, 3, 2, 1])
每次最多可以讓 h 減少 3
假設我們做需要做最多的次數為 maxd,而當前做的次數為 d
若還可以做的次數 (maxd - d) * 3 < h
代表每次改變最多的非連續數量也就是3次,而用剩下的次數還做不完的話
則沒必要繼續做下去,因為一定不可能比答案小
則可以直接剪枝掉
紀錄當前狀態是否有遞迴過
可以用一個 map 把整個序列存起來,紀錄當前序列最少要幾次可以走到
如果比原本的次數還要多 那就沒必要繼續走下去了
否則更新原本的答案
狀態壓縮
對於狀態我們通常會壓縮後再存起來
以上面題目為例,狀態為一個序列 [ 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 時,則直接回傳最佳值當作答案
通常不會用到時間剪枝
而且時間剪枝每次要判斷時間所以會增加運算成本
meet in the middle
中間相遇法 (折半枚舉)
把所有可能分兩半,分別暴力枚舉所有可能
例題 UVa 12911 - Subset sum
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
sample output
(2, 4, -1, -5), (2, 6, -5, -3), (4, -1, -3), (6, -5, -1)
sum up = 0
遞迴窮舉
窮舉第 x 個數字要不要使用,複雜度 \(O(2^N)\)
使用迴圈窮舉
每個數字選或不選,總共有 \(2^N\) 種可能
N 的大小為 40
\(2^{40} = 10^{12} >> 10^8\)
TLE
把每種數字選或不選轉換成圖
以前三個數字 -1,2,-3 為例
狀態數會隨著 n 越大呈現指數成長
而如果我們把狀態拆兩半,一半重頭開始窮舉,一半從尾巴
則狀態數會從 \(2^n\) 變成 \(2 \cdot 2^{\frac{n}{2}}\)
\(\to\)
N = 40
\(2^{\frac{40}{2}} = 10^6\)
分別算完兩邊 subset 的答案儲存起來後,
判斷兩邊算出來的答案能不能加起來剛好等於 target value
實作
(有部分細節沒處理)
此題為2021-12-21 CPE第七題
了解概念就可以 10 分鐘AC了(X
Practice
建議上面題目也做過一遍
Link