非完美算法初探——任一恒

1、非完美算法初探1完美算法非節(jié)省空間更快速方便壓縮2比賽題目標(biāo)準(zhǔn)算法可采用算法NOI追捕盜賊樹搜索分治貪心CTSC激光坦克/智能貪心矩陣網(wǎng)絡(luò)流構(gòu)造貪心隨機(jī)IOI船帆/貪心調(diào)整冬令營剪刀石頭布網(wǎng)絡(luò)流貪心調(diào)整2007年部分應(yīng)用非完美算法效果不錯的題目3一、隨機(jī)算法二、貪心算法四、模擬退火算法五、等等算法_三、抽樣測試法4三、抽樣測試法抽樣，即從統(tǒng)計總體中，任意抽出一部分單位作為樣本，并以其結(jié)果推算總體的相應(yīng)指標(biāo)。在某些問題中，需要讓我們檢查一系列測試元s，如果s中的某個測試元滿足了某個條件，那么則說s滿足了某個性質(zhì)。在大度數(shù)情況下，我們需要將s中的測試元一個一個的進(jìn)行驗證，才能確定s是否滿足該性質(zhì)。

2、但是如果s滿足如下性質(zhì)，要不s中不含滿足條件的測試元，要不滿足某條件的測試元很多，則可以直接選取幾個具有代表性的測試元進(jìn)行測試，通過這幾個測試元來確定s是否滿足該性質(zhì)。 5質(zhì)數(shù)檢驗質(zhì)數(shù)n，基底1n-1，必為強(qiáng)偽質(zhì)數(shù)對于一個整數(shù)n，設(shè)n-1=d*2s(d是奇數(shù))，對于給定的基底a，如果存在ad=1(mod n)或者對于0=rs，存在a(d*2r)=-1(mod n)則稱n是以a為基底的強(qiáng)偽質(zhì)數(shù)。 合數(shù)n，基底1n-1，1/4為強(qiáng)偽質(zhì)數(shù)6質(zhì)數(shù)檢驗以2為基底隨機(jī)抽取效率不高！2047137365325326001以2 3為基底以2 3 5為基底以2 3 5 7為基底固定取樣最小質(zhì)數(shù)。7例題 緊急修復(fù)

3、（百度之星 2007）某市的k家公司的計算機(jī)系統(tǒng)全部癱瘓，要在T小時之后才能自動修復(fù)，每家公司每小時都在受到損失，第i家公司每小時受損為P(i)，現(xiàn)在派遣n只維修隊進(jìn)行搶修，力求在自動修復(fù)之前將損失降到最小。 城市被劃分為r*c的網(wǎng)格，現(xiàn)給出了第個公司的坐標(biāo)(r(i), c(i)，該公司的受損程度B(i)隊小時。還給出了每個維修隊的初始坐標(biāo)，每小時每個維修隊可以移動（最多s格），也可以維修它所處在的格子中的公司，現(xiàn)在希望你設(shè)計一種方案使損失降低到最小。 8分析全局分析：每步產(chǎn)生一個全局最優(yōu)方案估價函數(shù)要求高，實現(xiàn)難度大舍棄極端想法：讓所有隊伍依次修理每個公司9實現(xiàn)1、預(yù)處理：計算每家公司到每個

4、點的距離。2、安排修理的順序。3、按照修理順序計算每個修理隊的活動（能參與維修的趕過去）。4、計算損失。10修理順序的選擇關(guān)鍵修理順序。每種順序損失的計算復(fù)雜度低模擬退火。11模擬退火模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為E-E/(kT)，其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。12模擬退火用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫

5、度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解計算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子t、每個t值時的迭代次數(shù)L和停止條件S。 13模擬退火基本思想(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L (2) 對k=1，L做第3至第6步： (3) 產(chǎn)生新解S (4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數(shù) (5) 若t0，然后轉(zhuǎn)第2步。 14模擬退火注意點(1)溫度T的初始值設(shè)置問題 (2) 退火速度問題 (3)溫度管理問題 關(guān)聯(lián)損失 L=20 Div 215小技巧優(yōu)化初始解生成新解：翻轉(zhuǎn)兩邊/翻轉(zhuǎn)中間 B(I)/P(I)Q (w1, w2 ,，wq , wq+1 ,，wp ,，wn) (wq, wq-1 ,，w1 , wq+1 ,，wn ,，wp)PQ (w1, w2 ,，wp , wp+1