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

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

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

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

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