1 DISJOINT SETS 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 講義 0 - Disjoint Sets 與搜索 tony1 Kaimu 01//11 1 Disjoint Sets Disjoint Sets( 並查集 ) 是用來處理多個不相交集合的資料結構 Disjoint sets 具有兩種操 作,Union 是將兩個集合合併,Find 則是查詢某個元素所在的集合 並查集用樹狀結構來表達一個集合, 以樹的樹根來代表該集合 實際上我們只需記錄每 個元素的父元素即可, 當要查詢元素所在集合時, 便相當於查詢其父元素所在的集合, 如此 遞迴下去, 直到找不到父元素為止, 就代表找到了樹根 而合併兩個集合就是將其中一個集 合的樹根之父元素指向另一集合的樹根 Algorithm 1 Disjoint Sets 1: procedure Find(x) : if x.parent x then 3: return Find(x.parent) : else 5: return x 6: end if : end procedure : procedure Union(x, y) 9: xroot Find(x) : yroot Find(y) 11: xroot.parent yroot 1: end procedure 以上的樸素的作法在最差的情況下 ( 一條鏈 ),Find 的複雜度會變為 O(N), 與暴力搜索 的複雜度一樣, 因此我們應該想辦法優化 以下介紹兩種常見的優化方式 : 1.1 Path Compression Path Compression 是在遞迴的過程中將所經過元素的父元素皆改為樹根, 如此一來下次 再查詢時便可節省許多時間 此優化的速度非常快, 但複雜度不好估計 Author: tony1 1
1 DISJOINT SETS 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 Algorithm Path Compression 1: procedure Find(x) : if x.parent x then 3: x.parent Find(x.parent) : return x.parent 5: else 6: return x : end if : end procedure 1. Union By Rank 對於每個集合, 多記錄一個 rank 值代表其最大深度 在合併時, 比較兩個集合的 rank, 將 rank 較小的合併到 rank 較大的集合中 若 rank 相同則可任意可併, 但合併後的集合 rank 須 +1 Algorithm 3 Union By Rank 1: procedure Union(x, y) : xroot Find(x) 3: yroot Find(y) : if xroot.rank < yroot.rank then 5: xroot.parent yroot 6: else if yroot.rank < xroot.rank then : yroot.parent xroot : else 9: xroot.parent yroot : yroot.rank yroot.rank + 1 11: end if 1: end procedure 使用這個優化後,Find 的複雜度將變為 O(lg N) 若同時使用以上兩種優化, 則總複雜度會變成 O(N α(n)) 由於 α(n) 的值在競賽領域 中 n 的範圍內幾乎可視為常數, 故可假設所有對並查集的操作加總為 O(N) Author: tony1
1 DISJOINT SETS 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 1.3 例題 1. TIOJ 131 家族 給你很多組數字 a, b, 代表 a 與 b 在同個家族 現在給你一個數字 k, 求 k 所在的家族中編號最小的是?. POJ 9 雌蟲雄蟲 給你很多對關係 x, y, 代表蟲 x 跟蟲 y 為異性 請輸出是否有任何矛盾 ( 也就是有蟲為雌雄同體 ) 3. POJ 11 食物鏈 總共有 A B C 三種動物,A 吃 B,B 吃 C,C 吃 A 依序給你很多組關係 d, x, y, 若 d = 1 代表 x 跟 y 是同類,d = 則代表 x 吃 y 若當前給的關係與之前的關係矛盾, 代表此組關係是假的 求總共有多少組關係是假的? Author: tony1 3
BINARY TREE 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11.1 定義 Binary Tree Binary Tree( 二元樹 ) 是一種樹狀資料結構 G = (V, E), 滿足以下條件 : G 為一棵有根的樹 對於所有的 v V,v 至多只有 個子節點 在二元樹裡, 一個點的深度即為他到根節點的距離, 二元樹的高度即為最深的節點的深度 葉子即為沒有子節點的節點, 而我們說兩節點為兄弟節點表示他們的父節點相同 一個二元樹是完整的, 表示二元樹的節點由上而下, 再由左而右填滿整個樹 一個二元樹是滿枝的, 表示二元樹除了深度為 H 的節點為葉子之外, 其他的節點都洽有兩個子節點 1. 3 5 6 9. 二元樹的儲存 如果二元樹非常接近完整二元樹, 我們可以如下編號, 另樹根的編號為 1(0), 每一個節點 x 的左子節點的編號為 x(x + 1), 右子節點的編號為 x + 1(x + ), 然後直接開一個陣列以編號當索引紀錄節點的資訊 另外當然也可以直接用儲存一般圖的方法, 這個後面會提到 Author: Kaimu
BINARY TREE 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11.3 二元樹的走訪 我們定義了三種二元樹的走訪方式 : 可以知道 前 中 後 分別代表在拜訪左節 1: function Pre-Order(v) : if v is not Null then 3: print v : PRE-ORDER(Left child of v) 5: PRE-ORDER(Right child of v) 6: end if : end function 1: function In-Order(v) : if v is not Null then 3: In-ORDER(Left child of v) : print v 5: In-ORDER(Right child of v) 6: end if : end function 1: function Post-Order(v) : if v is not Null then 3: Post-ORDER(Left child of v) : Post-ORDER(Right child of v) 5: print v 6: end if : end function 點前 拜訪左節點和右節點中間和拜訪右節點後將頂點的標號列印出來 Author: Kaimu 5
BINARY TREE 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11. Binary search tree Binary search tree( 二元搜尋樹 ) 是一個特別的二元樹, 滿足對任意節點 v, 左子樹任意節點的鍵值都比 v 的鍵值小, 右子樹任意節點的鍵值都比 v 的鍵值大 1. 1 15 0 11 1 這樣當我們要做操作時, 我們只需要按照其定義操作即可 比如我們要查詢一個鍵值 k, 便從樹根開始, 如果當前節點 v 的鍵值 v key = k 即找到了,v key < k 則往左子節點走,v key > k 則往右子節點走 插入和刪除的動作基本上差不多 而這些的操作時間複雜度和二元樹的高度 H 有關, 大部分都是 O(H), 在最好或是平均的狀況之下, 二元樹可以達到 H = O(lg N), 但在最差的情況下卻有可能 H = O(N) 例如插入的數字恰好是由小到大的, 此時二元樹會退化為一值鏈 為了解決這個問題, 便衍生出許多自平衡的二元搜尋樹, 我們將在後面介紹 Author: Kaimu 6
3 HEAP 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 3 Heap Heap 是一種資料結構, 可以快速地維持 查詢極值 查詢最大值 插入元素 刪除元素 合併 Binary Heap O(1) O(lg n) O(lg n) Leftist Heap O(1) O(lg n) O(lg n) O(lg n) Fibonacci Heap O(1) O(1) O(lg n) O(1) 在這裡主要介紹 Binary Heap Leftist Heap 可以說是可併堆中較好實作的一個,Fibonacci Heap 雖然理論複雜度優但實作複雜, 而且實際上常數頗大的 雖然 Binary Heap 幾乎可以被樹狀資料結構取代, 但因實作容易, 如果只需要查詢最大值的 話不失為一個不錯的資料結構, 並且 STL 中有 priority_queue 為一 max-heap 可供直接使 用 3.1 Binary Heap Binary Heap 是一個完整的二元樹, 必須要滿足一個結構, 任何一個節點的鍵值都要大於等於其子樹中任意節點的鍵值 也因為 Binary Heap 是一個完整的二元樹, 我們通常直接用一個陣列儲存. 5 1 接著我們考慮其基本操作 3.1.1 插入元素 當我們要插入一個元素時我們把新的節點加進最後的位置, 並且如果新的節點的值比其父節點大, 便將他往上調整, 即和他父節點交換, 直到他成為樹根或是其父節點比他還大為止 可以知道此操作的複雜度為 O(H) = O(lg N), 其中 H 為 heap 的高度 Author: Kaimu
3 HEAP 建國中學 01 年資訊能力競賽培訓講義 - 0 01//11.. 5 5 3 3 5 1 3 1 1 3.1. 刪除最大元素 與插入元素類似, 我們直接將樹根還有最尾端的元素交換, 並將新的樹根往下調整 此操作的複雜度為 O(H) = O(lg N), 其中 H 為 heap 的高度... 5 5 5 1 1 1 3.1.3 查詢最大值 這個 easy, 就是根節點的鍵值 Author: Kaimu
搜索建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 搜索 搜索是最基本的演算法, 也就是俗稱的 暴力 法, 嘗試所有的可能性以求得答案 縱 使如此, 方法的不同還是會有速度上的差異.1 枚舉 枚舉每種可能的答案 經過一番枚舉之後... 沒辦法我還是只想到這兩行可以打. 狀態空間搜索 當我們在搜索的時候, 可以想成我們在一張圖上行走, 對問題在某一時刻狀況的數學描述即稱為狀態, 可以想像成圖上的一個點, 一開始我們會在起始狀態, 而我們最終希望能到達結束狀態 從一個狀態轉換到另外一個狀態的操作就稱為狀態轉移, 即為圖上的一條邊 所有狀態的集合就稱為狀態空間 只不過我們可能不知道圖上所有的邊, 不知道圖上的兩點是否可以通行, 甚至不能確定圖上有那些點, 因此我們要進行搜索, 即嘗試走過圖上的點, 盡可能快地達到終點 以下介紹不同的搜索方式.3 DFS 與 BFS DFS(Depth First Search) 深度優先搜索, 即依照深度優先, 盡可能地往深度越深的地方搜索, 若走到死路即回頭, 通常使用遞迴或堆疊來實現 他的優點是實現簡潔, 而且佔用空間少 ( 空間複雜度僅 O(d), 其中 d 為最大深度 ), 但沒有辦法在深度無上界的狀態空間下搜索 BFS(Breath First Search) 廣度優先搜索, 就有點像是 地毯式 搜索, 一層一層優先擴展與初始狀態較近的節點, 通常使用佇列實做 可以在深度無上界的狀態空間下搜索, 但需要的記憶體往往是很可怕的 1. 1 3 3 6 9 5 6 5 9 Author: Kaimu 9
搜索建國中學 01 年資訊能力競賽培訓講義 - 0 01//11 1: function DFS(Init_State) : Push Init_State Into Stack 3: while Stack Is not Empty do : Current_State Pop Stack 5: Mark Current_State As visited 6: for each v adjacent to Current_State do : if v Is not Visited then : Push v Into Stack 9: end if : end for 11: end while 1: end function 1: function BFS(Init_State) : Push Init_State Into Queue 3: Mark Init_State As visited : while Queue Is not Empty do 5: Current_State Pop Queue 6: for each Next_State adjacent to Current_State do : if Next_State Is not Visited then : Push Next_State Into Queue 9: Mark Next_State As visited : end if 11: end for 1: end while 13: end function Author: Kaimu
搜索建國中學 01 年資訊能力競賽培訓講義 - 0 01//11. BiBFS 假設我們使用 BFS 進行搜索, 並且每個狀態都有 n 種轉移, 那當我們在搜索第 d 層的時後便會有 O(n d ) 種狀態, 往往會讓記憶體無法負荷 這時候如果狀態轉移的動作是可逆的, 並且我們明確的知道結束狀態, 我們其實可以一邊從起點搜索下去, 另一邊從終點倒推回去, 而讓搜索的層數降低為 d/.5 IDDFS BFS 雖能保證找到狀態轉移次數最少的解, 但是太佔空間 因此, 我們可以用迭代加深的 DFS 來模擬廣度優先搜索 IDDFS 即是每次限制 DFS 的最大深度 limit, 如果 DFS 的深度超過 limit 就不再繼續搜索下去 當我們在 limit 之內找不到解時, 加大 limit 再進行一次 DFS 雖然乍看之下好像做了許多重複搜索的工作, 但是因為搜索樹的每一層級往往擴展節點數量差異極多, 因此迭代加深的工作效率仍然不錯 IDDFS 的空間複雜度僅僅是 O(d).6 A* A* 是一種啟發式演算法, 主要的想法很簡單, 即是改變搜索的順序, 讓我們可以盡快地走到終點 以直覺來說我們每一次都應該選擇 現在看似離終點最近的狀態 繼續走下去, 而這時候就必須有一個估計函數估計目前狀態到終點的距離是多少 另 h(x) 為狀態 x 的估計函數,h (x) 為狀態 x 到終點的實際距離,g(x) 為狀態 x 從起點到現在的距離, 我們便用 f(x) = g(x) + h(x) 來決定擴展節點的順序 但當然, 好的估計函數會影響到搜索的速度, 甚至影響搜索的正確性 一個好估計函數應該要滿足以下條件 h(x) h (x), 這個不等式保證了估計函數的正確性 h(x) 越大越好,h(x) 越大 *A 算法便會越根據你的估計函數來決定搜索順序 在實作上通常會使用 priority queue 來維護頂點 f(x) 值的大小順序 Author: Kaimu 11
搜索建國中學 01 年資訊能力競賽培訓講義 - 0 01//11. IDA* IDA* 的缺點就是記憶體需求太大, 因此與 IDDFS 類似, 我們設定一個限制, 直接忽略 f(x) 值大於深度限制的節點, 並以迭代加深的方式搜索 Algorithm IDA* 1: function IDDFS(State,g,limit) : f g + h(state) 3: if f > Limit then : return false 5: end if 6: if S thentate Is Goal_State : return True : end if 9: for each Next_State adjacent to State do : ret IDDFS(NextState,g + 1, limit) 11: if r thenet Is not False 1: return ret 13: end if 1: end for 15: end function 16: function IDA*(Init_State) 1: Limit 0 1: repeat : Limit Limit +1 0: ret IDDFS(Init_State,0, Limit) 1: until ret is False : end function Author: Kaimu 1
搜索建國中學 01 年資訊能力競賽培訓講義 - 0 01//11. Exercise 1. Packing Rectangles (USACO 1-, packrec) 給定四個矩形的長 寬 矩形可以任意移動 順 / 逆時針旋轉 90 度, 但是不能重疊 如果要把四個矩形包在一個矩形當中, 則該矩形的面積最小是多少? 請輸出所有解. 經典問題 給一個 M N 的格子矩形, 每個格子不是 1 就是 0, 你每次可以對一個格子進行操作, 把那個格子和他周圍的格子 1 變成 0 0 變成 1, 問你至少要做幾次才能使所有格子都變成 0 (M, N 15) 3. 經典問題 輸出數獨問題的所有解. 射手座之日 (NPSC 006 決賽, pb) TIOJ 99 對一個三維空間的座標 (x, y, z), 你可以做它兩件事 : (a) 把 x, y, z 任意調換 (b) 把 (x, y, z) 變成 (y-x+1, x-y-1, z) 問有沒有可能把座標從 (x 1, y 1, z 1 ) 變成 (x, y, z ) 5. Snake(Codeforces 5D) 你現在在一個 M N 有障礙物的格子上玩貪吃蛇, 你蛇的長度為 L, 並且有個格子上有食物, 你每次頭可以往前 左或是右移動, 你某格身體便會移動到前面那一格的身體的位置 注意到你的頭不可以撞到任何障礙物或是身體, 問你至少要動幾步 (M, N 15, L 9) 6. 15-Puzzle TIOJ 153 給一個 的盤面, 當中填有 1,,, 15 的數字, 並有一個空位 每次你可以移動一個與空位相鄰的數字到空位去, 請問最少要幾部才能到達指定的盤面? Author: Kaimu 13