3，回溯算法 back tracking
4，博弈 game theory
其中最主要的就是LP找最優(yōu)解了。這門(mén)課每個(gè)星期都要交作業(yè)，每次都要和同組的同學(xué)要在一起費(fèi)力的做幾個(gè)小時(shí)才能完成。可以說(shuō)這門(mén)課和另外一門(mén)同樣也是每個(gè)禮拜都交作業(yè)的SPEZMOL都是尤其花費(fèi)功夫的課程。不過(guò)現(xiàn)在回頭看來(lái)，復(fù)習(xí)的時(shí)候倒也就不是那么的恐怖了，只是希望考試的時(shí)候能有足夠的時(shí)間來(lái)解題。
再過(guò)2天，17號(hào)的上午就是Algo.的考試了，這兩天會(huì)集中精力復(fù)習(xí)，白天估計(jì)會(huì)和同學(xué)一起在圖書(shū)館復(fù)習(xí)，晚上回來(lái)以后如果還有時(shí)間的話，就自己在這里做個(gè)整理吧。
局域搜索 local search
對(duì)于一些問(wèn)題并不一定非得要全局的最優(yōu)解，有的時(shí)候只要是能解決最優(yōu)解的次優(yōu)解也是可以接受的。這時(shí)就可以將求全局最優(yōu)解簡(jiǎn)化為求局域最優(yōu)解。同時(shí)也為了讓初始狀態(tài)對(duì)結(jié)果影響太大，而獲得更好的效果，還需要多試幾次隨機(jī)設(shè)定的初始狀態(tài)。
為了解決上面的問(wèn)題，還有一種辦法就是模擬自然界中的物理模型（模擬煺火）。在自然界中，當(dāng)一個(gè)很熱的金屬物體在降溫時(shí)，雖然從整體上而言分子都是從高位勢(shì)能往低位勢(shì)能的位置運(yùn)動(dòng)；但是就單個(gè)分子而言其運(yùn)動(dòng)是無(wú)規(guī)律的。不過(guò)這種無(wú)序運(yùn)動(dòng)的程度卻受溫度的影響。也就是說(shuō)，溫度越高，無(wú)序程度越高。對(duì)應(yīng)到模擬煺火算法則是有一定的概率使得某狀態(tài)向成本更高的相鄰狀態(tài)運(yùn)動(dòng)。而這個(gè)概率受運(yùn)算時(shí)間長(zhǎng)短的影響。
LP線性規(guī)劃
1，首先介紹的是一些基本概念，比如什么是線性規(guī)劃，目標(biāo)方程式等。這是通過(guò)一個(gè)最常見(jiàn)的生產(chǎn)啤酒的例子進(jìn)行的說(shuō)明。其中最難的是模型的建立，即變量、目標(biāo)方程式以及約束條件的設(shè)計(jì)。
2，然后就是如何從通用表達(dá)式向標(biāo)準(zhǔn)表達(dá)式轉(zhuǎn)換。即，s1，將所有的未限定的變量通過(guò)一對(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，再接下來(lái)的是，所有的IP問(wèn)題都是成對(duì)的。也就是說(shuō)，如果所求的是最大值，那么一定有一個(gè)和其對(duì)應(yīng)的求最小值的IP問(wèn)題。而這兩個(gè)問(wèn)題實(shí)質(zhì)上是同一個(gè)問(wèn)題。而剝?nèi)?shí)際意義，單純從數(shù)學(xué)角度上，這個(gè)問(wèn)題可以這么理解：
原來(lái)是求 max(c*x) 約束條件是 A * X <= b
那么對(duì)應(yīng)的最小值問(wèn)題則是 min(b*y) 約束條件是 A′ * y >= c
5，LP問(wèn)題還可以進(jìn)一步分為ILP，RLP問(wèn)題。即，所求的解必須是整數(shù)還是實(shí)數(shù)。很明顯ILP是難于RLP的。已經(jīng)得到證明的是，ILP 是NP完全的。所以，對(duì)于一些ILP問(wèn)題，可以用近似解的方法來(lái)求解。方法是：s1，將ILP轉(zhuǎn)換為RLP（konsistent）并求解；s2，檢驗(yàn)所求得的解是否正確（richtig）。
回溯算法 back tracking
回溯算法有點(diǎn)類似與深度優(yōu)先的搜索算法。即，深度優(yōu)先遍歷所以解集空間，通常是一棵樹(shù)。從根節(jié)點(diǎn)開(kāi)始，到第一個(gè)葉子節(jié)點(diǎn)，再回溯到上一層，然后進(jìn)入上一層的其它葉子節(jié)點(diǎn)，如果上一層的所有葉子節(jié)點(diǎn)都已經(jīng)遍歷過(guò)了，就再回溯至更上一層，并以此類推直至遍歷完成。
偽碼算法如下：
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ù)，用于剪去那些肯定沒(méi)必要訪問(wèn)的子樹(shù)。