《高級算法設計》課件 第5、6章 隨機算法；在線算法

高級算法設計與分析隨機算法目錄概述隨機快速排序最小圓覆蓋弗里瓦德算法集合覆蓋最小割概述概述此算法可能返回0，也可能返回n?a，算法復雜度可能為Θ(1)，也可能為Θ(n)概述：分類1拉斯維加斯算法(LasVegas)算法能夠得到一個確定性的解決，但算法執(zhí)行時間不確定例子:在有n個元素的數(shù)組A中，有一半的元素為0，另一半的元素為1(隨機分布)，找到一個值為1元素的下標。概述：分類1蒙特卡洛算法(MonteCarlo)蒙特卡洛算法得出的解是不確定的，但是執(zhí)行時間是確定的概述：分類1概述：分類2概述：分類2分類避免落入最壞情形降低算法復雜度避免落入最壞情形：隨機快速排序快速排序的平均復雜度是O(nlogn)，但是在最壞的情況下，算法的復雜度為O(n2)。為了消除這種最差的情況，可以在快速排序引入一種隨機因素隨機快速排序在數(shù)組中隨機的選擇一個元素作為主元素Lomuto劃分避免落入最壞情形：隨機快速排序避免落入最壞情形：隨機快速排序避免落入最壞情形：隨機快速排序秩小于i和大于j的元素被選為主元，i和j的比較概率并不會受到影響如果i和j被選為主元，則i和j進行比較(共2個元素)大于i且小于j的元素被選為主元(共j?i?1個元素)，則i和j不會比較避免落入最壞情形：隨機快速排序最小圓覆蓋所有三個點形成的圓個數(shù)為O(n3)，判斷每個圓是否包含所有其他點O(n)，暴力求解的總復雜度為O(n4)最小圓覆蓋隨機增量法(randomizedincrementalconstruction)增量:通過逐個的添加點，來計算每一步的最小覆蓋圓，即計算一個點的最小圓覆蓋，兩個點的最小圓覆蓋，···，直到n個點的最小圓覆蓋;隨機:通過一種隨機的方式來添加點，避免算法跌入最壞情況。最小圓覆蓋設目前新添加的點是pi，那么存在兩種情況:如果添加的新點pi

已經(jīng)被包含在Ci?1

內(nèi)，那么Ci=Ci?1

添加的新點pi

沒有被包含在Ci?1

內(nèi)，此時需要增大圓，增大到什么時候為止?圓剛好能夠包含pi

。最小圓覆蓋假設結論不成立：最小圓覆蓋pi在圓上，可以通過遍歷{p1,p2,···,pi?1}上任意的兩個點組合來確定Ci

p1

加入，這樣p1

和pi

形成兩個節(jié)點的最小圓，再依次加入{p2,···,pi?1}，直到找到第一個不被當前最小圓包含的點(設為pj)。pj和pi，它們是{p1,p2,···,pj,pi}這些點的最小圓邊界上的點再次對{p1,p2,···,pj?1}這些點增量判斷，得到{p1,p2,···,pj,

pi}這些點的最小圓重復上述流程，直到得到{p1,p2,···,pi?1,pi}所有這些點的最小圓最小圓覆蓋最小圓覆蓋最小圓覆蓋算法復雜度最小圓覆蓋算法復雜度主函數(shù)：因為點排列的隨機性，第i個點在Ci

邊界上的概率只有3/i（或者2/i）

最小圓覆蓋算法復雜度MinDisc1Piont函數(shù)的復雜度最小圓覆蓋算法復雜度MinDisc1Piont函數(shù)的復雜度最小圓覆蓋算法復雜度主函數(shù)分類避免落入最壞情形降低算法復雜度弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)集合覆蓋集合覆蓋的隨機算法基于IP建模，以及其對應的松弛LP問題假設已經(jīng)求得LP問題的最優(yōu)解x?，在隨機算法中，最優(yōu)解x?

看成子集S的選取概率集合覆蓋某個元素ei通過隨機算法沒有被覆蓋的概率集合覆蓋拋k次硬幣，只要出現(xiàn)一次硬幣朝上，子集Sj被選中集合覆蓋為了算法能夠得出一個合法解，我們可以通過多次執(zhí)行上面的拋硬幣流程，直到得出合法解為止算法repeat期望執(zhí)行次數(shù)為多少次？集合覆蓋算法repeat期望執(zhí)行次數(shù)為多少次？即求算法執(zhí)行一次repeat，得出合法解，且代價（權重之和）小于4k·OPTLP

的概率集合覆蓋集合覆蓋集合覆蓋最小割最小割最小割隨機的方式得出一個最小割的概率是多少?最小割最小割最小割最小割最小割最小割最小割在得到一個收縮圖G后，對圖G應用兩次隨機收縮算法，并遞歸的應用以上方法通過7

次收縮，可隨機得到4

個割，但如果進行獨立的收縮，則需要4?3=12次的收縮。最小割最小割最小割最小割遞歸收縮圖的葉子層（也就是邊界條件）看成是第0層，其上一層為第1層，以此類推，則第k+1層節(jié)點得出最小割概率p_{k+1}的遞歸式：高級算法設計與分析在線算法目錄基本概念確定性在線算法在線最小生成樹時間序列搜索隨機在線算法租買問題在線二分圖最大匹配概述離線算法在前面討論的算法中，問題實例的所有數(shù)據(jù)在計算時，都是已知的，稱為離線算法在線算法問題實例的數(shù)據(jù)是逐漸到來的，但是又需要對已經(jīng)到來的數(shù)據(jù)進行計算，也就是說算法必須在輸入數(shù)據(jù)不是很完全可知的情況下，完成相應的計算并輸出結果如股票買賣、物流中的裝車問題在線算法是近似算法概述人工智能算法試圖從以往的數(shù)據(jù)中尋找出規(guī)律，并根據(jù)目前的分配狀態(tài)，來智能的分配目前到達的任務在線算法數(shù)據(jù)完全未知假設存在一個對手(adversary)：這個對手對設計的算法了如指掌，所以能夠針對算法給出最壞數(shù)據(jù)到達實例(稱為最壞實例)，來使得算法的效率最低，所以設計在線算法時，通常需要分析在最壞實例下算法的性能。概述：流程股票買賣為例概述：定義競爭度ρ概述：定義在線算法的下界下界表達式給出了在最差實例下，任意在線算法ALG和OPT存在大于等于的關系，如果某算法ALG′的ρ=α，且c=0,b=0，說明在線算法ALG′的性能已經(jīng)最優(yōu)，因為所有在線算法在最壞實例下都是大于等于競爭度ρ的，當在線算法ALG′的競爭度是小于等于ρ，顯然ALG′已經(jīng)最優(yōu)。確定性在線算法：在線最小生成樹在線最小生成樹圖中的頂點不是一開始就已知，而是逐個到達，并要求一旦一個頂點到達就需要加入到樹中，且讓生成的樹總代價盡量小。一個比較簡單的在線算法是讓到達的頂點通過離樹內(nèi)最近的頂點加入到樹中。如，在第k個頂點到達時，選取前面k?1個頂點中和第k個頂點距離最近的頂點，通過此頂點將第k個頂點加入到樹中。我們把這種算法稱為最小生成樹的貪心在線算法。確定性在線算法：在線最小生成樹在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索確定性在線算法：時間序列搜索目錄基本概念確定性在線算法在線最小生成樹時間序列搜索隨機在線算法租買問題在線二分圖最大匹配隨機在線算法策略的做出是隨機性，形成隨機在線算法，隨機在線算法的好處是，假設的對手無法猜測算法的策略。隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題回到上面租買問題的例子ρ=4/3

的競爭度，這個競爭度比任意的確定性算法都要好，但這個競爭度是實例{I1,I2,I3}下的最優(yōu)競爭度嗎隨機在線算法：租買問題隨機實例下確定性算法費用和競爭度的計算隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：租買問題隨機在線算法：在線二分圖最大匹配隨機在線算法：在線二分圖最大匹配按秩進行貪心匹配的確定性算法隨機在線算法：在線二分圖最大匹配隨機在線算法：在線二分圖最大匹配在小數(shù)二分圖匹配中，一個到達的頂點(a∈A)可以和B中的頂點(可以有多個)部分匹配隨機在線算法：在線二分圖最大匹配一個非常簡單的算法是:當一個頂點ai到達時，和所有可匹配的頂點進行均勻匹配水位算法(waterlevelalgorithm)是一個非常著名的確定性在線算法，當A中的一個頂點a到達時，算法依據(jù)頂點a所有鄰頂點的匹配狀態(tài)，將a的匹配分配到這些鄰頂點中