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

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

2、 第二部分第二部分 隨機(jī)增量算法隨機(jī)增量算法 第三部分第三部分 模擬退火算法模擬退火算法 Expensive Drink ( Beijing Site, 2007 )（經(jīng)過(guò)抽象）（經(jīng)過(guò)抽象） 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)問(wèn)題的本質(zhì)發(fā)現(xiàn)問(wèn)題的本質(zhì) 提出算法提出算法 改造成增量算法改造成增量算法 加入隨機(jī)加入隨機(jī) c 解 c 解 c 解 結(jié)論結(jié)論1：如果存在解，必然存在

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

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

5、：隨機(jī)插入 半空間的順序半空間的順序 c 復(fù)雜度仍舊為復(fù)雜度仍舊為 O(n3) 對(duì)策：隨機(jī)插入對(duì)策：隨機(jī)插入 半空間的順序半空間的順序 取隨機(jī)變量取隨機(jī)變量Xi，若滿足前，若滿足前i-1條約束的最條約束的最 優(yōu)解滿足第優(yōu)解滿足第i條約束，則條約束，則Xi=0，否則，否則Xi=1。 時(shí)間復(fù)雜度為時(shí)間復(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è)約束構(gòu)成，恰個(gè)約束構(gòu)成，恰 好包括第好包括第i條約束的概率就是條約束的概率就是 。 i XE i 3 2 1 2 3 nO i

6、iO n i 在本題中，增量算法架筑起了線性規(guī)劃問(wèn)在本題中，增量算法架筑起了線性規(guī)劃問(wèn) 題與經(jīng)典幾何知識(shí)的橋梁，隨機(jī)化思想則題與經(jīng)典幾何知識(shí)的橋梁，隨機(jī)化思想則 消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。消除了輸入數(shù)據(jù)的順序?qū)τ趶?fù)雜度的影響。 本題也體現(xiàn)出隨機(jī)算法簡(jiǎn)單、快速（相對(duì)本題也體現(xiàn)出隨機(jī)算法簡(jiǎn)單、快速（相對(duì) 于單純形法）的特點(diǎn)。于單純形法）的特點(diǎn)。 下面將介紹論文中的第二個(gè)算法：模擬退下面將介紹論文中的第二個(gè)算法：模擬退 火算法?；鹚惴?。 模擬退火（模擬退火（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并計(jì)算評(píng)價(jià)函數(shù)并計(jì)算評(píng)價(jià)函數(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圖解，并圖解，并 對(duì)頂點(diǎn)集合進(jìn)行對(duì)頂點(diǎn)

8、集合進(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)的最小距離最大。 通過(guò)類比的思想，通過(guò)類比的思想， 引入模擬退火算法：引入模擬退火算法： 隨機(jī)初始解，隨機(jī)初始解， 溫度溫度T定義為調(diào)整定義為調(diào)整 向量的模長(zhǎng)。估價(jià)向量的模長(zhǎng)。估價(jià) 函數(shù)定義為到最近函數(shù)定義為到最近 點(diǎn)的距離。點(diǎn)的距離。 如果函數(shù)值變?nèi)绻瘮?shù)值變 大，則更新原解。大，則更新原解。 隨機(jī)初始解，隨機(jī)初始解， 溫度溫度T定義為調(diào)整定義為調(diào)整 向量的模長(zhǎng)。估價(jià)向量的模長(zhǎng)。估價(jià) 函數(shù)定義為到最近

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

10、模擬退火算法有很強(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） 在平面上有在平面上有N個(gè)坦克，個(gè)坦克， M個(gè)鏡子。要求在平面內(nèi)個(gè)鏡子。要求在平面內(nèi) 放置一個(gè)激光發(fā)射器，使放置一個(gè)激光發(fā)射器，使 得它在發(fā)出的每束激光經(jīng)得它在發(fā)出的每束激光經(jīng) 過(guò)不超過(guò)過(guò)不超過(guò)k次反射后擊中所次反射后

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

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

13、大家打開(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)題熟練 掌握的前提下的，因?yàn)閯?chuàng)新永遠(yuǎn)建立在扎掌握的前提下的，因?yàn)閯?chuàng)新永遠(yuǎn)建立在扎 實(shí)的基礎(chǔ)之上。實(shí)的基礎(chǔ)之上。 zyx0 有有3種物品的價(jià)格（設(shè)為種物品的價(jià)格（設(shè)為x, y, z）要滿足）要滿足n組約束組約束 iiiii RzcybxaL 且且 求求 的最大值的最大值czbyax c 解 c 解 c 解 結(jié)論結(jié)論1：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。 想法：枚舉兩個(gè)平面，想法：枚舉兩

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

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

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

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

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

19、沒(méi)有必要的，因此用 數(shù)值概率算法可得到滿意的解。數(shù)值概率算法可得到滿意的解。 舉個(gè)例子：計(jì)算舉個(gè)例子：計(jì)算p 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 p近似等于近似等于4 4k/n。 舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的 解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下 的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有 較大差別時(shí)，可以在這

20、個(gè)確定算法中引入隨機(jī)性較大差別時(shí)，可以在這個(gè)確定算法中引入隨機(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īng)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。一個(gè)最廣泛的應(yīng)用就是快速排序的隨機(jī)化實(shí)現(xiàn)。 這個(gè)問(wèn)題不復(fù)雜，以下代碼就可以以線性這個(gè)問(wèn)題不復(fù)雜，以下代碼就可以以線性 的時(shí)間復(fù)雜度得到一個(gè)的時(shí)間復(fù)雜

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

22、型所描繪的過(guò)程，通過(guò)模擬實(shí)驗(yàn)的結(jié)果， 作為問(wèn)題的近似解的過(guò)程。作為問(wèn)題的近似解的過(guò)程。 模擬退火算法是一種元啟發(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時(shí)的內(nèi)能，時(shí)的內(nèi)能，E為其改變量，為其改變量，k為為 Boltzmann常數(shù)。常數(shù)。 T t e 元啟發(fā)式算法（元啟發(fā)式算法（Meta-Heuristics）是一）是一 種啟發(fā)式策略，意思就是指導(dǎo)啟發(fā)式算法種啟發(fā)式策略，意思就是指導(dǎo)啟發(fā)式算法 進(jìn)行工作的方法。常見(jiàn)的元啟發(fā)式算法有：進(jìn)行工作的方法。常見(jiàn)的元啟發(fā)式算法有： 模擬退火算法模擬退火算法 遺傳算法遺傳算法 蟻群算法蟻群算法 PSO(粒子群優(yōu)化粒子群優(yōu)化) 最優(yōu)解附近（如點(diǎn)最優(yōu)解附近（如點(diǎn)A，B）的點(diǎn)非