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

1、 隨著信息學(xué)的開(kāi)展，近幾年，各種各樣靈隨著信息學(xué)的開(kāi)展，近幾年，各種各樣靈敏的幾何標(biāo)題層出不窮。因此隨機(jī)算法和隨機(jī)敏的幾何標(biāo)題層出不窮。因此隨機(jī)算法和隨機(jī)化思想便有了扮演的舞臺(tái)?；枷氡阌辛税缪莸奈枧_(tái)。 隨機(jī)算法的特點(diǎn)是：簡(jiǎn)單、快速、靈敏和隨機(jī)算法的特點(diǎn)是：簡(jiǎn)單、快速、靈敏和易于并行化，這些特點(diǎn)都會(huì)在論文中得到表達(dá)。易于并行化，這些特點(diǎn)都會(huì)在論文中得到表達(dá)。 數(shù)值概率算法數(shù)值概率算法拉斯維加斯算法拉斯維加斯算法蒙特卡羅算法蒙特卡羅算法舍伍德算法舍伍德算法第一部分第一部分 隨機(jī)算法簡(jiǎn)介隨機(jī)算法簡(jiǎn)介第二部分第二部分隨機(jī)增量算法隨機(jī)增量算法第三部分第三部分模擬退火算法模擬退火算法Expensive

2、Drink ( Beijing Site, 2007 )經(jīng)過(guò)籠統(tǒng)經(jīng)過(guò)籠統(tǒng)czbyax11111rzcybxal22222rzcybxalnnnnnrzcybxalmaximizes.t.單純形法、內(nèi)點(diǎn)法？單純形法、內(nèi)點(diǎn)法？(n100)zyx0yx0 x0zy0iiiiiRzcybxaLzyx0發(fā)現(xiàn)問(wèn)題的本質(zhì)發(fā)現(xiàn)問(wèn)題的本質(zhì)提出算法提出算法改呵斥增量算法改呵斥增量算法參與隨機(jī)參與隨機(jī)c解c解c解結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。想法：枚舉兩個(gè)平面，想法：枚舉兩個(gè)平面， 得到一條直線。得到一條直線。枚舉其他約束，枚舉其他約束，切割該直線。切

3、割該直線。結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。想法：枚舉兩個(gè)平面，想法：枚舉兩個(gè)平面， 得到一條直線。得到一條直線。枚舉其他約束，枚舉其他約束，切割該直線。切割該直線。直到最后剩下一直到最后剩下一條線段。條線段。結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。直線數(shù)量直線數(shù)量O(n2)切割復(fù)雜度切割復(fù)雜度O(n)總復(fù)雜度總復(fù)雜度O(n3)仍需求提高結(jié)論結(jié)論2：只需線段的兩個(gè)端點(diǎn)能夠成為解。：只需線段的兩個(gè)端點(diǎn)能夠成為解。結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存

4、在于三個(gè)平面的交點(diǎn)上。癥結(jié)：沒(méi)有利用到之前曾經(jīng)計(jì)算的結(jié)果癥結(jié)：沒(méi)有利用到之前曾經(jīng)計(jì)算的結(jié)果 cv對(duì)癥：引入增量算對(duì)癥：引入增量算法。依次參與半空法。依次參與半空間的時(shí)候，假設(shè)原間的時(shí)候，假設(shè)原先的最優(yōu)解為先的最優(yōu)解為v，且滿足當(dāng)前的約束，且滿足當(dāng)前的約束，就沒(méi)有必要枚舉平就沒(méi)有必要枚舉平面上的直線了。面上的直線了。c復(fù)雜度仍舊為復(fù)雜度仍舊為O(n3)對(duì)策：隨機(jī)插入對(duì)策：隨機(jī)插入半空間的順序半空間的順序c復(fù)雜度仍舊為復(fù)雜度仍舊為O(n3)對(duì)策：隨機(jī)插入對(duì)策：隨機(jī)插入半空間的順序半空間的順序 取隨機(jī)變量取隨機(jī)變量Xi，假設(shè)滿足前，假設(shè)滿足前i-1條約束的條約束的最優(yōu)解滿足第最優(yōu)解滿足第i條約束，那

5、么條約束，那么Xi=0，否那么，否那么Xi=1。時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 iniXiO12根據(jù)期望的線性率有根據(jù)期望的線性率有 ininiiXEiOXiOE1212 是多少呢？最優(yōu)解由是多少呢？最優(yōu)解由3個(gè)約束構(gòu)成，恰個(gè)約束構(gòu)成，恰好包括第好包括第i條約束的概率就是條約束的概率就是 。iXEi3 2123nOiiOni 在此題中，增量算法架筑起了線性規(guī)劃問(wèn)在此題中，增量算法架筑起了線性規(guī)劃問(wèn)題與經(jīng)典幾何知識(shí)的橋梁，隨機(jī)化思想那題與經(jīng)典幾何知識(shí)的橋梁，隨機(jī)化思想那么消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影么消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。此題也表達(dá)出隨機(jī)算法簡(jiǎn)單、快速響。此題也表達(dá)出隨機(jī)算法簡(jiǎn)單

6、、快速相對(duì)于單純形法的特點(diǎn)。相對(duì)于單純形法的特點(diǎn)。下面將引見(jiàn)論文中的第二個(gè)算法：模擬退下面將引見(jiàn)論文中的第二個(gè)算法：模擬退火算法。火算法。 模擬退火模擬退火Simulated Annealing算法是算法是模擬自然界中固體退火的原理的一種元啟發(fā)式模擬自然界中固體退火的原理的一種元啟發(fā)式Meta-Heuristics算法。算法。 初始化：初始充分大的溫度初始化：初始充分大的溫度T，初始解形狀，初始解形狀S，迭代數(shù)，迭代數(shù)L for k=1 to L 做至做至 產(chǎn)生新解產(chǎn)生新解S并計(jì)算評(píng)價(jià)函數(shù)并計(jì)算評(píng)價(jià)函數(shù)C(S) 假設(shè)假設(shè)C(S)C(S)那么接受那么接受S作為新的當(dāng)前解，否那么作為新的當(dāng)前解，否

7、那么以概率以概率 接受接受S作為新的當(dāng)前解作為新的當(dāng)前解 假設(shè)滿足終止條件那么輸出當(dāng)前解作為最優(yōu)解，終了程假設(shè)滿足終止條件那么輸出當(dāng)前解作為最優(yōu)解，終了程序序 T逐漸減少，然后轉(zhuǎn)逐漸減少，然后轉(zhuǎn)Tte經(jīng)典方法：構(gòu)造經(jīng)典方法：構(gòu)造Voronoi圖解，并圖解，并對(duì)頂點(diǎn)集合進(jìn)展對(duì)頂點(diǎn)集合進(jìn)展判別。判別。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。經(jīng)過(guò)類比的思想，經(jīng)過(guò)類比的思想，引入模擬退火算法：引入模擬退火算法： 隨機(jī)初始解，隨機(jī)初始解，溫度溫度T定義為調(diào)整定義

8、為調(diào)整向量的模長(zhǎng)。估價(jià)向量的模長(zhǎng)。估價(jià)函數(shù)定義為到最近函數(shù)定義為到最近點(diǎn)的間隔。點(diǎn)的間隔。 假設(shè)函數(shù)值變假設(shè)函數(shù)值變大，那么更新原解。大，那么更新原解。 隨機(jī)初始解，隨機(jī)初始解，溫度溫度T定義為調(diào)整定義為調(diào)整向量的模長(zhǎng)。估價(jià)向量的模長(zhǎng)。估價(jià)函數(shù)定義為到最近函數(shù)定義為到最近點(diǎn)的間隔。點(diǎn)的間隔。 假設(shè)函數(shù)值變假設(shè)函數(shù)值變大，那么更新原解。大，那么更新原解。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。經(jīng)過(guò)類比的思想，經(jīng)過(guò)類比的思想，引入模擬退火算法：引入模擬退火算法：模擬退火算法有模擬退火算法有并行性。并行性。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最

9、大。求區(qū)域中一點(diǎn)，到某個(gè)點(diǎn)集中的點(diǎn)的最小間隔最大。不斷反復(fù)這一過(guò)不斷反復(fù)這一過(guò)程，直到步長(zhǎng)足程，直到步長(zhǎng)足夠小。取當(dāng)前最夠小。取當(dāng)前最優(yōu)解作為答案。優(yōu)解作為答案。經(jīng)過(guò)類比的思想，經(jīng)過(guò)類比的思想，引入模擬退火算法：引入模擬退火算法：模擬退火算法有很強(qiáng)的可移植性。模擬退火算法有很強(qiáng)的可移植性。最小間隔最大最小間隔最大對(duì)應(yīng)于對(duì)應(yīng)于最近點(diǎn)最近點(diǎn)Voronoi圖解圖解最大間隔最小最大間隔最小最遠(yuǎn)點(diǎn)最遠(yuǎn)點(diǎn)Voronoi圖解圖解第第k大間隔最小大間隔最小k階階Voronoi圖解圖解經(jīng)過(guò)反射后間隔最小經(jīng)過(guò)反射后間隔最小和間隔最小和間隔最小倒數(shù)和間隔最小倒數(shù)和間隔最小激光坦克激光坦克CTSC2007 在平面上有

10、在平面上有N個(gè)坦克，個(gè)坦克，M個(gè)鏡子。要求在平面內(nèi)個(gè)鏡子。要求在平面內(nèi)放置一個(gè)激光發(fā)射器，使放置一個(gè)激光發(fā)射器，使得它在發(fā)出的每束激光經(jīng)得它在發(fā)出的每束激光經(jīng)過(guò)不超越過(guò)不超越k次反射后擊中一次反射后擊中一切目的的前提下，間隔的切目的的前提下，間隔的最大值最小。最大值最小。N=4M=4k=2激光坦克激光坦克CTSC2007 N=4M=4k=2 此題是一個(gè)最大間隔此題是一個(gè)最大間隔最小的問(wèn)題，假設(shè)不思索最小的問(wèn)題，假設(shè)不思索鏡子的要素，可以運(yùn)用最鏡子的要素，可以運(yùn)用最遠(yuǎn)點(diǎn)遠(yuǎn)點(diǎn)Voronoi圖或前面的隨圖或前面的隨機(jī)增量算法來(lái)處理，但是機(jī)增量算法來(lái)處理，但是鏡子的存在使得問(wèn)題非常鏡子的存在使得問(wèn)題非

11、常棘手。棘手。激光坦克激光坦克CTSC2007 N=4M=4k=2 此時(shí)，模擬退火算法此時(shí)，模擬退火算法的可移植性的優(yōu)勢(shì)就表達(dá)的可移植性的優(yōu)勢(shì)就表達(dá)了出來(lái)，我們可以在主算了出來(lái)，我們可以在主算法的框架上，分別獨(dú)立編法的框架上，分別獨(dú)立編寫(xiě)與鏡子不同次數(shù)相交的寫(xiě)與鏡子不同次數(shù)相交的評(píng)價(jià)函數(shù)。評(píng)價(jià)函數(shù)。Testcasek不處置反射不處置反射處置一次反射處置一次反射處置兩次反射處置兩次反射601010102110101031010107111010521010108261010139101043101010930010105000總得分總得分568090代碼長(zhǎng)度代碼長(zhǎng)度90160240300 本文經(jīng)

12、過(guò)幾道例題，以及表達(dá)出的一種思本文經(jīng)過(guò)幾道例題，以及表達(dá)出的一種思想，希望能為大家翻開(kāi)一扇窗，在遇到幾想，希望能為大家翻開(kāi)一扇窗，在遇到幾何問(wèn)題的時(shí)候多一種思緒。當(dāng)然，隨機(jī)化何問(wèn)題的時(shí)候多一種思緒。當(dāng)然，隨機(jī)化思想的靈敏運(yùn)用，是在對(duì)于經(jīng)典問(wèn)題熟練思想的靈敏運(yùn)用，是在對(duì)于經(jīng)典問(wèn)題熟練掌握的前提下的，由于創(chuàng)新永遠(yuǎn)建立在扎掌握的前提下的，由于創(chuàng)新永遠(yuǎn)建立在扎實(shí)的根底之上。實(shí)的根底之上。zyx0有有3種物品的價(jià)錢設(shè)為種物品的價(jià)錢設(shè)為x, y, z要滿足要滿足n組約束組約束iiiiiRzcybxaL且且求求 的最大值的最大值czbyaxc解c解c解結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假

13、設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。想法：枚舉兩個(gè)平面，想法：枚舉兩個(gè)平面， 得到一條直線。得到一條直線。枚舉其他約束，枚舉其他約束，切割該直線。切割該直線。結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。結(jié)論結(jié)論1：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。：假設(shè)存在解，必然存在于三個(gè)平面的交點(diǎn)上。想法：枚舉兩個(gè)平面，想法：枚舉兩個(gè)平面， 得到一條直線。得到一條直線。枚舉其他約束，枚舉其他約束，切割該直線。切割該直線。直到最后剩下一直到最后剩下一條線段。條線段。引理引理1 只需線段的兩個(gè)端點(diǎn)能夠是的目的函數(shù)的只需線段的兩個(gè)端點(diǎn)能夠是的目的函數(shù)的

14、最大值。最大值。引理引理2 不會(huì)有某三個(gè)平面的交點(diǎn)被脫漏。不會(huì)有某三個(gè)平面的交點(diǎn)被脫漏。結(jié)論結(jié)論2：只需線段的兩個(gè)端點(diǎn)能夠成為解。：只需線段的兩個(gè)端點(diǎn)能夠成為解。引理引理1 只需線段的兩個(gè)端點(diǎn)能夠是的目的函數(shù)的最大值。只需線段的兩個(gè)端點(diǎn)能夠是的目的函數(shù)的最大值。引理引理2 不會(huì)有某三個(gè)平面的交點(diǎn)在計(jì)算中被脫漏。不會(huì)有某三個(gè)平面的交點(diǎn)在計(jì)算中被脫漏。 由于空間中的直線情況比較多、比較復(fù)雜，因此我們可以由于空間中的直線情況比較多、比較復(fù)雜，因此我們可以運(yùn)用參數(shù)方程進(jìn)展一致表示。運(yùn)用參數(shù)方程進(jìn)展一致表示。tzzztyyytxxx101010 這樣，我們對(duì)直線的切割就轉(zhuǎn)化成為對(duì)于參數(shù)值求交的過(guò)這樣，我

15、們對(duì)直線的切割就轉(zhuǎn)化成為對(duì)于參數(shù)值求交的過(guò)程。程。 最后是求解參數(shù)方程的過(guò)程。首先我們假設(shè)枚舉的兩個(gè)平最后是求解參數(shù)方程的過(guò)程。首先我們假設(shè)枚舉的兩個(gè)平面不平行，我們恣意消去面不平行，我們恣意消去x、y、z中的一個(gè)，得到一個(gè)二元中的一個(gè)，得到一個(gè)二元一元一次方程。取恣意一個(gè)自在元的方程的系數(shù)，經(jīng)過(guò)兩一元一次方程。取恣意一個(gè)自在元的方程的系數(shù)，經(jīng)過(guò)兩次回代即可求出直線的參數(shù)方程。次回代即可求出直線的參數(shù)方程。 這題實(shí)際上存在這題實(shí)際上存在O(n)復(fù)雜度的方法。但是該算法有兩點(diǎn)復(fù)雜度的方法。但是該算法有兩點(diǎn)弊?。罕撞。?1) 時(shí)間復(fù)雜度中隱藏的常數(shù)宏大。此題中在時(shí)間上的優(yōu)時(shí)間復(fù)雜度中隱藏的常數(shù)宏大

16、。此題中在時(shí)間上的優(yōu)勢(shì)微小。勢(shì)微小。n僅僅100。 2) 編程復(fù)雜度過(guò)大。其實(shí)編程復(fù)雜度過(guò)大。其實(shí)O(n)的算法并不難想：每次的算法并不難想：每次參與一個(gè)半空間后，假設(shè)先前的解不成立需求更新，此時(shí)參與一個(gè)半空間后，假設(shè)先前的解不成立需求更新，此時(shí)就是要將目的向量在平面上的投影作為新的目的向量，將就是要將目的向量在平面上的投影作為新的目的向量，將其他半空間轉(zhuǎn)換成半平面做一次二維線性規(guī)劃。幾次空間其他半空間轉(zhuǎn)換成半平面做一次二維線性規(guī)劃。幾次空間和平面間的轉(zhuǎn)換與旋轉(zhuǎn)，將該算法僅僅保管在實(shí)際上。和平面間的轉(zhuǎn)換與旋轉(zhuǎn)，將該算法僅僅保管在實(shí)際上。 我們運(yùn)用隨機(jī)思想是希望事半功倍、化繁為簡(jiǎn)，因此本算我們運(yùn)

17、用隨機(jī)思想是希望事半功倍、化繁為簡(jiǎn)，因此本算法有悖于我們的初衷。而且無(wú)論在信息學(xué)還是法有悖于我們的初衷。而且無(wú)論在信息學(xué)還是ACM賽場(chǎng)賽場(chǎng)上競(jìng)賽的時(shí)間都是有限的，因此本算法雖然存在，但并不上競(jìng)賽的時(shí)間都是有限的，因此本算法雖然存在，但并不值得推行。值得推行。 數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。這類算法數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計(jì)所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的添加不斷提高。在許多情況下，要計(jì)算算時(shí)間的添加不斷提高。在許多情況下，要計(jì)算出問(wèn)題的準(zhǔn)確解是不能夠或沒(méi)有必要的，因此用出問(wèn)題的準(zhǔn)確解是不能夠或沒(méi)有必要的，因此用數(shù)值

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

19、定算法中引入隨機(jī)性將它改呵斥一個(gè)舍伍德算法，消除或減少問(wèn)題的將它改呵斥一個(gè)舍伍德算法，消除或減少問(wèn)題的好壞實(shí)例間的這種差別。舍伍德算法精華不是防好壞實(shí)例間的這種差別。舍伍德算法精華不是防止算法的最壞情況的發(fā)生，而是設(shè)法消除這種最止算法的最壞情況的發(fā)生，而是設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法的壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法的一個(gè)最廣泛的運(yùn)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。一個(gè)最廣泛的運(yùn)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。這個(gè)問(wèn)題不復(fù)雜，以下代碼就可以以線性這個(gè)問(wèn)題不復(fù)雜，以下代碼就可以以線性的時(shí)間復(fù)雜度得到一個(gè)的時(shí)間復(fù)雜度得到一個(gè)1n的隨機(jī)陳列。的隨機(jī)陳列。記錄在數(shù)組記錄在數(shù)組O

20、中。中。Algorithm Random_shufflefor i 2 to n 交換交換Oi，Orandom(i)其中其中random(n)前往一個(gè)前往一個(gè)1n的隨機(jī)數(shù)。的隨機(jī)數(shù)。 它的根本思想是，對(duì)于所求的問(wèn)題，經(jīng)過(guò)它的根本思想是，對(duì)于所求的問(wèn)題，經(jīng)過(guò)實(shí)驗(yàn)的方法和大樣本來(lái)模擬，得到這個(gè)隨實(shí)驗(yàn)的方法和大樣本來(lái)模擬，得到這個(gè)隨機(jī)變量的期望值，并用它作為問(wèn)題的解。機(jī)變量的期望值，并用它作為問(wèn)題的解。它是以一個(gè)概率模型為根底，按照這個(gè)模它是以一個(gè)概率模型為根底，按照這個(gè)模型所描畫(huà)的過(guò)程，經(jīng)過(guò)模擬實(shí)驗(yàn)的結(jié)果，型所描畫(huà)的過(guò)程，經(jīng)過(guò)模擬實(shí)驗(yàn)的結(jié)果，作為問(wèn)題的近似解的過(guò)程。作為問(wèn)題的近似解的過(guò)程。 模擬退

21、火算法是一種元啟發(fā)式模擬退火算法是一種元啟發(fā)式Meta-Heuristics算算法，來(lái)源于固體退火原理，將固體加溫至充分高，再讓其法，來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)平衡態(tài)，最后在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小。根據(jù)平衡態(tài)，最后在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)那么，粒子在溫度準(zhǔn)那么，粒子在溫度T時(shí)趨于平衡的概率為時(shí)趨于平衡的概率為 ，其中，其中E為溫度為溫度T

22、時(shí)的內(nèi)能，時(shí)的內(nèi)能，E為其改動(dòng)量，為其改動(dòng)量，k為為Boltzmann常數(shù)。常數(shù)。Tte 元啟發(fā)式算法元啟發(fā)式算法Meta-Heuristics是一是一種啟發(fā)式戰(zhàn)略，意思就是指點(diǎn)啟發(fā)式算法種啟發(fā)式戰(zhàn)略，意思就是指點(diǎn)啟發(fā)式算法進(jìn)展任務(wù)的方法。常見(jiàn)的元啟發(fā)式算法有：進(jìn)展任務(wù)的方法。常見(jiàn)的元啟發(fā)式算法有： 模擬退火算法模擬退火算法 遺傳算法遺傳算法 蟻群算法蟻群算法 PSO(粒子群優(yōu)化粒子群優(yōu)化) 最優(yōu)解附近如點(diǎn)最優(yōu)解附近如點(diǎn)A，B的點(diǎn)非常稀少且的點(diǎn)非常稀少且間隔很遠(yuǎn)，因此有候選解在它周圍所在間隔很遠(yuǎn)，因此有候選解在它周圍所在的的Delaunay三角剖分區(qū)域內(nèi)的概率是三角剖分區(qū)域內(nèi)的概率是很大的。而且此時(shí)的間隔比較大，我們對(duì)很大的。而且此時(shí)的間隔比較大，我們對(duì)方向進(jìn)展多次嘗試，因此調(diào)整出去的概率方向進(jìn)展多次嘗試，因此調(diào)整出去的概率也很小。也很小。 如圖