算法合集之《淺談隨機(jī)化思想在幾何問題中的應(yīng)用》

1、算法合集之淺談隨機(jī)化思算法合集之淺談隨機(jī)化思 想在幾何問題中的應(yīng)用想在幾何問題中的應(yīng)用 隨著信息學(xué)的發(fā)展，近幾年，各種各樣靈隨著信息學(xué)的發(fā)展，近幾年，各種各樣靈 活的幾何題目層出不窮。因此隨機(jī)算法和隨機(jī)活的幾何題目層出不窮。因此隨機(jī)算法和隨機(jī) 化思想便有了表演的舞臺?；枷氡阌辛吮硌莸奈枧_。 隨機(jī)算法的特點(diǎn)是：簡單、快速、靈活和隨機(jī)算法的特點(diǎn)是：簡單、快速、靈活和 易于并行化，這些特點(diǎn)都會在論文中得到體現(xiàn)。易于并行化，這些特點(diǎn)都會在論文中得到體現(xiàn)。 數(shù)值概率算法數(shù)值概率算法 拉斯維加斯算法拉斯維加斯算法 蒙特卡羅算法蒙特卡羅算法 舍伍德算法舍伍德算法 第一部分第一部分 隨機(jī)算法簡介隨機(jī)算法簡介

2、 第二部分第二部分 隨機(jī)增量算法隨機(jī)增量算法 第三部分第三部分 模擬退火算法模擬退火算法 Expensive Drink ( Beijing Site, 2007 )（經(jīng)過抽象）（經(jīng)過抽象） czbyax 11111 rzcybxal 22222 rzcybxal nnnnn rzcybxal maximize s.t. 單純形法、內(nèi)點(diǎn)法？單純形法、內(nèi)點(diǎn)法？ (n100) zyx0 yx0 x0 zy0 iiiii RzcybxaL zyx0 發(fā)現(xiàn)問題的本質(zhì)發(fā)現(xiàn)問題的本質(zhì) 提出算法提出算法 改造成增量算法改造成增量算法 加入隨機(jī)加入隨機(jī) c 解 c 解 c 解 結(jié)論結(jié)論1：如果存在解，必然存在

3、于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 想法：枚舉兩個平面，想法：枚舉兩個平面， 得到一條直線。得到一條直線。 枚舉其余約束，枚舉其余約束， 切割該直線。切割該直線。 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 想法：枚舉兩個平面，想法：枚舉兩個平面， 得到一條直線。得到一條直線。 枚舉其余約束，枚舉其余約束， 切割該直線。切割該直線。 直到最后剩下一直到最后剩下一 條線段。條線段。 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 直線數(shù)量直線數(shù)量O(n2) 切割復(fù)雜度切

4、割復(fù)雜度O(n) 總復(fù)雜度總復(fù)雜度O(n3) 仍需要提高 結(jié)論結(jié)論2：只有線段的兩個端點(diǎn)可能成為解。：只有線段的兩個端點(diǎn)可能成為解。 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 癥結(jié)：沒有利用到之前已經(jīng)計算的結(jié)果癥結(jié)：沒有利用到之前已經(jīng)計算的結(jié)果 c v 對癥：引入增量算對癥：引入增量算 法。依次加入半空法。依次加入半空 間的時候，若原先間的時候，若原先 的最優(yōu)解為的最優(yōu)解為v，且，且 滿足當(dāng)前的約束，滿足當(dāng)前的約束， 就沒有必要枚舉平就沒有必要枚舉平 面上的直線了。面上的直線了。 c 復(fù)雜度仍舊為復(fù)雜度仍舊為 O(n3) 對策：隨機(jī)插入對策

5、：隨機(jī)插入 半空間的順序半空間的順序 c 復(fù)雜度仍舊為復(fù)雜度仍舊為 O(n3) 對策：隨機(jī)插入對策：隨機(jī)插入 半空間的順序半空間的順序 取隨機(jī)變量取隨機(jī)變量Xi，若滿足前，若滿足前i-1條約束的最條約束的最 優(yōu)解滿足第優(yōu)解滿足第i條約束，則條約束，則Xi=0，否則，否則Xi=1。 時間復(fù)雜度為時間復(fù)雜度為 i n i XiO 1 2 根據(jù)期望的線性率有根據(jù)期望的線性率有 i n i n i i XEiOXiOE 1 2 1 2 是多少呢？最優(yōu)解由是多少呢？最優(yōu)解由3個約束構(gòu)成，恰個約束構(gòu)成，恰 好包括第好包括第i條約束的概率就是條約束的概率就是 。 i XE i 3 2 1 2 3 nO i

6、iO n i 在本題中，增量算法架筑起了線性規(guī)劃問在本題中，增量算法架筑起了線性規(guī)劃問 題與經(jīng)典幾何知識的橋梁，隨機(jī)化思想則題與經(jīng)典幾何知識的橋梁，隨機(jī)化思想則 消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。 本題也體現(xiàn)出隨機(jī)算法簡單、快速（相對本題也體現(xiàn)出隨機(jī)算法簡單、快速（相對 于單純形法）的特點(diǎn)。于單純形法）的特點(diǎn)。 下面將介紹論文中的第二個算法：模擬退下面將介紹論文中的第二個算法：模擬退 火算法?；鹚惴ā?模擬退火（模擬退火（Simulated Annealing）算法是）算法是 模仿自然界中固體退火的原理的一種元啟發(fā)式模仿自然界中固體退火的原理的一種元啟

7、發(fā)式 （Meta-Heuristics）算法。）算法。 初始化：初始充分大的溫度初始化：初始充分大的溫度T，初始解狀態(tài)，初始解狀態(tài)S，迭代數(shù)迭代數(shù)L for k=1 to L 做至做至 產(chǎn)生新解產(chǎn)生新解S并計算評價函數(shù)并計算評價函數(shù)C(S) 若若C(S)C(S)則接受則接受S作為新的當(dāng)前解，否則以概作為新的當(dāng)前解，否則以概 率率 接受接受S作為新的當(dāng)前解作為新的當(dāng)前解 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序 T逐漸減少，然后轉(zhuǎn)逐漸減少，然后轉(zhuǎn) T t e 經(jīng)典方法：構(gòu)造經(jīng)典方法：構(gòu)造 Voronoi圖解，并圖解，并 對頂點(diǎn)集合進(jìn)行對頂點(diǎn)

8、集合進(jìn)行 判斷。判斷。 求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。 求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。 通過類比的思想，通過類比的思想， 引入模擬退火算法：引入模擬退火算法： 隨機(jī)初始解，隨機(jī)初始解， 溫度溫度T定義為調(diào)整定義為調(diào)整 向量的模長。估價向量的模長。估價 函數(shù)定義為到最近函數(shù)定義為到最近 點(diǎn)的距離。點(diǎn)的距離。 如果函數(shù)值變?nèi)绻瘮?shù)值變 大，則更新原解。大，則更新原解。 隨機(jī)初始解，隨機(jī)初始解， 溫度溫度T定義為調(diào)整定義為調(diào)整 向量的模長。估價向量的模長。估價 函數(shù)定義為到最近

9、函數(shù)定義為到最近 點(diǎn)的距離。點(diǎn)的距離。 如果函數(shù)值變?nèi)绻瘮?shù)值變 大，則更新原解。大，則更新原解。 求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。 通過類比的思想，通過類比的思想， 引入模擬退火算法：引入模擬退火算法： 模擬退火算法有模擬退火算法有 并行性。并行性。 求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。求區(qū)域中一點(diǎn)，到某個點(diǎn)集中的點(diǎn)的最小距離最大。 不斷重復(fù)這一過不斷重復(fù)這一過 程，直到步長足程，直到步長足 夠小。取當(dāng)前最夠小。取當(dāng)前最 優(yōu)解作為答案。優(yōu)解作為答案。 通過類比的思想，通過類比的思想， 引入模擬退火算法：引入模擬退火算法：

10、模擬退火算法有很強(qiáng)的可移植性。模擬退火算法有很強(qiáng)的可移植性。 最小距離最大最小距離最大 對應(yīng)于對應(yīng)于 最近點(diǎn)最近點(diǎn)Voronoi圖解圖解 最大距離最小最大距離最小最遠(yuǎn)點(diǎn)最遠(yuǎn)點(diǎn)Voronoi圖解圖解 第第k大距離最小大距離最小k階階Voronoi圖解圖解 經(jīng)過反射后距離最小經(jīng)過反射后距離最小 和距離最小和距離最小 倒數(shù)和距離最小倒數(shù)和距離最小 激光坦克（激光坦克（CTSC2007） 在平面上有在平面上有N個坦克，個坦克， M個鏡子。要求在平面內(nèi)個鏡子。要求在平面內(nèi) 放置一個激光發(fā)射器，使放置一個激光發(fā)射器，使 得它在發(fā)出的每束激光經(jīng)得它在發(fā)出的每束激光經(jīng) 過不超過過不超過k次反射后擊中所次反射后

11、擊中所 有目標(biāo)的前提下，距離的有目標(biāo)的前提下，距離的 最大值最小。最大值最小。 N=4 M=4 k=2 激光坦克（激光坦克（CTSC2007） N=4 M=4 k=2 本題是一個最大距離本題是一個最大距離 最小的問題，如果不考慮最小的問題，如果不考慮 鏡子的因素，可以使用最鏡子的因素，可以使用最 遠(yuǎn)點(diǎn)遠(yuǎn)點(diǎn)Voronoi圖或前面的隨圖或前面的隨 機(jī)增量算法來解決，但是機(jī)增量算法來解決，但是 鏡子的存在使得問題非常鏡子的存在使得問題非常 棘手。棘手。 激光坦克（激光坦克（CTSC2007） N=4 M=4 k=2 此時，模擬退火算法此時，模擬退火算法 的可移植性的優(yōu)勢就體現(xiàn)的可移植性的優(yōu)勢就體現(xiàn)

12、了出來，我們可以在主算了出來，我們可以在主算 法的框架上，分別獨(dú)立編法的框架上，分別獨(dú)立編 寫與鏡子不同次數(shù)相交的寫與鏡子不同次數(shù)相交的 評價函數(shù)。評價函數(shù)。 Testcasek不處理反射不處理反射處理一次反射處理一次反射處理兩次反射處理兩次反射 60101010 21101010 3101010 7111010 52101010 8261010 1391010 43101010 930010 105000 總得分總得分568090 代碼長度代碼長度90160240300 本文通過幾道例題，以及體現(xiàn)出的一種思本文通過幾道例題，以及體現(xiàn)出的一種思 想，希望能為大家打開一扇窗，在遇到幾想，希望能為

13、大家打開一扇窗，在遇到幾 何問題的時候多一種思路。當(dāng)然，隨機(jī)化何問題的時候多一種思路。當(dāng)然，隨機(jī)化 思想的靈活運(yùn)用，是在對于經(jīng)典問題熟練思想的靈活運(yùn)用，是在對于經(jīng)典問題熟練 掌握的前提下的，因為創(chuàng)新永遠(yuǎn)建立在扎掌握的前提下的，因為創(chuàng)新永遠(yuǎn)建立在扎 實(shí)的基礎(chǔ)之上。實(shí)的基礎(chǔ)之上。 zyx0 有有3種物品的價格（設(shè)為種物品的價格（設(shè)為x, y, z）要滿足）要滿足n組約束組約束 iiiii RzcybxaL 且且 求求 的最大值的最大值czbyax c 解 c 解 c 解 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 想法：枚舉兩個平面，想法：枚舉兩

14、個平面， 得到一條直線。得到一條直線。 枚舉其余約束，枚舉其余約束， 切割該直線。切割該直線。 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 結(jié)論結(jié)論1：如果存在解，必然存在于三個平面的交點(diǎn)上。：如果存在解，必然存在于三個平面的交點(diǎn)上。 想法：枚舉兩個平面，想法：枚舉兩個平面， 得到一條直線。得到一條直線。 枚舉其余約束，枚舉其余約束， 切割該直線。切割該直線。 直到最后剩下一直到最后剩下一 條線段。條線段。 引理引理1 只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的 最大值。最大值。 引理引理2 不會有某三個平面的交

15、點(diǎn)被遺漏。不會有某三個平面的交點(diǎn)被遺漏。 結(jié)論結(jié)論2：只有線段的兩個端點(diǎn)可能成為解。：只有線段的兩個端點(diǎn)可能成為解。 引理引理1 只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的最大值。只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的最大值。 引理引理2 不會有某三個平面的交點(diǎn)在計算中被遺漏。不會有某三個平面的交點(diǎn)在計算中被遺漏。 因為空間中的直線情況比較多、比較復(fù)雜，因此我們可以因為空間中的直線情況比較多、比較復(fù)雜，因此我們可以 使用參數(shù)方程進(jìn)行統(tǒng)一表示。使用參數(shù)方程進(jìn)行統(tǒng)一表示。 tzzz tyyy txxx 10 10 10 這樣，我們對直線的切割就轉(zhuǎn)化成為對于參數(shù)值求交的過這樣，我們對直線的切割就轉(zhuǎn)化成為對于

16、參數(shù)值求交的過 程。程。 最后是求解參數(shù)方程的過程。首先我們假設(shè)枚舉的兩個平最后是求解參數(shù)方程的過程。首先我們假設(shè)枚舉的兩個平 面不平行，我們?nèi)我庀ッ娌黄叫?，我們?nèi)我庀、y、z中的一個，得到一個二元（中的一個，得到一個二元（ 一元）一次方程。取任意一個自由元的方程的系數(shù)，經(jīng)過兩次一元）一次方程。取任意一個自由元的方程的系數(shù)，經(jīng)過兩次 回代即可求出直線的參數(shù)方程?；卮纯汕蟪鲋本€的參數(shù)方程。 這題理論上存在這題理論上存在O(n)復(fù)雜度的方法。但是該算法有兩點(diǎn)復(fù)雜度的方法。但是該算法有兩點(diǎn) 弊?。罕撞。?1) 時間復(fù)雜度中隱藏的常數(shù)巨大。本題中在時間上的優(yōu)時間復(fù)雜度中隱藏的常數(shù)巨大。本題中在

17、時間上的優(yōu) 勢微小。（勢微小。（n僅僅100。）。） 2) 編程復(fù)雜度過大。其實(shí)編程復(fù)雜度過大。其實(shí)O(n)的算法并不難想：每次的算法并不難想：每次 加入一個半空間后，如果先前的解不成立需要更新，此時加入一個半空間后，如果先前的解不成立需要更新，此時 就是要將目標(biāo)向量在平面上的投影作為新的目標(biāo)向量，將就是要將目標(biāo)向量在平面上的投影作為新的目標(biāo)向量，將 其他半空間轉(zhuǎn)換成半平面做一次二維線性規(guī)劃。幾次空間其他半空間轉(zhuǎn)換成半平面做一次二維線性規(guī)劃。幾次空間 和平面間的轉(zhuǎn)換與旋轉(zhuǎn)，將該算法僅僅保留在理論上。和平面間的轉(zhuǎn)換與旋轉(zhuǎn)，將該算法僅僅保留在理論上。 我們使用隨機(jī)思想是希望事半功倍、化繁為簡，因此

18、本算我們使用隨機(jī)思想是希望事半功倍、化繁為簡，因此本算 法有悖于我們的初衷。而且無論在信息學(xué)還是法有悖于我們的初衷。而且無論在信息學(xué)還是ACM賽場賽場 上比賽的時間都是有限的，因此本算法雖然存在，但并不上比賽的時間都是有限的，因此本算法雖然存在，但并不 值得推廣。值得推廣。 數(shù)值概率算法常用于數(shù)值問題的求解。這類算法數(shù)值概率算法常用于數(shù)值問題的求解。這類算法 所得到的往往是近似解。而且近似解的精度隨計所得到的往往是近似解。而且近似解的精度隨計 算時間的增加不斷提高。在許多情況下，要計算算時間的增加不斷提高。在許多情況下，要計算 出問題的精確解是不可能或沒有必要的，因此用出問題的精確解是不可能或

19、沒有必要的，因此用 數(shù)值概率算法可得到滿意的解。數(shù)值概率算法可得到滿意的解。 舉個例子：計算舉個例子：計算p p的近似值時，我們可以在單位圓的近似值時，我們可以在單位圓 的外接矩形內(nèi)隨機(jī)撒的外接矩形內(nèi)隨機(jī)撒n個點(diǎn)，設(shè)有個點(diǎn)，設(shè)有k個點(diǎn)落在單位個點(diǎn)落在單位 圓內(nèi)，可以得到圓內(nèi)，可以得到p p近似等于近似等于4 4k/n。 舍伍德算法總能求得問題的一個解，且所求得的舍伍德算法總能求得問題的一個解，且所求得的 解總是正確的。當(dāng)一個確定性算法在最壞情況下解總是正確的。當(dāng)一個確定性算法在最壞情況下 的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有 較大差別時，可以在這

20、個確定算法中引入隨機(jī)性較大差別時，可以在這個確定算法中引入隨機(jī)性 將它改造成一個舍伍德算法，消除或減少問題的將它改造成一個舍伍德算法，消除或減少問題的 好壞實(shí)例間的這種差別。舍伍德算法精髓不是避好壞實(shí)例間的這種差別。舍伍德算法精髓不是避 免算法的最壞情況的發(fā)生，而是設(shè)法消除這種最免算法的最壞情況的發(fā)生，而是設(shè)法消除這種最 壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法的壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法的 一個最廣泛的應(yīng)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。一個最廣泛的應(yīng)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。 這個問題不復(fù)雜，以下代碼就可以以線性這個問題不復(fù)雜，以下代碼就可以以線性 的時間復(fù)雜度得到一個的時間復(fù)雜

21、度得到一個1n的隨機(jī)排列。的隨機(jī)排列。 （記錄在數(shù)組（記錄在數(shù)組O中。）中。） Algorithm Random_shuffle for i 2 to n 交換交換Oi，Orandom(i) （其中（其中random(n)返回一個返回一個1n的隨機(jī)數(shù)。）的隨機(jī)數(shù)。） 它的基本思想是，對于所求的問題，通過它的基本思想是，對于所求的問題，通過 試驗的方法和大樣本來模擬，得到這個隨試驗的方法和大樣本來模擬，得到這個隨 機(jī)變量的期望值，并用它作為問題的解。機(jī)變量的期望值，并用它作為問題的解。 它是以一個概率模型為基礎(chǔ)，按照這個模它是以一個概率模型為基礎(chǔ)，按照這個模 型所描繪的過程，通過模擬實(shí)驗的結(jié)果，

22、型所描繪的過程，通過模擬實(shí)驗的結(jié)果， 作為問題的近似解的過程。作為問題的近似解的過程。 模擬退火算法是一種元啟發(fā)式（模擬退火算法是一種元啟發(fā)式（Meta-Heuristics）算）算 法，來源于固體退火原理，將固體加溫至充分高，再讓其法，來源于固體退火原理，將固體加溫至充分高，再讓其 徐徐冷卻。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)徐徐冷卻。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi) 能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到 平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù) Metropolis準(zhǔn)則，粒子在溫度準(zhǔn)則，粒子在溫度T時趨于平衡的概率為時趨于平衡的概率為 ，其中，其中E為溫度為溫度T時的內(nèi)能，時的內(nèi)能，E為其改變量，為其改變量，k為為 Boltzmann常數(shù)。常數(shù)。 T t e 元啟發(fā)式算法（元啟發(fā)式算法（Meta-Heuristics）是一）是一 種啟發(fā)式策略，意思就是指導(dǎo)啟發(fā)式算法種啟發(fā)式策略，意思就是指導(dǎo)啟發(fā)式算法 進(jìn)行工作的方法。常見的元啟發(fā)式算法有：進(jìn)行工作的方法。常見的元啟發(fā)式算法有： 模擬退火算法模擬退火算法 遺傳算法遺傳算法 蟻群算法蟻群算法 PSO(粒子群優(yōu)化粒子群優(yōu)化) 最優(yōu)解附近（如點(diǎn)最優(yōu)解附近（如點(diǎn)A，B）的點(diǎn)非