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