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