⑴ 優化演算法筆記（一）優化演算法的介紹
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。
演算法本質是一種按照固定步驟執行的過程。
優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。
等冪性即 對於同樣的輸入，輸出是相同的 。
比如圖1，對於給定的魚和給定的熊掌，我們在相同的條件下一定可以知道它們誰更重，當然，相同的條件是指魚和熊掌處於相同的重力作用下，且不用考慮水分流失的影響。在這些給定的條件下，我們（無論是誰）都將得出相同的結論，魚更重或者熊掌更重。我們可以認為，秤是一個等冪性的演算法（工具）。
現在把問題變一變，問魚與熊掌你更愛哪個，那麼現在，這個問題，每個人的答案可能不會一樣，魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問，哪個更重，和更喜歡哪個這兩個問題一個是客觀問題，一個是主觀問題，主觀問題沒有確切的答案的。當我們處理主觀問題時，也會將其轉換成客觀問題，比如給喜歡魚和喜歡熊掌的程度打個分，再去尋求答案，畢竟計算機沒有感情，只認0和1（量子計算機我不認識你）。
說完了等冪性，再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。
有一場考試，考試的內容全部取自課本，同時老師根據自己的經驗給同學們劃了重點，但是因為試卷並不是該老師所出，也會有考試內容不在重點之內，老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試，學霸為了考滿分所以無視重點，學渣為了pass，因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。
當重點跟上圖一樣的時候，所有的內容都是重點的時候，學霸和學渣的學習策略變成了相同的策略，則score(學霸)=score(學渣)。但同時，學渣也要付出跟學霸相同的努力去學習這些內容，學渣心裡苦啊。
當課本如下圖時
學霸？學霸人呢，哪去了快來學習啊，不是說學習一時爽，一直學習一直爽嗎，快來啊，還等什麼。
這時，如果重點內容遠少於書本內容時，學渣的學習策略有了優勢——花費的時間和精力較少。但是同時，學渣的分數也是一個未知數，可能得到80分也可能拿到100分，分數完全取決於重點內容與題目的契合度，契合度越高，分數越高。對學渣來說，自己具體能考多少分無法由自己決定，但是好在能夠知道大概的分數范圍。
學霸的學習策略是一種遍歷性演算法，他會遍歷、通讀全部內容，以保證滿分。
學渣的學習策略則是一種概率演算法，他只會遍歷、學習重點內容，但至於這些重點是不是真重點他也不知道。
與遍歷演算法相比，概率演算法的結果具有不確定性，可能很好，也可能很差，但是會消耗更少的資源，比如時間（人生），空間（記憶）。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ，在現實中體現於節省時間，使用很少的時間得到一個不與最優解相差較多的結果。
「莊子：吾生也有涯，而知也無涯；以有涯隨無涯，殆矣。」的意思是：人生是有限的，但知識是無限的（沒有邊界的），用有限的人生追求無限的知識，是必然失敗的。
生活中概率演算法（思想）的應用其實比較廣泛，只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論，比如墨菲定律和倖存者偏差，此處不再詳述。
上面說到，優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢？因為優化演算法是一種概率演算法，執行一次操作就得到最優結果幾乎是不可能的，重復多次取得最優的概率也會增大。
栗子又來了，要從1-10這10個數中取出一個大於9的數，只取1次，達到要求的概率為10%，取2次，達到要求的概率為19%。
可以看出取到第10次時，達到要求的概率幾乎65%，取到100次時，達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎？非也，這並不是一個恰當的例子，因為每次取數的操作之間是相互獨立的，第2次取數的結果不受第1次取數結果的影響，假設前99次都沒達到要求，那麼再取一次達到要求的概率跟取一次達到要求的概率相同。
優化演算法中，後一次的計算會依賴前一次的結果，以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。
由鐵組成的鏈叫做鐵鏈，同理可得，馬爾可夫鏈就是馬爾可夫組成的鏈。
言歸正傳, 馬爾可夫鏈（Markov Chain, MC） ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時，我都會陷入沉思，生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活，今天的努力決定明天的生活」，你的下一份工作的工資大多由你當前的工資決定，這些都與馬爾可夫鏈有異曲同工之處。
還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3，那麼下次只能在3-10這幾個數中取，這樣一來，達到目標的概率應該會顯著提升。還是用數據說話。
取1次達到要求的概率仍然是
取2次內達到要求的概率為
取3次內達到要求的概率為
取4次內……太麻煩了算了不算了
可以看出基於馬爾可夫鏈來取數時，3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢？原因一，其實現方式不是那麼簡單，例子中我們規定了取數的規則是復合馬爾可夫鏈的，而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二，並不是所有的問題都符合馬爾科夫鏈條件，比如原子內電子出現的位置，女朋友為什麼會生（lou）氣，彩票號碼的規律等，建立模型必須與問題有相似之處才能較好的解決問題。
介紹完了優化演算法，再來討論討論優化演算法的使用場景。
前面說了優化演算法是一種概率演算法，無法保證一定能得到最優解，故如果要求結果必須是確定、穩定的值，則無法使用優化演算法求解。
例1，求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵，那麼其結果必定是唯一確定的值，因為修路寸土寸金，必須選取最優解使花費最少。但如果結果是用來趕路，那麼即使沒有選到最優的路線，我們可能也不會有太大的損失。
例2，求城市a與城市b間的最短路線，即使有兩條路徑，路徑1和路徑2，它們從a到b的距離相同，我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下，求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案，因為最短的線路可能並不是最快的路線，還需要考慮到天氣，交通路況等因素，該問題的結果是一個動態的結果，不同的時間不同的天氣我們很可能得出不同的結果。
現實生產、生活中，也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體，停車場車牌識別，人臉識別等，其底層參數可能使用了優化演算法來加速參數計算，其參數的細微差別對結果的影響不太大，需要較快的得出誤差范圍內的參數即可；電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂，我們會發現每次刷新時，推給我們的商品都有幾個會發生變化，而且隨著我們對商品的瀏覽，系統推給我們的商品也會發生變化，其結果是動態變化的；打車軟體的訂單系統，會根據司機和客人的位置，區域等來派發司機給客人，不同的區域，不同的路況，派發的司機也是動態變化的。
綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。
前面說過，優化演算法處理的問題都是客觀的問題，如果遇到主觀的問題，比如「我孰與城北徐公美」，我們需要將這個問題進行量化而轉換成客觀的問題，如身高——「修八尺有餘」，「外貌——形貌昳麗」，自信度——「明日徐公來，孰視之，自以為不如；窺鏡而自視，又弗如遠甚」，轉化成客觀問題後我們可以得到各個解的分數，通過比較分數，我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程，建立的問題模型實際上是一個函數，這個函數對優化演算法來說是一個黑盒函數，即不需要知道其內部實現只需要給出輸入，得到輸出。
在優化演算法中這個黑盒函數叫做 適應度函數 ， 優化演算法的求解過程就是尋找適應度函數最優解的過程 ，使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型，一旦合適的模型建立完成，我們就可以愉快的使用優化演算法來求解問題啦。（「合適」二字談何容易）
優化演算法的大致介紹到此結束，後面我們會依次介紹常見、經典的優化演算法，並探究其參數對演算法性能的影響。
——2019.06.20
[目錄]
[下一篇 優化演算法筆記（二）優化演算法的分類]
⑵ python演算法設計的步驟有三步分別是
1. 弄清楚題目的意思，列出題目的輸入、輸出、約束條件
其中又一道題目是這樣的：「有一個mxn的矩陣，每一行從左到右是升序的，每一列從上到下是升序的。請實現一個函數，在矩陣中查找元素elem，找到則返回elem的位置。」題設只說了行和列是升序的，我在草稿紙上畫了一個3x4的矩陣，裡面的元素是1~12，於是我就想當然的認為矩陣的左上角是最小的元素，右下角是最大的元素。於是整個題目的思考方向就錯了。
2. 思考怎樣讓演算法的時間復雜度盡可能的小
繼續以上面的題目為例子。可以有如下幾種演算法：
a. 遍歷整個矩陣進行查找，那麼復雜度為O(m*n)；
b. 因為每一行是有序的，所以可以對每一行進行二分查找，復雜度為O(m*logn)。但是這樣只用到了行有序的性質。
c. 網上查了一下，最優的演算法是從矩陣的左下角開始，比較左下角的元素（假設為X）與elem的大小，如果elem比X大，那麼X所在的那一列元素就都被排除了，因為X是該列中最大的了，比X還大，那麼肯定比X上面的都大；如果elem比X小，那麼X所在的那一行就可以排除了，因為X是這一行里最小的了，比X還小那麼肯定比X右邊的都小。每迭代一次，矩陣的尺寸就縮小一行或一列。復雜度為O(max(m,n))。
可以先從復雜度較高的實現方法入手，然後再考慮如何利用題目的特定條件來降低復雜度。
3. 編寫偽代碼或代碼
⑶ 求最優路徑的演算法
以下是C寫的廣度優先的最短路徑窮舉法,希望對你有所幫助.
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define SIGHTS 4 //自定義景點個數為4，以後可以擴充
class Sight //景點類信息，以後可以擴充
{
public:
Sight(string name, string sd) { sname = name; sight_detial = sd; }
string Sight_Name() { return sname; }
string Sight_detial() { return sight_detial; }
protected:
string sname; //景點名稱
string sight_detial; //景點備注
};
struct SI
{
string sname; //景點名稱
int index; //景點編碼
};
SI SightInfo[SIGHTS];
map<int, string>results; //距離與路徑的映射結構體，可以動態擴充
vector<Sight> sights; //VECTOR向量保存景點信息，目前的作用只是保存
//但是其強大的功能完全可以應付以後的功能擴充
int MinDistanct = 50000; //假定最小距離為一個很大的值
string Sight_Names = "楓林園蛟橋園青山園麥廬園 "; //目標字元串
string Best_Path; //保存最佳路徑的STRING字元串
int DISTANCE[4][4] = { //查找表，用於儲存接點之間距離的信息
0, 1500, 2500, 2400,
1500, 0, 800, 0,
2500, 800, 0, 200,
2400, 0, 200, 0
};
bool connect[4][4] = { //查找表，用於儲存接點之間連通的信息
0, 1, 1, 1,
1, 0, 1, 0,
1, 1, 0, 1,
1, 0, 1, 0
};
void InitSights()
{ //初始化景點的各類信息
SightInfo[0].index=0;
SightInfo[0].sname = "麥廬園";
SightInfo[1].index=1;
SightInfo[1].sname = "楓林園";
SightInfo[2].index=2;
SightInfo[2].sname = "蛟橋園";
SightInfo[3].index=3;
SightInfo[3].sname = "青山園";
Sight s1("楓林園",
"楓林園以計算機系的理工科學生為主，是江西財經大學的唯一一個計算機學院");
sights.push_back(s1);
Sight s2("蛟橋園",
"蛟橋園是江西財經大學的會計、貿易等財務教學為主的教學樓群，為本部");
sights.push_back(s2);
Sight s3("青山園",
"青山園是江西財經大學的會計、貿易等財務教學為主的學生的宿舍群");
sights.push_back(s3);
Sight s4("麥廬園",
"麥廬園是江西財經大學的外語、藝術等人文科學為主的學習園地");
sights.push_back(s4);
}
void Find_Ways(string start, string end, int DIST, string path, int depth)
{ //遞歸調用，逐層尋找可連通的路徑，並以該路徑繼續重復循環查找，根據分析可以
//知道，所有最優解即最短路徑所經過的接點數目必定小於N，於是採用廣度優先遍歷，
//設置count為循環深度，當count大於SIGHTS時退出循環
int count = 1;
int i,j;
int start1 = 0,end1 = 0;
int distanct = 0, storeDist = 0;
string temp, target, pathway, storePath; //臨時儲存體，用於恢復遞歸調用後會
//改變的數據，以便之後無差別使用
count += depth;
if(count > SIGHTS)
return;
distanct += DIST; //距離累加
if(path=="") //第一次時，pathway初始化為第一個接點名稱
{
pathway = start;
pathway += "=>";
}
if(path!="")
pathway = path;
storeDist = distanct; //填充臨時儲存值
storePath = pathway;
for(i = 0; i < SIGHTS; ++i) //通過遍歷，查找景點名稱對應的編號
{
if(start == SightInfo[i].sname)
start1 = SightInfo[i].index;
if(end == SightInfo[i].sname)
end1 = SightInfo[i].index;
}
for(i = 0; i < SIGHTS; i++) //演算法核心步驟
{
if(connect[start1][i] != 0)
{
if(i==end1) //如果找到了一條路徑，則保存之
{
distanct += DISTANCE[start1][end1];
for(j = 0; j < SIGHTS; ++j)
{
if(end1==SightInfo[j].index)
target = SightInfo[j].sname;
}
pathway += target;
results.insert(make_pair(distanct, pathway)); //保存結果路徑信息
distanct = storeDist; //恢復數據供下次使用
pathway = storePath;
}
else //分支路徑
{
for(j = 0; j < SIGHTS; ++j)
{
if(i==SightInfo[j].index)
temp = SightInfo[j].sname;
}
pathway += temp;
pathway += "=>";
distanct += DISTANCE[start1][i];
Find_Ways(temp, end, distanct, pathway, count); //以該連通的分支
//路徑繼續遞歸調用，查找子層路徑信息。
distanct = storeDist; //恢復數據
pathway = storePath;
}
}
}
}
void Find_Best_Way()
{ //該函數建立在上述函數執行完畢之後，在map映射結構中通過對比每條路徑的長度，來
//選擇最優解
map<int, string>::iterator itor = results.begin();
while(itor!=results.end()) //尋找最小值
{
// cout<<"distanct = "<<itor->first<<endl;
if(itor->first < MinDistanct)
MinDistanct = itor->first;
itor++;
}
itor = results.begin();
while(itor!=results.end()) //尋找最小值所對應的整個路徑字元串
{
if(itor->first == MinDistanct)
Best_Path = itor->second;
itor++;
}
}
int main(int argc, char *argv[])
{
int choice;
size_t t1=0,t2=0;
string source, termination;
InitSights();
do{
cout<<"////////////////////////////////////////////////////////\n"
<<"**** 請輸入您所需要的服務號碼: ********\n"
<<"**** 1.楓林園介紹 ********\n"
<<"**** 2.蛟橋園介紹 ********\n"
<<"**** 3.青山園介紹 ********\n"
<<"**** 4.麥廬園介紹 ********\n"
<<"**** 5.查詢地圖路徑 ********\n"
<<"**** 6.退出查詢系統 ********\n"
<<"////////////////////////////////////////////////////////\n"
<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<sights[0].Sight_Name()<<endl
<<sights[0].Sight_detial()<<endl;
break;
case 2:
cout<<sights[1].Sight_Name()<<endl
<<sights[1].Sight_detial()<<endl;
break;
case 3:
cout<<sights[2].Sight_Name()<<endl
<<sights[2].Sight_detial()<<endl;
break;
case 4:
cout<<sights[3].Sight_Name()<<endl
<<sights[3].Sight_detial()<<endl;
break;
case 5:
flag1:
cout<<"請輸入路徑的起點"<<endl;
cin>>source;
cout<<"請輸入路徑的終點"<<endl;
cin>>termination;
if((t1=Sight_Names.find(source,t1))==string::npos || (t2=Sight_Names.find(termination,t2))==string::npos)
{ //檢查輸入的數據是否含有非法字元
cerr<<"輸入的路徑結點不存在，請重新輸入:"<<endl;
goto flag1;
}
Find_Ways(source, termination, 0, "",0); //尋找所有可能解
Find_Best_Way(); //在所有可能解中找到最優解
cout<<"最佳路徑是："<< Best_Path <<endl
<<"最小路程為(米):"<< MinDistanct<<endl;
t1 = 0; //恢復字元串下標，以支持下次查詢
t2 = 0;
break;
case 6:
break;
default:
cerr<<"您的選擇超出了范圍，請重新輸入:"<<endl;
break;
}
}while(choice!=6);
system("pause");
return 0;
}