上帝擲骰子嗎.pptx

《上帝擲骰子嗎.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、上帝擲色子嗎謝其哲Introduction上帝擲色子嗎->隨機(jī)和概率能力：1.很大概率上的正確解2.較優(yōu)解3.期望時(shí)間復(fù)雜度很好的正確解效果好最好寫的平衡樹Treap期末時(shí)當(dāng)你開始預(yù)習(xí)數(shù)據(jù)結(jié)構(gòu)的平衡樹是什么感受？AVL，紅黑，AA……Whatthef*ckaretheseuglytrees?被嚇倒了？來(lái)看看居家旅行殺人越貨必備之平衡樹：Treap最好寫的平衡樹Treap堆+排序二叉樹權(quán)值：key,aux。Key：左子樹≤根≤右子樹（排序二叉樹）Aux:根≤左子樹，右子樹（堆）最好寫的平衡樹Treap插入：根據(jù)key找到插入的位

2、置隨機(jī)生成aux，旋轉(zhuǎn)調(diào)整最好寫的平衡樹TreapInsert(I,k)If(i==0)新建點(diǎn)，aux[i]=rand()If(kaux[i])left(i)最好寫的平衡樹TreapDelete差不多，只有單旋期望高度：O(logn)平均復(fù)雜度：O(logn)素?cái)?shù)判定Miller-Rabin算法O()->O(logn)費(fèi)馬小定理：(p為素?cái)?shù),a

3、為合數(shù)時(shí)，x取值有很多，如素?cái)?shù)判定Miller-Rabin算法令，d為奇數(shù)若或，則稱p通過(guò)以a為底的素性測(cè)試（為素?cái)?shù)）。原理：若p為素?cái)?shù)，則考慮數(shù)列.最后一位是1，每一位是前一位的平方%p，設(shè)數(shù)列最后一個(gè)1的前一個(gè)是x，若x≠-1則p為合數(shù)。例子：a=2，p=13，p-1=12=數(shù)列：8,64%13=12,144%13=1素?cái)?shù)判定Miller-Rabin算法素?cái)?shù)一定會(huì)通過(guò)測(cè)試合數(shù)有1/4的概率通過(guò)測(cè)試取6次不同的底a，誤判率不到千分之二取內(nèi)無(wú)誤判。判斷A*B=C?Problem:給定A，B，C(n*n的矩陣)，判斷是否A*B=

4、C隨機(jī)生成D(1*n的矩陣)，判斷是否D*A*B=D*C平面最近點(diǎn)對(duì)O(logn)兩點(diǎn)距離≥X值的差解1:(對(duì)隨機(jī)數(shù)據(jù)效果很好)把輸入的點(diǎn)按x從小到大排序Fori=1tonforj=i+1tonif(x[j]–x[i]

5、三個(gè)點(diǎn)為頂點(diǎn)的三角形，使其周長(zhǎng)最小。傳統(tǒng)算法：O(nlogn)，難寫，常數(shù)大O(n^3)隨機(jī)向量投影，O(n^3)+break比O(nlogn)快費(fèi)馬點(diǎn)問題給定n個(gè)點(diǎn)，求一個(gè)點(diǎn)到這n個(gè)點(diǎn)的距離和最小。費(fèi)馬點(diǎn)爬山算法:(求局部最優(yōu)解)隨機(jī)設(shè)置一個(gè)初始點(diǎn)b，設(shè)置初始步長(zhǎng)TWhileT>T_minFlag=falseFori=1tok生成長(zhǎng)度為T的隨機(jī)向量vIfb+v優(yōu)于bb=b+v,flag=trueIf(flag==false)T=T*0.8模擬退火原理：熱力學(xué)退火過(guò)程，給固體設(shè)置一個(gè)充分高的溫度，溫度高時(shí)，原子容易脫離原位置做

6、自由運(yùn)動(dòng)。再讓其慢慢冷卻。冷卻時(shí)原子會(huì)趨向內(nèi)能最小的地方，但也有一定概率去內(nèi)能較大的地方，直到溫度足夠低。流程：初始溫度T，初始解S，每次迭代次數(shù)L，降溫系數(shù)pWhileT>T_minFlag=falseFork=1toL隨機(jī)長(zhǎng)度為T的增量D，S’=S+D計(jì)算df=f(S’)-f(S)df>0時(shí)(變優(yōu)了)接受解S’,flag=truedf<0時(shí)(變差了)以接受解S’If(flag==false)T=T*p最小正方形覆蓋(poj3301)枚舉正方形一條邊的角度，計(jì)算最小需要的邊長(zhǎng)。初始溫度T=pi/2,角度S=0，每次迭代次數(shù)L

7、=20,降溫系數(shù)p=0.5WhileT>1e-8Flag=falseFork=1toLt=T*(-1到1中的一個(gè)隨機(jī)數(shù))df=f(S)-f(S+t)（f(S)為一條邊角度為S時(shí)最小正方形邊長(zhǎng)）df>0時(shí)接受解S’,flag=truedf<0時(shí)以接受解S’（）If(flag==false)T=T*p遺傳算法原理：達(dá)爾文進(jìn)化論和遺傳學(xué)機(jī)理有n個(gè)個(gè)體（DNA序列），按照適應(yīng)度（權(quán)值）從高到低排序。繁殖：選出兩個(gè)個(gè)體，以高概率選擇適應(yīng)度高的，低概率選擇適應(yīng)度低的，以一定概率P交配得出兩個(gè)新個(gè)體代替原來(lái)的老個(gè)體，新個(gè)體的DNA是老個(gè)體D

8、NA的組合。突變：以一定概率隨機(jī)改變序列的一到兩位。重復(fù)適應(yīng)度高的個(gè)體得到保存，適應(yīng)度低的個(gè)體淘汰。拓展遺傳算法與蒙娜麗莎TSP問題->模擬退火謝謝！