淺談隨機化思想在幾何問題中的應(yīng)用

引入隨著信息學(xué)的發(fā)展，近幾年，各種各樣靈活的幾何題目層出不窮。因此隨機算法和隨機化思想便有了表演的舞臺。隨機算法的特點是：簡單、快速、靈活和易于并行化，這些特點都會在論文中得到體現(xiàn)。第一頁第二頁，共50頁。概覽數(shù)值概率算法拉斯維加斯算法蒙特卡羅算法舍伍德算法第一部分隨機算法簡介第二部分隨機增量算法第三部分模擬退火算法第二頁第三頁，共50頁。隨機增量算法的一個例子ExpensiveDrink

(BeijingSite,2007)（經(jīng)過抽象）maximize s.t. ……單純形法、內(nèi)點法？(n≤100)第三頁第四頁，共50頁。ExpensiveDrink第四頁第五頁，共50頁。隨機增量算法的一般步驟發(fā)現(xiàn)問題的本質(zhì)提出算法改造成增量算法加入隨機第五頁第六頁，共50頁。ExpensiveDrink解解解結(jié)論1：如果存在解，必然存在于三個平面的交點上。第六頁第七頁，共50頁。ExpensiveDrink想法：枚舉兩個平面，得到一條直線。枚舉其余約束，切割該直線。結(jié)論1：如果存在解，必然存在于三個平面的交點上。第七頁第八頁，共50頁。ExpensiveDrink想法：枚舉兩個平面，得到一條直線。枚舉其余約束，切割該直線。直到最后剩下一條線段。結(jié)論1：如果存在解，必然存在于三個平面的交點上。第八頁第九頁，共50頁。ExpensiveDrink直線數(shù)量O(n2)切割復(fù)雜度O(n)總復(fù)雜度O(n3)仍需要提高結(jié)論2：只有線段的兩個端點可能成為解。結(jié)論1：如果存在解，必然存在于三個平面的交點上。第九頁第十頁，共50頁。ExpensiveDrink癥結(jié)：沒有利用到之前已經(jīng)計算的結(jié)果對癥：引入增量算法。依次加入半空間的時候，若原先的最優(yōu)解為v，且滿足當(dāng)前的約束，就沒有必要枚舉平面上的直線了。第十頁第十一頁，共50頁。ExpensiveDrink復(fù)雜度仍舊為O(n3)對策：隨機插入半空間的順序第十一頁第十二頁，共50頁。ExpensiveDrink復(fù)雜度仍舊為O(n3)對策：隨機插入半空間的順序第十二頁第十三頁，共50頁。復(fù)雜度分析取隨機變量Xi，若滿足前i-1條約束的最優(yōu)解滿足第i條約束，則Xi=0，否則Xi=1。時間復(fù)雜度為根據(jù)期望的線性率有是多少呢？最優(yōu)解由3個約束構(gòu)成，恰好包括第i條約束的概率就是。第十三頁第十四頁，共50頁。在本題中，增量算法架筑起了線性規(guī)劃問題與經(jīng)典幾何知識的橋梁，隨機化思想則消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。本題也體現(xiàn)出隨機算法簡單、快速（相對于單純形法）的特點。ExpensiveDrink下面將介紹論文中的第二個算法：模擬退火算法。第十四頁第十五頁，共50頁。模擬退火算法簡介模擬退火（SimulatedAnnealing）算法是模仿自然界中固體退火的原理的一種元啟發(fā)式（Meta-Heuristics）算法。①初始化：初始充分大的溫度T，初始解狀態(tài)S，迭代數(shù)L②fork=1toL做③至⑤③產(chǎn)生新解S’并計算評價函數(shù)C(S’)④若C(S’)<C(S)則接受S’作為新的當(dāng)前解，否則以概率接受S’作為新的當(dāng)前解⑤如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序⑥T逐漸減少，然后轉(zhuǎn)②第十五頁第十六頁，共50頁。最小距離問題經(jīng)典方法：構(gòu)造Voronoi圖解，并對頂點集合進行判斷。求區(qū)域中一點，到某個點集中的點的最小距離最大。第十六頁第十七頁，共50頁。最小距離問題求區(qū)域中一點，到某個點集中的點的最小距離最大。通過類比的思想，引入模擬退火算法：隨機初始解，溫度T定義為調(diào)整向量的模長。估價函數(shù)定義為到最近點的距離。如果函數(shù)值變大，則更新原解。第十七頁第十八頁，共50頁。最小距離問題隨機初始解，溫度T定義為調(diào)整向量的模長。估價函數(shù)定義為到最近點的距離。如果函數(shù)值變大，則更新原解。求區(qū)域中一點，到某個點集中的點的最小距離最大。通過類比的思想，引入模擬退火算法：第十八頁第十九頁，共50頁。最小距離問題模擬退火算法有并行性。求區(qū)域中一點，到某個點集中的點的最小距離最大。不斷重復(fù)這一過程，直到步長足夠小。取當(dāng)前最優(yōu)解作為答案。通過類比的思想，引入模擬退火算法：第十九頁第二十頁，共50頁。模擬退火算法的應(yīng)用模擬退火算法有很強的可移植性。最小距離最大對應(yīng)于最近點Voronoi圖解最大距離最小最遠點Voronoi圖解第k大距離最小k階Voronoi圖解經(jīng)過反射后距離最小和距離最小倒數(shù)和距離最小第二十頁第二十一頁，共50頁。模擬退火算法的例子激光坦克（CTSC2007）在平面上有N個坦克，M個鏡子。要求在平面內(nèi)放置一個激光發(fā)射器，使得它在發(fā)出的每束激光經(jīng)過不超過k次反射后擊中所有目標的前提下，距離的最大值最小。N=4M=4k=2第二十一頁第二十二頁，共50頁。模擬退火算法的例子激光坦克（CTSC2007）N=4M=4k=2本題是一個最大距離最小的問題，如果不考慮鏡子的因素，可以使用最遠點Voronoi圖或前面的隨機增量算法來解決，但是鏡子的存在使得問題非常棘手。第二十二頁第二十三頁，共50頁。模擬退火算法的例子激光坦克（CTSC2007）N=4M=4k=2此時，模擬退火算法的可移植性的優(yōu)勢就體現(xiàn)了出來，我們可以在主算法的框架上，分別獨立編寫與鏡子不同次數(shù)相交的評價函數(shù)。第二十三頁第二十四頁，共50頁。激光坦克的得分與代價Testcasek不處理反射處理一次反射處理兩次反射601010102110101031010107111010521010108261010139101043101010930010105000總得分568090代碼長度90160240300第二十四頁第二十五頁，共50頁?？偨Y(jié)本文通過幾道例題，以及體現(xiàn)出的一種思想，希望能為大家打開一扇窗，在遇到幾何問題的時候多一種思路。當(dāng)然，隨機化思想的靈活運用，是在對于經(jīng)典問題熟練掌握的前提下的，因為創(chuàng)新永遠建立在扎實的基礎(chǔ)之上。第二十五頁第二十六頁，共50頁。謝謝！第二十六頁第二十七頁，共50頁。ExpensiveDrink題目描述有3種物品的價格（設(shè)為x,y,z）要滿足n組約束且求的最大值第二十七頁第二十八頁，共50頁。ExpensiveDrink解解解結(jié)論1：如果存在解，必然存在于三個平面的交點上。第二十八頁第二十九頁，共50頁。ExpensiveDrink想法：枚舉兩個平面，得到一條直線。枚舉其余約束，切割該直線。結(jié)論1：如果存在解，必然存在于三個平面的交點上。第二十九頁第三十頁，共50頁。結(jié)論1：如果存在解，必然存在于三個平面的交點上。ExpensiveDrink想法：枚舉兩個平面，得到一條直線。枚舉其余約束，切割該直線。直到最后剩下一條線段。第三十頁第三十一頁，共50頁。引理1只有線段的兩個端點可能是的目標函數(shù)的最大值。ExpensiveDrink引理2不會有某三個平面的交點被遺漏。結(jié)論2：只有線段的兩個端點可能成為解。第三十一頁第三十二頁，共50頁。ExpensiveDrink引理1只有線段的兩個端點可能是的目標函數(shù)的最大值。第三十二頁第三十三頁，共50頁。ExpensiveDrink引理2不會有某三個平面的交點在計算中被遺漏。第三十三頁第三十四頁，共50頁。具體的實現(xiàn)因為空間中的直線情況比較多、比較復(fù)雜，因此我們可以使用參數(shù)方程進行統(tǒng)一表示。這樣，我們對直線的切割就轉(zhuǎn)化成為對于參數(shù)值求交的過程。最后是求解參數(shù)方程的過程。首先我們假設(shè)枚舉的兩個平面不平行，我們?nèi)我庀、y、z中的一個，得到一個二元（一元）一次方程。取任意一個自由元的方程的系數(shù)，經(jīng)過兩次回代即可求出直線的參數(shù)方程。第三十四頁第三十五頁，共50頁。三維線性規(guī)劃O(n)的算法這題理論上存在O(n)復(fù)雜度的方法。但是該算法有兩點弊病：1)時間復(fù)雜度中隱藏的常數(shù)巨大。本題中在時間上的優(yōu)勢微小。（n僅100。）2)編程復(fù)雜度過大。其實O(n)的算法并不難想：每次加入一個半空間后，如果先前的解不成立需要更新，此時就是要將目標向量在平面上的投影作為新的目標向量，將其他半空間轉(zhuǎn)換成半平面做一次二維線性規(guī)劃。幾次空間和平面間的轉(zhuǎn)換與旋轉(zhuǎn)，將該算法僅僅保留在理論上。我們使用隨機思想是希望事半功倍、化繁為簡，因此本算法有悖于我們的初衷。而且無論在信息學(xué)還是ACM賽場上比賽的時間都是有限的，因此本算法雖然存在，但并不值得推廣。第三十五頁第三十六頁，共50頁。數(shù)值概率算法數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數(shù)值概率算法可得到滿意的解。舉個例子：計算p的近似值時，我們可以在單位圓的外接矩形內(nèi)隨機撒n個點，設(shè)有k個點落在單位圓內(nèi)，可以得到p近似等于4k/n。第三十六頁第三十七頁，共50頁。舍伍德算法舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當(dāng)一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況的發(fā)生，而是設(shè)法消除這種最壞行為與特定實例之間的關(guān)聯(lián)性。舍伍德算法的一個最廣泛的應(yīng)用就是快速排序的隨機化實現(xiàn)。第三十七頁第三十八頁，共50頁。隨機洗牌算法這個問題不復(fù)雜，以下代碼就可以以線性的時間復(fù)雜度得到一個1~n的隨機排列。（記錄在數(shù)組O中。）AlgorithmRandom_shufflefori

2ton交換O[i]，O[random(i)]（其中random(n)返回一個1~n的隨機數(shù)。）第三十八頁第三十九頁，共50頁。蒙特卡羅抽樣它的基本思想是，對于所求的問題，通過試驗的方法和大樣本來模擬，得到這個隨機變量的期望值，并用它作為問題的解。它是以一個概率模型為基礎(chǔ)，按照這個模型所描繪的過程，通過模擬實驗的結(jié)果，作為問題的近似解的過程。第三十九頁第四十頁，共50頁。模擬退火算法的原理模擬退火算法是一種元啟發(fā)式（Meta-Heuristics）算法，來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為，其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。第四十頁第四十一頁，共50頁。元啟發(fā)式算法元啟發(fā)式算法（Meta-Heuristics）是一種啟發(fā)式策略，意思就是指導(dǎo)啟發(fā)式算法進行工作的方法。常見的元啟發(fā)式算法有：模擬退火算法遺傳算法蟻群算法PSO(粒子群優(yōu)化)第四十一頁第四十二頁，共50頁。精確度分析的一個例子最優(yōu)解附近（如點A，B）的點非常稀少且距離很遠，因此有候選解在它周圍（所在的Delaunay三角剖分區(qū)域內(nèi)）的概率是很大的。而且此時的距離比較大，我們對方向進行多次嘗試，因此調(diào)整出去的概率也很小。第四十二頁第四十三頁，共50頁。精確度分析的一個例子如圖，假設(shè)一次隨機調(diào)整成功的概率為P，則第四十三頁第四十四頁，共50頁。精確度分析的一個例子若我們的L取30…………(d=0,g=0)

D取到最小值0.085r。1）因為此時兩者垂直，因此對于答案的影響很小。2）我們使用了放縮過程，把g、d都當(dāng)成0計算，因此實際的調(diào)整概率還要更高。第四十四頁第四十五頁，共50頁。精確度分析的一個例子但是如果題目的精度要求非常高，怎么辦呢？既然很難隨機到向量和Voronoi邊平行，我們可以直接枚舉平行于Voronoi邊的向量，雖然在時間上付出一點代價，但是在調(diào)整成功的概率和解的精度無疑將大大提高。當(dāng)然對于普通的題目（本節(jié)三道例題Run