|
|
其實(shí)這門課開始的時(shí)候非常非常的擔(dān)心。因?yàn)樵诒究频臅r(shí)候著實(shí)沒有認(rèn)真學(xué)過算法和數(shù)據(jù)結(jié)構(gòu)。更確切的說，大學(xué)四年，專業(yè)知識(shí)幾乎就沒怎么認(rèn)真學(xué)過，導(dǎo)致如今還在努力的填著當(dāng)年留下的空缺。
不過慶幸的是，這門課對(duì)基礎(chǔ)的要求并不是很高，需要回頭補(bǔ)得東西倒也不是很多。也算是幸運(yùn)吧。
Algo.這門課主要內(nèi)容就4點(diǎn)：
1，局域搜索 local search
2，線性規(guī)劃 LP
3，回溯算法 back tracking
4，博弈 game theory
其中最主要的就是LP找最優(yōu)解了。這門課每個(gè)星期都要交作業(yè)，每次都要和同組的同學(xué)要在一起費(fèi)力的做幾個(gè)小時(shí)才能完成。可以說這門課和另外一門同樣也是每個(gè)禮拜都交作業(yè)的SPEZMOL都是尤其花費(fèi)功夫的課程。不過現(xiàn)在回頭看來，復(fù)習(xí)的時(shí)候倒也就不是那么的恐怖了，只是希望考試的時(shí)候能有足夠的時(shí)間來解題。
再過2天，17號(hào)的上午就是Algo.的考試了，這兩天會(huì)集中精力復(fù)習(xí)，白天估計(jì)會(huì)和同學(xué)一起在圖書館復(fù)習(xí)，晚上回來以后如果還有時(shí)間的話，就自己在這里做個(gè)整理吧。
局域搜索 local search
對(duì)于一些問題并不一定非得要全局的最優(yōu)解，有的時(shí)候只要是能解決最優(yōu)解的次優(yōu)解也是可以接受的。這時(shí)就可以將求全局最優(yōu)解簡化為求局域最優(yōu)解。同時(shí)也為了讓初始狀態(tài)對(duì)結(jié)果影響太大，而獲得更好的效果，還需要多試幾次隨機(jī)設(shè)定的初始狀態(tài)。
為了解決上面的問題，還有一種辦法就是模擬自然界中的物理模型（模擬煺火）。在自然界中，當(dāng)一個(gè)很熱的金屬物體在降溫時(shí)，雖然從整體上而言分子都是從高位勢(shì)能往低位勢(shì)能的位置運(yùn)動(dòng)；但是就單個(gè)分子而言其運(yùn)動(dòng)是無規(guī)律的。不過這種無序運(yùn)動(dòng)的程度卻受溫度的影響。也就是說，溫度越高，無序程度越高。對(duì)應(yīng)到模擬煺火算法則是有一定的概率使得某狀態(tài)向成本更高的相鄰狀態(tài)運(yùn)動(dòng)。而這個(gè)概率受運(yùn)算時(shí)間長短的影響。
LP線性規(guī)劃
1，首先介紹的是一些基本概念，比如什么是線性規(guī)劃，目標(biāo)方程式等。這是通過一個(gè)最常見的生產(chǎn)啤酒的例子進(jìn)行的說明。其中最難的是模型的建立，即變量、目標(biāo)方程式以及約束條件的設(shè)計(jì)。
2，然后就是如何從通用表達(dá)式向標(biāo)準(zhǔn)表達(dá)式轉(zhuǎn)換。即，s1，將所有的未限定的變量通過一對(duì)變量轉(zhuǎn)換為大于零的被限定的變量;s2將所有不等式用松弛變量轉(zhuǎn)變成等式。
3，再用simplex算法求最優(yōu)解。在物理意義上，即轉(zhuǎn)換成凸多邊形，然后找最優(yōu)的頂點(diǎn)。步驟：s1，計(jì)算得到一個(gè)基礎(chǔ)解；s2，得到一個(gè)可行的基礎(chǔ)解；s3，得到最優(yōu)解。
4，再接下來的是，所有的IP問題都是成對(duì)的。也就是說，如果所求的是最大值，那么一定有一個(gè)和其對(duì)應(yīng)的求最小值的IP問題。而這兩個(gè)問題實(shí)質(zhì)上是同一個(gè)問題。而剝?nèi)?shí)際意義，單純從數(shù)學(xué)角度上，這個(gè)問題可以這么理解：
原來是求 max(c*x) 約束條件是 A * X <= b
那么對(duì)應(yīng)的最小值問題則是 min(b*y) 約束條件是 A′ * y >= c
5，LP問題還可以進(jìn)一步分為ILP，RLP問題。即，所求的解必須是整數(shù)還是實(shí)數(shù)。很明顯ILP是難于RLP的。已經(jīng)得到證明的是，ILP 是NP完全的。所以，對(duì)于一些ILP問題，可以用近似解的方法來求解。方法是：s1，將ILP轉(zhuǎn)換為RLP（konsistent）并求解；s2，檢驗(yàn)所求得的解是否正確（richtig）。
回溯算法 back tracking
回溯算法有點(diǎn)類似與深度優(yōu)先的搜索算法。即，深度優(yōu)先遍歷所以解集空間，通常是一棵樹。從根節(jié)點(diǎn)開始，到第一個(gè)葉子節(jié)點(diǎn)，再回溯到上一層，然后進(jìn)入上一層的其它葉子節(jié)點(diǎn)，如果上一層的所有葉子節(jié)點(diǎn)都已經(jīng)遍歷過了，就再回溯至更上一層，并以此類推直至遍歷完成。
偽碼算法如下：
Algorithm Backtrack(l，x(1)，....，x(l-1))
Input: l ( depth l is natural number)， partial solution (x(1)，....，x(l-1))
Output: optimal solution (x(1)，....，x(l-1)) in a global variable
if x(1)，....，x(l-1) is a valid solution then
compute the value of (x(1)，....，x(l-1))
else
compute Cl
for all x belong to Cl do Backtrack(l+1 ， (x(1)，....，x(l-1))，x) end for
end if
其中 Cl 是選擇后的解集，而不是笛卡爾的所有解集空間。
所以我們需要的是
上面的算法雖然正確，但是效率卻很低，當(dāng)解集空間特別大時(shí)，那么需要的時(shí)間將非常恐怖。所以這個(gè)時(shí)候就需要提高效率。其中一個(gè)很有效的方法就是bounding function。即，建立一個(gè)限定函數(shù)，用于剪去那些肯定沒必要訪問的子樹。
具體說明的例子，看說明時(shí)候有空再添加吧。
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
