共性演算法
1. 求八數碼問題演算法，並說明下該演算法優缺點，要演算法，不是源代碼（可以沒有）。
八數碼問題
一.八數碼問題
八數碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始轉變成目標狀態的移動棋子步數最少的移動步驟。所謂問題的一個狀態就是棋子在棋盤上的一種擺法。棋子移動後，狀態就會發生改變。解八數碼問題實際上就是找出從初始狀態到達目標狀態所經過的一系列中間過渡狀態。
八數碼問題一般使用搜索法來解。搜索法有廣度優先搜索法、深度優先搜索法、A*演算法等。這里通過用不同方法解八數碼問題來比較一下不同搜索法的效果。
二.搜索演算法基類
1.八數碼問題的狀態表示
八數碼問題的一個狀態就是八個數字在棋盤上的一種放法。每個棋子用它上面所標的數字表示，並用0表示空格，這樣就可以將棋盤上棋子的一個狀態存儲在一個一維數組p[9]中，存儲的順序是從左上角開始，自左至右，從上到下。也可以用一個二維數組來存放。
2.結點
搜索演算法中，問題的狀態用結點描述。結點中除了描述狀態的數組p[9]外，還有一個父結點指針last，它記錄了當前結點的父結點編號，如果一個結點v是從結點u經狀態變化而產生的，則結點u就是結點v的父結點，結點v的last記錄的就是結點u的編號。在到達目標結點後，通過last 可以找出搜索的路徑。
3.類的結構
在C++中用類來表示結點，類將結點有關的數據操作封裝在一起。
不同的搜索演算法具有一定共性，也有各自的個性，因此這里將不同搜索演算法的共有的數據和功能封裝在一個基類中，再通過繼承方式實現不同的搜索演算法。
4.結點擴展規則
搜索就是按照一定規則擴展已知結點，直到找到目標結點或所有結點都不能擴展為止。
八數碼問題的結點擴展應當遵守棋子的移動規則。按照棋子移動的規則，每一次可以將一個與空格相鄰棋子移動到空格中，實際上可以看作是空格作相反移動。空格移動的方向可以是右、下、左、上，當然不能移出邊界。棋子的位置，也就是保存狀態的數組元素的下標。空格移動後，它的位置發生變化，在不移出界時，空格向右、下、左和上移動後，新位置是原位置分別加上1、3、-1、-3，如果將空格向右、下、左和上移動分別用0、1、2、3表示，並將-3、3、-1、1放在靜態數組d[4]中，空格位置用spac表示，那麼空格向方向i移動後，它的位置變為spac+d[i]。空格移動所產生的狀態變化，反映出來則是將數組p[]中，0的新位置處的數與0交換位置。
5.八數碼問題的基類
八數碼問題的基類及其成員函數的實現如下：
#define Num 9
class TEight
{
public:
TEight(){}
TEight(char *fname); //用文件數據構造節點
virtual void Search()=0; //搜索
protected:
int p[Num];
int last,spac;
static int q[Num],d[],total;
void Printf();
bool operator==(const TEight &T);
bool Extend(int i);
};
int TEight::q[Num];//儲存目標節點
int TEight::d[]={1,3,-1,-3};//方向
int TEight::total=0;//步數
TEight::TEight(char *fname)
{
ifstream fin;
fin.open(fname,ios::in);
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
int i;
for(i=0;i<Num;)//得到源節點
fin>>p[i++];
fin>>spac;
for(i=0;i<Num;)//得到目標節點
fin>>q[i++];
fin.close();
last=-1;
total=0;
}
void TEight::Printf()//把路徑列印到結果文件
{
ofstream fout;
fout.open("eight_result.txt",ios::ate|ios::app);
fout<<total++<<"t";
for(int i=0;i<Num;)
fout<<" "<<p[i++];
fout<<endl;
fout.close();
}
bool TEight::operator==(const TEight &T)//判斷兩個狀態是否相同
{
for(int i=0;i<Num;)
if(T.p[i]!=p[i++])
return 0;
return 1;
}
bool TEight::Extend(int i)//擴展
{
if(i==0 && spac%3==2 || i==1 && spac>5
|| i==2 && spac%3==0 || i==3 && spac<3)
return 0;
int temp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
return 1;
}
數據文件的結構：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。
三.線性表
搜索法在搜索過程中，需要使用一個隊列存儲搜索的中間結點，為了在找到目標結點後，能夠找到從初始結點到目標結點的路徑，需要保留所有搜索過的結點。另一方面，不同問題甚至同一問題的不同搜索方法中，需要存儲的結點數量相差很大，所以這里採用鏈式線性表作為存儲結構，同時，為適應不同問題，線性表設計成類模板形式。
template<class Type> class TList; //線性表前視定義
template<class Type> class TNode //線性表結點類模板
{
friend class TList<Type>;
public:
TNode(){}
TNode(const Type& dat);
private:
TNode<Type>* Next;
Type Data;
};
template<class Type> class TList
{
public:
TList(){Last=First=0;Length=0;} //構造函數
int Getlen()const{return Length;} //成員函數，返回線性表長度
int Append(const Type& T); //成員函數，從表尾加入結點
int Insert(const Type& T,int k); //成員函數，插入結點
Type GetData(int i); //成員函數，返回結點數據成員
void SetData(const Type& T,int k); //成員函數，設置結點數據成員
private:
TNode<Type> *First,*Last; //數據成員，線性表首、尾指針
int Length; //數據成員，線性表長度
};
template<class Type> int TList<Type>::Append(const Type& T)
{
Insert(T,Length);
return 1;
}
template<class Type> int TList<Type>::Insert(const Type& T,int k)
{
TNode<Type> *p=new TNode<Type>;
p->Data=T;
if(First)
{
if(k<=0)
{
p->Next=First;
First=p;
}
if(k>Length-1)
{
Last->Next=p;
Last=Last->Next;
Last->Next=0;
}
if(k>0 && k<Length)
{
k--;
TNode<Type> *q=First;
while(k-->0)
q=q->Next;
p->Next=q->Next;
q->Next=p;
}
}
else
{
First=Last=p;
First->Next=Last->Next=0;
}
Length++;
return 1;
}
template<class Type> Type TList<Type>::GetData(int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
return p->Data;
}
template<class Type> void TList<Type>::SetData(const Type& T,int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
p->Data=T;
}
線性表單獨以頭文件形式存放。
四.廣度優先搜索法
在搜索法中，廣度優先搜索法是尋找最短路經的首選。
1.廣度優先搜索演算法的基本步驟
1）建立一個隊列，將初始結點入隊，並設置隊列頭和尾指針
2）取出隊列頭（頭指針所指）的結點進行擴展，從它擴展出子結點，並將這些結點按擴展的順序加入隊列。
3）如果擴展出的新結點與隊列中的結點重復，則拋棄新結點，跳至第六步。
4）如果擴展出的新結點與隊列中的結點不重復，則記錄其父結點，並將它加入隊列，更新隊列尾指針。
5）如果擴展出的結點是目標結點，則輸出路徑，程序結束。否則繼續下一步。
6）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
2.搜索路徑的輸出
搜索到目標結點後，需要輸出搜索的路徑。每個結點有一個數據域last，它記錄了結點的父結點，因此輸出搜索路徑時，就是從目標結點Q出發，根據last找到它的父結點，再根據這個結點的last找到它的父結點，....,最後找到初始結點。搜索的路徑就是從初始結點循相反方向到達目標結點的路徑。
3.廣度優先搜索法TBFS類的結構
廣度優先搜索法TBFS類是作為TEight類的一個子類。其類的結構和成員函數的實現如下：
class TBFS:public TEight
{
public:
TBFS(){}
TBFS(char *fname):TEight(fname){}
virtual void Search();
private:
void Printl(TList<TBFS> &L);
int Repeat(TList<TBFS> &L);
int Find();
};
void TBFS::Printl(TList<TBFS> &L)
{
TBFS T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TBFS::Repeat(TList<TBFS> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}
int TBFS::Find()
{
for(int i=0;i<Num;)
if(p[i]!=q[i++])
return 0;
return 1;
}
void TBFS::Search()
{
TBFS T=*this;
TList<TBFS> L;
L.Append(T);
int head=0,tail=0;
while(head<=tail)
{
for(int i=0;i<4;i++)
{
T=L.GetData(head);
if(T.Extend(i) && T.Repeat(L)>tail)
{
T.last=head;
L.Append(T);
tail++;
}
if(T.Find())
{
T.Printl(L);
T.Printf();
return;
}
}
head++;
}
}
4.廣度優先搜索法的缺點
廣度優先搜索法在有解的情形總能保證搜索到最短路經，也就是移動最少步數的路徑。但廣度優先搜索法的最大問題在於搜索的結點數量太多，因為在廣度優先搜索法中，每一個可能擴展出的結點都是搜索的對象。隨著結點在搜索樹上的深度增大，搜索的結點數會很快增長，並以指數形式擴張，從而所需的存儲空間和搜索花費的時間也會成倍增長。
五、A*演算法
1.啟發式搜索
廣度優先搜索和雙向廣度優先搜索都屬於盲目搜索，這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關的狀態結點後才碰到解答，甚至更本不能碰到解答。
搜索是一種試探性的查尋過程，為了減少搜索的盲目性引，增加試探的准確性，就要採用啟發式搜索了。所謂啟發式搜索就是在搜索中要對每一個搜索的位置進行評估，從中選擇最好、可能容易到達目標的位置，再從這個位置向前進行搜索，這樣就可以在搜索中省略大量無關的結點，提高了效率。
2.A*演算法
A*演算法是一種常用的啟發式搜索演算法。
在A*演算法中，一個結點位置的好壞用估價函數來對它進行評估。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以實際上使用的是下面的估價函數：
f(n) = g(n) + h(n)
其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足兩個條件：（1）g(n)>=g'(n)（大多數情況下都是滿足的，可以不用考慮），且f必須保持單調遞增。（2）h必須小於等於實際的從當前節點到達目標節點的最小耗費h(n)<=h'(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。
3.A*演算法的步驟
A*演算法基本上與廣度優先演算法相同，但是在擴展出一個結點後，要計算它的估價函數，並根據估價函數對待擴展的結點排序，從而保證每次擴展的結點都是估價函數最小的結點。
A*演算法的步驟如下：
1）建立一個隊列，計算初始結點的估價函數f，並將初始結點入隊，設置隊列頭和尾指針。
2）取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展。
3）檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復（位於隊列頭指針之前），則將它拋棄；若新結點與待擴展的結點重復（位於隊列頭指針之後），則比較兩個結點的估價函數中g的大小，保留較小g值的結點。跳至第五步。
4）如果擴展出的新結點與隊列中的結點不重復，則按照它的估價函數f大小將它插入隊列中的頭結點後待擴展結點的適當位置，使它們按從小到大的順序排列，最後更新隊列尾指針。
5）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
4.八數碼問題的A*演算法的估價函數
估價函數中，主要是計算h，對於不同的問題，h有不同的含義。那麼在八數碼問題中，h的含意是各什麼？八數碼問題的一個狀態實際上是數字0~8的一個排列，用一個數組p[9]來存儲它，數組中每個元素的下標，就是該數在排列中的位置。例如，在一個狀態中，p[3]=7，則數字7的位置是3。如果目標狀態數字3的位置是8，那麼數字7對目標狀態的偏移距離就是3，因為它要移動3步才可以回到目標狀態的位置。
八數碼問題中，每個數字可以有9個不同的位置，因此，在任意狀態中的每個數字和目標狀態中同一數字的相對距離就有9*9種，可以先將這些相對距離算出來，用一個矩陣存儲，這樣只要知道兩個狀態中同一個數字的位置，就可查出它們的相對距離，也就是該數字的偏移距離：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一個狀態中，數字8的位置是3，在另一狀態中位置是7，那麼從矩陣的3行7列可找到2，它就是8在兩個狀態中的偏移距離。
估價函數中的h就是全體數字偏移距離之和。顯然，要計算兩個不同狀態中同一數字的偏移距離，需要知道該數字在每個狀態中的位置，這就要對數組p[9]進行掃描。由於狀態發生變化，個數字的位置也要變化，所以每次計算h都沿線掃描數組，以確定每個數字在數組中的位置。為了簡化計算，這里用一個數組存儲狀態中各個數字的位置，並讓它在狀態改變時隨著變化，這樣就不必在每次計算h時，再去掃描狀態數組。
例如，某個狀態中，數字5的位置是8，如果用數組r[9]存儲位置，那麼就有r[5]=8。
現在用數組r[9]存儲當前狀態的數字位置，而用s[9]存儲目標狀態的數字位置，那麼當前狀態數字i對目標狀態的偏移距離就是矩陣中r[i]行s[i]列對應的值。
5.A*演算法的類結構
A*演算法的類聲明如下：
class TAstar:public TEight
{
public:
TAstar(){} //構造函數
TAstar(char *fname); //帶參數構造函數
virtual void Search(); //A*搜索法
private:
int f,g,h; //估價函數
int r[Num]; //存儲狀態中各個數字位置的輔助數組
static int s[Num]; //存儲目標狀態中各個數字位置的輔助數組
static int e[]; //存儲各個數字相對距離的輔助數組
void Printl(TList<TAstar> L); //成員函數，輸出搜索路徑
int Expend(int i); //成員函數，A*演算法的狀態擴展函數
int Calcuf(); //成員函數，計算估價函數
void Sort(TList<TAstar>& L,int k); //成員函數，將新擴展結點按f從小到大順序插入待擴展結點隊列
int Repeat(TList<TAstar> &L); //成員函數，檢查結點是否重復
};
int TAstar::s[Num],TAstar::e[Num*Num];
TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;i<Num;)
{
r[p[i]]=i; //存儲初始狀態個個數字的位置
s[q[i]]=i++; //存儲目標狀態個個數字的位置
}
ifstream fin;
fin.open("eight_dis.txt",ios::in); //打開數據文件
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
for(int i=0;i<Num*Num;i++) //讀入各個數字相對距離值
fin>>e[i];
fin.close();
f=g=h=0; //估價函數初始值
}
void TAstar::Printl(TList<TAstar> L)
{
TAstar T=*this;
if(T.last==-1) return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TAstar::Expend(int i)
{
if(Extend(i)) //結點可擴展
{
int temp=r[p[r[0]]]; //改變狀態後數字位置變化，存儲改變後的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}
int TAstar::Calcuf()
{
h=0;
for(int i=0;i<Num;i++) //計算估價函數的 h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}
void TAstar::Sort(TList<TAstar>& L,int k)
{
int n=L.Getlen();
int i;
for(i=k+1;i<n;i++)
{
TAstar T=L.GetData(i);
if(this->f<=T.f)
break;
}
L.Insert(*this,i);
}
int TAstar::Repeat(TList<TAstar> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}
void TAstar::Search()
{
TAstar T=*this; //初始結點
T.f=T.Calcuf(); //初始結點的估價函數
TList<TAstar> L; //建立隊列
L.Append(T); //初始結點入隊
int head=0,tail=0; //隊列頭和尾指針
while(head<=tail) //隊列不空則循環
{
for(int i=0;i<4;i++) //空格可能移動方向
{
T=L.GetData(head); //去隊列頭結點
if(T.h==0) //是目標結點
{
T.Printl(L);//輸出搜索路徑
T.Printf(); //輸出目標狀態
return; //結束
}
if(T.Expend(i)) //若結點可擴展
{
int k=T.Repeat(L); //返回與已擴展結點重復的序號
if(k<head) //如果是不能擴展的結點
continue; //丟棄
T.last=head; //不是不能擴展的結點，記錄父結點
T.f=T.Calcuf(); //計算f
if(k<=tail) //新結點與可擴展結點重復
{
TAstar Temp=L.GetData(k);
if(Temp.g>T.g) //比較兩結點g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新結點插入可擴展結點隊列
tail++; //隊列尾指針後移
}
}
head++; //一個結點不能再擴展，隊列頭指針指向下一結點
}
}
六、測試程序
A*演算法的測試：
int main()
{
TAstar aStar("eight.txt");
aStar.Search();
system("pauze");
return 0;
}
eight.txt文件中的數據（初始態和目標態）：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。
8 3 5 1 2 7 4 6 0
8
1 2 3 4 5 6 7 8 0
eight_dis.txt中的數據（估計函數使用）
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0
eight_Result.txt中的結果（運行後得到的結果）
七、演算法運行結果
1.BFS演算法只能適用於到達目標結點步數較少的情況，如果步數超過15步，運行時間太長，實際上不再起作用。
2.對於隨機生成的同一個可解狀態，BFS演算法最慢，DBFS演算法較慢，A*演算法較快。但在15步以內，DBFS演算法與A*演算法相差時間不大，超過15步後，隨步數增加，A*演算法的優勢就逐漸明顯，A*演算法要比DBFS演算法快5倍以上，並隨步數增大而增大。到25步以上，DBFS同樣因運行時間過長而失去價值。
3.一般來說，解答的移動步數每增加1，程序運行時間就要增加5倍以上。由於八數碼問題本身的特點，需要檢查的節點隨步數增大呈指數形式增加，即使用A*演算法，也難解決移動步數更多的問題。
八、問題可解性
八數碼問題的一個狀態實際上是0~9的一個排列，對於任意給定的初始狀態和目標，不一定有解，也就是說從初始狀態不一定能到達目標狀態。因為排列有奇排列和偶排列兩類，從奇排列不能轉化成偶排列或相反。
如果一個數字0~8的隨機排列871526340，用F(X)表示數字X前面比它小的數的個數，全部數字的F(X)之和為Y=∑(F(X))，如果Y為奇數則稱原數字的排列是奇排列，如果Y為偶數則稱原數字的排列是偶排列。
例如871526340這個排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶數，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇數，所以他奇排列。
因此，可以在運行程序前檢查初始狀態和目標狀態的窘是否相同，相同則問題可解，應當能搜索到路徑。否則無解。
PS:整理自網路
2. 模型與演算法之間是什麼關系
模型是一類問題的解題步驟，亦即一類問題的演算法。如果問題的演算法不具有一般性，就沒有必要為演算法建立模型，因為此時個體和整體的對立不明顯，模型的抽象性質也體現不出來。
數學模型還沒有一個統一的准確的定義，因為站在不同的角度可以有不同的定義。不過我們可以給出如下定義。"數學模型是關於部分現實世界和為一種特殊目的而作的一個抽象的、簡化的結構。"具體來說，數學模型就是為了某種目的，用字母、數字及其它數學符號建立起來的等式或不等式以及圖表、圖象、框圖等描述客觀事物的特徵及其內在聯系的數學結構表達式。
演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
3. 關於LocateElem演算法
1、LocateElem(L,e,compare())函數：
初始條件：線性表存在，compare()是數據元素判定函數；
操作結果：返回第一個與e滿足關系compare()的數據元素的位序。若不存在，返回0.
由定義的結構體知：
typedef struct
{
char Name[100]; //學生姓名
char Number[100]; //學生的學號
} StudentRacord;
如何來比較每位學生的信息呢？及如何創建compare()函數？根據一般的學號特點，學號的前兩位一般表示的是學生的入學年份。由此我們可以構造一個比較兩位同學是否同一年入學的函數。部分代碼如下：
Status compare(StudentRacord Student_A, StudentRacord Student_B)
{
//學號前兩位數表示該生的入學年份
///判斷該生是否和比較的學生是否是同一年入學
if(Student_A.Number[0]==Student_B.Number[0]&&
Student_A.Number[1]==Student_B.Number[1])
{
return TRUE;
}
else
{
return FALSE;
}
}
Status LocateElem(SequentialList Record, StudentRacord Student,
int (*compare)(StudentRacord , StudentRacord)) // 演算法2.6
{
// 在順序線性表Record中查找第1個值與Student滿足compare()的元素的位序。
// 若找到，則返回其在Record中的位序，否則返回0。
int i,j;
StudentRacord *p;
i = 1; // i的初值為第1個元素的位序
p = Record.elem; // p的初值為第1個元素的存儲位置
j = (*compare)(*p++, Student);
while (i <= Record.length&&j==0)
{
++i;
j = (*compare)(*p++, Student);
}
if (i <= Record.length)
{
return i;
}
else
{
return 0;
}
} // LocateElem
2、ListTraverse(L,visit())函數：
初始條件：線性表已存在.
操作結果：依次對線性表中的每個數據元素調用函數visit().一旦visit()失敗，則操作失敗。
注意操作失敗的字眼，這就意味著線性表中的每個數據元素都存在一個共性，一旦缺乏這個共性，就代表學生信息內容有誤，提示線性表構建失敗。
為此我們認定每個學生的學號都是13位數，如果一個學生的學號不是13位即意味著操作失敗。
部分代碼：
bool visit(StudentRacord STUDENT)
{
///規定學號為13位，若非13位；則該同學的學號輸入有誤，操作失敗
if(strlen(STUDENT.Number)==13)
{
return true;
}
else
{
return false;
}
}
Status ListTraverse(SequentialList Record,bool (*visit)(StudentRacord))
{
StudentRacord *p;
p = Record.elem;
int i=1,j = (*visit)(*p++);
while (i <= Record.length&&j!=0)
{
++i;
j = (*visit)(*p++);
}
if (i <= Record.length)
{
printf("The number of student%d is Error!/n",i);
return ERROR;
}
else
{
printf("The number of students is OK!/n");
return 0;
}
4. 簡評三個基於VRF的共識演算法
上交所技術公司 朱立
Algorand、Dfinity和Ouroboros Praos三個共識演算法（Dfinity雖然是項目名，這里用來稱呼其共識演算法也應無不妥）近期較受關注，而且都是基於VRF(Verifiable Random Function) 設計，可以對照學習。Algorand的版本很多，以下單指 1607.01341v9 ，暫稱其為Algorand'（筆者手中另有Algorand的 最新版本 ，其中已對下文提及的幾處問題完成了修正，可與本文參看）。
一、VRF的共性
VRF的意義很好理解——用以完成出塊人（群）的隨機選擇。為此，VRF的返回值應盡力難以預測。先看Algorand'和Dfinity的套路是怎麼做的：大體上是先將前一個隨機數（最初的隨機數卻是協議給定的）和某種代表高度、輪次的變數進行組合，用某種私鑰對之進行簽名（或者是先簽名再組合），最後哈希一下得出最新的隨機數。這樣產生的隨機數旁人很容易驗證其合乎演算法，"V"就這樣得到了；而哈希返回值又是隨機分布的，「R」也因此得到保證。在此過程中，為降低操縱結果的可能性，有兩個注意事項： A) 簽名演算法應當具有唯一性，也就是用同一把私鑰對同樣的信息進行簽名，只有一個合法簽名可以通過驗證——普通的非對稱加解密演算法一般不具備這個屬性，如SM2。如果用的簽名演算法沒有這種uniqueness屬性，那在生成新隨機數的時候就存在通過反復多次嘗試簽名以挑出最有利者的餘地，會降低安全性。 B) 避免在生成新隨機數時將當前塊的數據作為隨機性來源之一，比如引用本塊交易列表的merkle root值等等，因為這樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產生最有利的新隨機數的餘地。在設計和檢視新的共識演算法時，以上兩個注意事項是要特別留意的。
考察一下VRF的返回結果應該如何運用。目前所見用法中，VRF的返回結果可以用來公開完成節點或節點群體的選擇，也可以私密地完成選擇。以Dfinity為例，它是利用mod操作來唯一、公開地確定一個Group。Algorand'、Ouroboros Praos是私密選擇的範例，大致套路是對VRF的最新返回值，配上輪次等變數後用私鑰進行簽名並哈希，如果哈希值小於某個閾值，節點就可以私密地知道自己被選中。這種方法很可能在網路節點數較多時的表現會更穩定，否則幸運兒個數上下波動會較大，進而影響協議表現，包括空塊和分叉。
二、簡評強同步假設版本的Algorand'
私密選擇提供了較強的抗擊定點攻擊的能力，但由於幸運兒的總數對於任何一個幸運兒都是不能預知的，也因此給後續共識演算法的設計和區塊鏈的優化帶來了困難。Algorand『採用了很強的同步網路假設（同步網路假設下的共識演算法當然容易做一些），要求預先知道網路消息傳播時間的上限：在固定時間內完成對固定比例的用戶的網路傳播。比如要知道，1KB消息，在1秒鍾內完成全網95%的傳播，而1MB消息需要1.5分鍾完成全網95%的傳播。但這個傳輸上限應該如何選擇？ 通過一段時間的統計結果再乘以一個系數這種經驗統計？只能說「感覺上可以」，但如果要嚴謹和安全，Algorand『演算法應該補充證明即使在遭遇DDOS或互聯網擁堵的情況下消息傳播嚴重超限後演算法仍然能夠保證安全——然而這個證明是缺失的。作為對照，Ouroboros Praos公開承認之前在同步網路假設下設計的Ouroboros協議在非同步網路條件下會出錯，所以才又做了Ouroboros Praos；新版本的Algorand承認在弱同步網路時會在不同的塊上達成共識（後續網路恢復強同步時分叉可以得到解決）雲雲，這些都可資參考。
即使我們暫且認可Algorand'演算法可以通過設定一個很大的傳播時間上限來回應上述問題，但隨之而來的是此時可以看出此演算法缺乏一個非常好的特性：Responsiveness。這個特性指的是：若一個協議被設計為在一個較大的傳播時間上限DELTA下工作，但若實際傳播時間是較小的delta，則協議的實際推進步調將只和delta有關，這種協議被稱為Responsive的。具有Responsive特性的共識演算法再配以同步網路假設會非常理想——出於安全，上限可以設置很大，然而協議執行速度只和當時網路條件有關。Algorand'並不具有這種特性。平均而言，Algorand'完成共識所需的消息傳送次數是11輪，每輪如果要確保安全，完成共識的時間就會很長，單個分區的吞吐量就不會太高。當然，架構設計涉及很多取捨，最終評價一個演算法好還是不好還是要回到初心——准備拿來實現的目標是什麼。上述分析只是嘗試客觀地指出Algorand'演算法的幾個少為人知的固有特徵，供讀者自行評估。
三、簡評Dfinity的可擴展性問題
私密選擇並且立即上任的做法，也給系統分片帶來了極大挑戰。Dfinity是明確要做分片(Sharding)的，所以必須直面挑戰。可擴展性問題非常復雜，完整解決這個問題需要通盤考慮網路、存儲、計算三方面的可擴展性——時下大多數區塊鏈3.0項目只注意到計算的分片和可擴展性，忽略了其餘二者，從而不可能真正實現理想的擴展。由於公鏈節點網路帶寬的制約，計算合約所需的數據通常很難迅速地從一個節點拷貝到另一節點，所以就算用VRF實現了飄忽來去的出塊節點選擇，存儲節點是沒法同樣飄逸如風的。明顯的選擇有那麼幾個：全部節點存儲全部數據，不同節點靜態地分配用來存儲不同分區。前者的可擴展性很差，對於後者而言，如果出塊節點漂浮不定且出塊節點還需要完成合約運算，就意味著基於P2P網路來回遠程訪問存儲，性能多半急劇下降；動態決定的出塊節點只完成排序共識，計算能力和存儲捆綁，通過靜態分區提供可擴展性，可能是合理的應對。然而，最可恨的就是「然而」二字——即使如此，系統還存在一處對存儲和網路構成壓力的所在：最終用戶提交的待打包交易。普通公鏈（先不考慮EOS那種）的帶寬有限，如果用戶提交的待打包交易必須粗放型地全網泛濫傳播，那現有網路帶寬可以提供多少TPS？如果出塊節點是靜態分區或者至少提前一段時間公開知曉，事情尚有迴旋餘地；如果出塊節點是如此飄忽不定，而且直到最後一刻也只有這些節點自己知道，那無論是用戶還是出塊節點候選人看起來最直接的應對之道就是全網泛濫傳播全部待打包交易、保存全部待打包交易，這樣帶寬和存儲仍然成為系統瓶頸。
所以這里碰到的，本質上還是安全、可擴展性、去中心化的不可能三角。
四、簡評Ouroboros Praos
BM懟 Ouroboros的文字已經流傳廣泛。BM的話當然有些明顯是不對的，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS，但其關於Pareto分布的評論則值得玩味。如果我們仔細瀏覽後出的Ouroboros Praos，可以發現協議的安全假設和安全證明完全沒有考慮經濟博弈因素，因此洋洋灑灑的證明很可能會不得要領而錯過真正需要防護的方向——畢竟一直以來POS/DPOS這些協議的血管裡面流淌的就是基於經濟博弈和人性進行設計的血液。最明顯的例子是在forward secure signature的實現方法上，協議目前的設計是要求每個好的節點自覺主動地安全刪除用過的私鑰，而完全沒有考慮近乎零的私鑰保存成本如何面對bribe attack的誘惑，然而這卻是值得考慮的。除了形式化證明之外，Ouroboros Praos本身並沒有太多值得關注的協議特徵，總體上就是用VRF抽簽結合POS演算法並針對某些安全假設進行了形式化證明，其做事的態度是非常值得贊賞的。
五、總結
這幾個演算法本身頗有創意，也很值得學習。與此同時，在看過以太坊CASPER目前披露的分區技術後，筆者的體會是：區塊鏈3.0的競爭才剛剛開始，從以太坊團隊的技術路線看，他們的技術考量和選擇要比很多宣稱要超越以太坊的團隊來得深刻和全面。如果當真要超越以太坊，還是應該先從理解以太坊開始。
順便感謝趣鏈邱煒偉博士對本文的貢獻！
5. 優化演算法筆記（二）優化演算法的分類
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
在分類之前，我們先列舉一下常見的優化演算法（不然我們拿什麼分類呢？）。
1遺傳演算法Genetic algorithm
2粒子群優化演算法Particle Swarm Optimization
3差分進化演算法Differential Evolution
4人工蜂群演算法Artificial Bee Colony
5蟻群演算法Ant Colony Optimization
6人工魚群演算法Artificial Fish Swarm Algorithm
7杜鵑搜索演算法Cuckoo Search
8螢火蟲演算法Firefly Algorithm
9灰狼演算法Grey Wolf Optimizer
10鯨魚演算法Whale Optimization Algorithm
11群搜索演算法Group search optimizer
12混合蛙跳演算法Shuffled Frog Leaping Algorithm
13煙花演算法fireworks algorithm
14菌群優化演算法Bacterial Foraging Optimization
以上優化演算法是我所接觸過的演算法，沒接觸過的演算法不能隨便下結論，知之為知之，不知為不知。其實到目前為止優化演算法可能已經有幾百種了，我們不可能也不需要全面的了解所有的演算法，而且優化演算法之間也有較大的共性，深入研究幾個之後再看其他優化演算法上手速度會灰常的快。
優化演算法從提出到現在不過50-60年（遺傳演算法1975年提出），雖種類繁多但大多較為相似，不過這也很正常，比較香蕉和人的基因相似度也有50%-60%。當然演算法之間的相似度要比香蕉和人的相似度更大，畢竟人家都是優化演算法，有著相同的目標，只是實現方式不同。就像條條大路通羅馬，我們可以走去，可以坐汽車去，可以坐火車去，也可以坐飛機去，不管使用何種方式，我們都在去往羅馬的路上，也不會說坐飛機去要比走去更好，交通工具只是一個工具，最終的方案還是要看我們的選擇。
上面列舉了一些常見的演算法，即使你一個都沒見過也沒關系，後面會對它們進行詳細的介紹，但是對後面的分類可能會有些許影響，不過問題不大，就先當總結看了。
再對優化演算法分類之前，先介紹一下演算法的模型，在筆記（一）中繪制了優化演算法的流程，不過那是個較為簡單的模型，此處的模型會更加復雜。上面說了優化演算法有較大的相似性，這些相似性主要體現在演算法的運行流程中。
優化演算法的求解過程可以看做是一個群體的生存過程。
有一群原始人，他們要在野外中尋找食物，一個原始人是這個群體中的最小單元，他們的最終目標是尋找這個環境中最容易獲取食物的位置，即最易存活下來的位置。每個原始人都去獨自尋找食物，他們每個人每天獲取食物的策略只有採集果實、製作陷阱或者守株待兔，即在一天之中他們不會改變他們的位置。在下一天他們會根據自己的策略變更自己的位置。到了某一天他們又聚在了一起，選擇了他們到過的最容易獲取食物的位置定居。
一群原始人=優化演算法中的種群、群體；
一個原始人=優化演算法中的個體；
一個原始人的位置=優化演算法中個體的位置、基因等屬性；
原始人變更位置=優化演算法中總群的更新操作；
該位置獲取食物的難易程度=優化演算法中的適應度函數；
一天=優化演算法中的一個迭代；
這群原始人最終的定居位置=優化演算法所得的解。
優化演算法的流程圖如下：
對優化演算法分類得有個標准，按照不同的標准分類也會得到不一樣的結果。首先說一下我所使用的分類標准（動態更新，有了新的感悟再加）：
按由來分類比較好理解，就是該演算法受何種現象啟發而發明，本質是對現象分類。
可以看出演算法根據由來可以大致分為有人類的理論創造而來，向生物學習而來，受物理現象啟發。其中向生物學習而來的演算法最多，其他類別由於舉例有偏差，不是很准確，而且物理現象也經過人類總結，有些與人類現象相交叉，但仍將其獨立出來。
類別分好了，那麼為什麼要這么分類呢？
當然是因為要湊字數啦，啊呸，當然是為了更好的理解學習這些演算法的原理及特點。
向動物生存學習而來的演算法一定是一種行之有效的方法，能夠保證演算法的效率和准確性，因為，如果使用該策略的動物無法存活到我們可以對其進行研究，我們也無法得知其生存策略。（而這也是一種倖存者偏差，我們只能看到行之有效的策略，但並不是我們沒看到的策略都是垃圾，畢竟也發生過小行星撞地球這種小概率毀滅性事件。講個冷笑話開cou心一shu下:一隻小恐龍對他的小夥伴說，好開心，我最喜歡的那顆星星越來越亮了（完）。）但是由於生物的局限性，人們所創造出的演算法也會有局限性：我們所熟知的生物都生存在三維空間，在這些環境中，影響生物生存的條件比較有限，反應到演算法中就是這些演算法在解決較低維度的問題時效果很好，當遇到超高維（維度>500）問題時，結果可能不容樂觀，沒做過實驗，我也不敢亂說。
按更新過程分類相對復雜一點，主要是根據優化演算法流程中更新位置操作的方式來進行分類。更新位置的操作按我的理解可大致分為兩類：1.跟隨最優解；2.不跟隨最優解。
還是上面原始人的例子，每天他有一次去往其他位置狩獵的機會，他們採用何種方式來決定今天自己應該去哪裡呢？
如果他們的策略是「跟隨最優解」，那麼他們選取位置的方式就是按一定的策略向群體已知的最佳狩獵位置（歷史最佳）或者是當前群體中的最佳狩獵位置（今天最佳）靠近，至於是直線跑過去還是蛇皮走位繞過去，這個要看他們群體的策略。當然，他們的目的不是在最佳狩獵位置集合，他們的目的是在過去的途中看是否能發現更加好的狩獵位置，去往已經到過的狩獵地點再次狩獵是沒有意義的，因為每個位置獲取食物的難易程度是固定的。有了目標，大家都會朝著目標前進，總有一日，大家會在謀個位置附近相聚，相聚雖好但不利於後續的覓食容易陷入局部最優。
什麼是局部最優呢？假設在當前環境中有一「桃花源」，擁有上帝視角的我們知道這個地方就是最適合原始人們生存的，但是此地入口隱蔽「山有小口，彷彿若有光」、「初極狹，才通人。」，是一個難以發現的地方。如果沒有任何一個原始人到達了這里，大家向著已知的最優位置靠近時，也難以發現這個「桃源之地」，而當大家越聚越攏之後，「桃源」被發現的可能性越來越低。雖然原始人們得到了他們的解，但這並不是我們所求的「桃源」，他們聚集之後失去了尋求「桃源」的可能，這群原始人便陷入了局部最優。
如果他們的策略是「不跟隨最優解」，那麼他們的策略是什麼呢？我也不知道，這個應該他們自己決定。畢竟「是什麼」比「不是什麼」的范圍要小的多。總之不跟隨最優解時，演算法會有自己特定的步驟來更新個體的位置，有可能是隨機在自己附近找，也有可能是隨機向別人學習。不跟隨最優解時，原始人們應該不會快速聚集到某一處，這樣一來他們的選擇更具多樣性。
按照更新過程對上面的演算法分類結果如下
可以看出上面不跟隨最優解的演算法只有遺傳演算法和差分進化演算法，他們的更新策略是與進化和基因的重組有關。因此這些不跟隨最優解的演算法，他們大多依據進化理論更新位置（基因）我把他們叫做進化演算法，而那些跟隨群體最優解的演算法，他們則大多依賴群體的配合協作，我把這些演算法叫做群智能演算法。
目前我只總結了這兩種，分類方法，如果你有更加優秀的分類方法，我們可以交流一下：
目錄
上一篇 優化演算法筆記（一）優化演算法的介紹
下一篇 優化演算法筆記（三）粒子群演算法（1）
6. 如何理解「關鍵共性（核心）技術」
從寫碩士論文的那年起，我就開始接觸到類似「關鍵共性（核心）技術」的概念，至今已快30年了。現在看來，似乎每一個科技人員、科研單位，都把研製「關鍵共性（核心）技術」作為自己的使命；正如企業往往把「世界一流高精尖」技術作為自己的定位一樣。
大家為什麼喜歡這樣的定位呢？在我看來，其實是想做「工作量小而價值大」的事情。當團隊比較小的時候很難做成大事，要走這條路才能體現價值。如果一件事的「工作量小而價值大」，一定是難度很大，同時使用的頻度還會很高。
在人們心目中，「關鍵共性（核心）技術」往事是一些關鍵參數或工藝、基礎原材料、特殊演算法等。但有多少人實現了當初的夢想了呢？回想起來，似乎少之又少。
在我看來，是因為這樣的工作本身就少、而且不易被注意到。事實上，工業界的難點往往是因為復雜；復雜就會面臨眾多的細節和工作量，就難以做到「小而美」。當然，工業上也有很多巧妙的做法，但這些做法是在做具體工作的時候才能遇到、才能想到的。而且，這些「小而美」的做法一旦能想到，往往並不困難、也很難體現理論水平。
真正好的項目總結成功經驗時，往往會提到一種簡單的思想。如寶鋼的「數據不落地」、波音的「統一數據源」、UNIX的「簡單就是美」。思想的描述很簡單，但作用卻很大。可惜的是，這些思想很難用學術的標准進行衡量。
在我看來，「關鍵共性（核心）技術」主要應該是解決復雜問題的，其重要性在於這類復雜問題有共性。把「復雜問題的共性問題」提煉出來，用統一的方法去解決，一定是更加復雜、更加困難的問題。什麼技術或問題符合這樣的要求呢？我想，平台技術和技術標准就是這樣的。要做好這些東西，真的需要超強的智慧和能力。
來源：搜狐
作者：蟈蟈創新雜談
7. 求類似計算器的演算法- - 比如 (2+7)*2 或者 (4-1)/3 解這些字元串 然後算出結果
這是我以前做的額，運行在tc上運行可以，因為atoi()(字元轉數值)是tc的庫函數，在c++6.0上會報錯，其實很簡單，自己都可以編一個。剛開始運行沒有提示，忘記了，輸入表達式回車就行了。基本思想是將中綴表達式利用棧轉成後綴表達式，再求值。
#include<stdio.h>
#define max 100
typedef long datatype;
typedef char chartype;
typedef struct
{
datatype data[max];
int top;
}numstack;/*對象棧用於存儲運算對象*/
typedef struct
{
chartype data[max];
int top,y[max];/*y中存儲對應運算符的優先順序*/
}stack;/*運算符棧用於存儲運算符*/
int fenli(numstack *S,char string[max],int i)
/*將運算對象從表達式中取出轉換為數值並存儲在對象棧中*/
{
int j=0;
char st[100];/*st用於暫時存儲字元類型的運算對象*/
do
{
st[j]=string[i];i++;j++;
}while(string[i]>='0'&&string[i]<='9');/*將運算對象從表達式中取出存儲在st中*/
st[j]='\0';
S->top++;
S->data[S->top]=atoi(st);/*atoi的作用是將字元串轉換為對應的數值，將轉換後的數值存儲在對象棧中*/
j=0;
return(i);/*將當前字元的位置返回*/
}
int pipei(char string[max])
/*驗證括弧是否匹配*/
{
stack *S;
int i=0;
S->top=0;/*初始化運算符棧*/
while(string[i]!='\0')
{
if(string[i]=='(')/*遇到'('將'('入棧*/
{
S->top++;
S->data[S->top]=string[i];
}
if(string[i]==')')/*遇到')',判斷棧頂是否'(',如果是則將棧頂出棧，否則括弧不匹配返回0*/
if(S->data[S->top]=='(')
S->top--;
else return(0);
i++;
}
if(S->top>0) return(0);/*判斷運算符棧是否為空，不為空則括弧不匹配返回0，為空則括弧匹配返回1*/
else return(1);
}
void yunsuan(char string[max])
{
numstack *S;
int i=0;
S->top=0;/*初始化對象棧*/
while(string[i]!='\0')/*如果是結束符，結束循環*/
{
if(string[i]>='0'&&string[i]<='9')/*如果當前字元是運算對象，調用fenli函數將運算對象分離出來，並轉換為對應數值*/
i=fenli(S,string,i);
else
{/*如果是運算符，則將對象棧中棧頂倆個運算對象做對應的運算，將結果壓入對象棧*/
switch(string[i])
{
case ' ':{break;}
case '+':{S->data[S->top-1]+=S->data[S->top];S->top--;break;}
case '-':{S->data[S->top-1]-=S->data[S->top];S->top--;break;}
case '*':{S->data[S->top-1]*=S->data[S->top];S->top--;break;}
case '/':{S->data[S->top-1]/=S->data[S->top];S->top--;break;}
}
i++;/*掃描下一字元*/
}
}
printf("表達式運算結果為: %ld \n",S->data[S->top]);
}
int zhuanghuan(char s[max],char string[max])
/*將中綴表達式轉換為後綴表達式*/
{
stack *S;
int i=0,j=0;
S->top=-1;
S->y[0]=0;/*初始化運算符棧*/
while(s[i]!='\0')/*遇到結束符結束循環*/
{
if(s[i]>='0'&&s[i]<='9')/*遇到運算對象*/
{
string[j]=s[i];/*將運算對象存入轉換後的字元串中*/
j++;
}
else switch(s[i])
{
case '(':{/*遇到'(',直接入運算符棧*/
S->top++;
S->data[S->top]='(';
S->y[S->top]=0;/*'('在括弧內運算優先順序最低，在括弧外最高*/
break;
}
case ')':/*遇到')'，將運算符棧的運算符出棧，直到遇到'('為止，將'('直接出棧*/
{
while(S->data[S->top]!='(')
{
string[j]=S->data[S->top];
S->top--;j++;
}
S->top--;break;
}
case '+':
case '-':{
string[j]=' ';/*將運算對像用間隔開*/
if(S->y[S->top]>=1)/*如果棧頂元素的優先順序大於+-的優先順序1，則將棧頂元素出棧*/
{
string[j]=S->data[S->top];
S->top--;
}
S->top++;
S->data[S->top]=s[i];/*將當前運算符+或-入棧*/
S->y[S->top]=1;/*+-的優先順序定義為1*/
j++;break;
}
case '*':
case '/':{ if(s[i]=='/'&&s[i+1]=='0') {printf("除數不能為0\n");return(0);}
string[j]=' ';
if(S->y[S->top]>=2)/*如果棧頂元素的優先順序大於等於*或/的優先順序，則將棧頂元素出棧*/
{
string[j]=S->data[S->top];
S->top--;
}
S->top++;
S->data[S->top]=s[i];/*將當前運算符*或/入棧*/
S->y[S->top]=2;/*優先順序定義為2*/
j++;break;
}
}
i++;
}
while(S->top!=-1)/*若棧不為空，出棧直到棧空*/
{
string[j]=S->data[S->top];S->top--;j++;
}
string[j]='\0';
printf("後綴表達式為:%s\n",string);
return(1);
}
int main()
{
char string[max],s[max],flag='1';
while(flag!='0')
{
printf("");
gets(s);
if(pipei(s))
{
if(zhuanghuan(s,string))
yunsuan(string);
}
else printf("bupipei");
printf("結束輸入0，輸入任意字元繼續");
scanf("%c",&flag);
}
}
8. 粒子群優化演算法
姓名：楊晶晶 學號：21011210420 學院：通信工程學院
【嵌牛導讀】
傳統的多目標優化方法是將多目標問題通過加權求和轉化為單目標問題來處理的,而粒子演算法主要是解決一些多目標優化問題的（例如機械零件的多目標設計優化）,其優點是容易實現,精度高,收斂速度快。
【嵌牛鼻子】粒子群演算法的概念、公式、調參以及與遺傳演算法的比較。
【嵌牛提問】什麼是粒子群演算法？它的計算流程是什麼？與遺傳演算法相比呢？
【嵌牛正文】
1. 概念
粒子群優化演算法(PSO：Particle swarm optimization) 是一種進化計算技術（evolutionary computation），源於對鳥群捕食的行為研究。
粒子群優化演算法的基本思想：是通過群體中個體之間的協作和信息共享來尋找最優解。
PSO的優勢：在於簡單容易實現並且沒有許多參數的調節。目前已被廣泛應用於函數優化、神經網路訓練、模糊系統控制以及其他遺傳演算法的應用領域。
2. 演算法
2.1 問題抽象
鳥被抽象為沒有質量和體積的微粒(點)，並延伸到N維空間，粒子i在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)。每個粒子都有一個由目標函數決定的適應值(fitness value)，並且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi。這個可以看作是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest)(gbest是pbest中的最好值)，這個可以看作是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
2.2 更新規則
PSO初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次的迭代中，粒子通過跟蹤兩個「極值」(pbest，gbest)來更新自己。在找到這兩個最優值後，粒子通過下面的公式來更新自己的速度和位置。
公式(1)的第一部分稱為【記憶項】，表示上次速度大小和方向的影響；公式(1)的第二部分稱為【自身認知項】，是從當前點指向粒子自身最好點的一個矢量，表示粒子的動作來源於自己經驗的部分；公式(1)的第三部分稱為【群體認知項】，是一個從當前點指向種群最好點的矢量，反映了粒子間的協同合作和知識共享。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
以上面兩個公式為基礎，形成了PSO的標准形式。
公式(2)和 公式(3)被視為標准PSO演算法。
2.3 標准PSO演算法流程
標准PSO演算法的流程：
1）初始化一群微粒(群體規模為N)，包括隨機位置和速度；
2）評價每個微粒的適應度；
3）對每個微粒，將其適應值與其經過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest；
4）對每個微粒，將其適應值與其經過的最好位置gbest作比較，如果較好，則將其作為當前的最好位置gbest；
5）根據公式(2)、(3)調整微粒速度和位置；
6）未達到結束條件則轉第2）步。
迭代終止條件根據具體問題一般選為最大迭代次數Gk或(和)微粒群迄今為止搜索到的最優位置滿足預定最小適應閾值。
公式(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優位置。
當C1＝0時，則粒子沒有了認知能力，變為只有社會的模型(social-only)：
被稱為全局PSO演算法。粒子有擴展搜索空間的能力，具有較快的收斂速度，但由於缺少局部搜索，對於復雜問題
比標准PSO 更易陷入局部最優。
當C2＝0時，則粒子之間沒有社會信息，模型變為只有認知(cognition-only)模型：
被稱為局部PSO演算法。由於個體之間沒有信息的交流，整個群體相當於多個粒子進行盲目的隨機搜索，收斂速度慢，因而得到最優解的可能性小。
2.4 參數分析
參數：群體規模N，慣性因子 ，學習因子c1和c2，最大速度Vmax，最大迭代次數Gk。
群體規模N：一般取20～40，對較難或特定類別的問題可以取到100～200。
最大速度Vmax：決定當前位置與最好位置之間的區域的解析度(或精度)。如果太快，則粒子有可能越過極小點；如果太慢，則粒子不能在局部極小點之外進行足夠的探索，會陷入到局部極值區域內。這種限制可以達到防止計算溢出、決定問題空間搜索的粒度的目的。
權重因子：包括慣性因子和學習因子c1和c2。使粒子保持著運動慣性，使其具有擴展搜索空間的趨勢，有能力探索新的區域。c1和c2代表將每個粒子推向pbest和gbest位置的統計加速項的權值。較低的值允許粒子在被拉回之前可以在目標區域外徘徊，較高的值導致粒子突然地沖向或越過目標區域。
參數設置：
1)如果令c1＝c2＝0，粒子將一直以當前速度的飛行，直到邊界。很難找到最優解。
2)如果＝0，則速度只取決於當前位置和歷史最好位置，速度本身沒有記憶性。假設一個粒子處在全局最好位置，它將保持靜止，其他粒子則飛向它的最好位置和全局最好位置的加權中心。粒子將收縮到當前全局最好位置。在加上第一部分後，粒子有擴展搜索空間的趨勢，這也使得的作用表現為針對不同的搜索問題，調整演算法的全局和局部搜索能力的平衡。較大時，具有較強的全局搜索能力；較小時，具有較強的局部搜索能力。
3)通常設c1＝c2＝2。Suganthan的實驗表明：c1和c2為常數時可以得到較好的解，但不一定必須等於2。Clerc引入收斂因子(constriction factor) K來保證收斂性。
通常取為4.1,則K＝0.729.實驗表明，與使用慣性權重的PSO演算法相比，使用收斂因子的PSO有更快的收斂速度。其實只要恰當的選取和c1、c2，兩種演算法是一樣的。因此使用收斂因子的PSO可以看作使用慣性權重PSO的特例。
恰當的選取演算法的參數值可以改善演算法的性能。
3. PSO與其它演算法的比較
3.1 遺傳演算法和PSO的比較
1)共性：
(1)都屬於仿生演算法。
(2)都屬於全局優化方法。
(3)都屬於隨機搜索演算法。
(4)都隱含並行性。
(5)根據個體的適配信息進行搜索，因此不受函數約束條件的限制，如連續性、可導性等。
(6)對高維復雜問題，往往會遇到早熟收斂和收斂 性能差的缺點，都無法保證收斂到最優點。
2)差異：
(1)PSO有記憶，好的解的知識所有粒子都保 存，而GA（Genetic Algorithm），以前的知識隨著種群的改變被改變。
(2)PSO中的粒子僅僅通過當前搜索到最優點進行共享信息，所以很大程度上這是一種單共享項信息機制。而GA中，染色體之間相互共享信息，使得整個種群都向最優區域移動。
(3)GA的編碼技術和遺傳操作比較簡單，而PSO相對於GA，沒有交叉和變異操作，粒子只是通過內部速度進行更新，因此原理更簡單、參數更少、實現更容易。
(4)應用於人工神經網路(ANN)
GA可以用來研究NN的三個方面：網路連接權重、網路結構、學習演算法。優勢在於可處理傳統方法不能處理的問題，例如不可導的節點傳遞函數或沒有梯度信息。
GA缺點:在某些問題上性能不是特別好；網路權重的編碼和遺傳運算元的選擇有時較麻煩。
已有利用PSO來進行神經網路訓練。研究表明PSO是一種很有潛力的神經網路演算法。速度較快且有較好的結果。且沒有遺傳演算法碰到的問題。
9. LLVM和GCC的區別
LLVM與GCC在三段式架構上並沒有本質區別。LLVM與其它編譯器最大的差別是，它不僅僅是Compiler
Collection，也是Libraries
Collection。舉個例子，假如說我要寫一個XYZ語言的優化器，我自己實現了PassXYZ演算法，用以處理XYZ語言與其它語言差別最大的地方。而LLVM優化器提供的PassA和PassB演算法則提供了XYZ語言與其它語言共性的優化演算法。那麼我可以選擇XYZ優化器在鏈接的時候把LLVM提供的演算法鏈接進來。LLVM不僅僅是編譯器，也是一個SDK。
10. 怎樣才能學好數據結構
一時間也寫不出太具體的方法 就在網上為你找了一個前輩發的帖子 你看一下，肯定比我寫的好。
-------------------------
學習數據結構這門課程至少要經歷三個過程，方可真正
的掌握這門課程，得到一個滿意的成績。這個過程簡單來說就是三個字：活→死→活。
首先，是一個學「活」的過程，就要要求我們對書中的每一個演算法，能夠在腦海中
建立起相應的模型，而不是死板的演算法。比如樹的遍歷非遞歸演算法，在入棧與出棧的過程
中，我們就要在腦海中形成訪問樹每個結點的過程，真正掌握住這個演算法。這樣，全書復
習下來，你的腦海中就有了整個數據結構的模型概念，對任何一個陌生的演算法，將不感到
生疏和害怕。
有些同學到了此處就覺得數據結構已經學好，可以萬事大吉了，其實這還遠遠不夠
，如果參加考試，往往會拿不到高分，甚至還會納悶，為何自己數據結構學的這樣好，成
績卻不盡如人意，因此產生了批卷老師判錯的想法。所以第二個過程，就是一個學「死」
的過程，這個過程要求，要記住書中的演算法（功利一點就是要背誦會所報考學校的考試要
求的演算法）。有的學校有別的特殊要求，也一並背會。如上海交通大學喜歡考平均復雜度
的分析這樣的題目，我們在書上可以找到這樣的分析一共十一個，全部背會，就免去了在
考場上分析的麻煩，如果連答案都能記住，那麼，也不會因為粗心失分了。這一過程也許
有些枯燥，但卻是最重要的過程，比如說背會了樹的後序遍歷非遞歸，遇到了像求某個結
點的所有祖先，兩個結點的共同祖先這樣的題，不用想，直接套用。這樣才是考試的高分
的關鍵：在考場上，遇到考題，不用思考，直接從腦海中找匹配的演算法，直接引用。
有了第二個過程的辛苦，我們就可以得到一個比較高的分數了，如果還想提高，就
要進行第三個過程，再學「活」的過程。這一個過程中就要要求我們，在第二步的基礎上
，多進行思考，看看有哪些演算法有共性，比如說：樹的前序非遞歸遍歷演算法和圖的深度優
先遍歷演算法是不是類似啊，有些什麼不同，有些什麼相同，為什麼會相同；森林轉化為二
叉樹和圖的生成樹的演算法也是這樣，等等。總結出這種共性，這樣就能正確有效的記憶算
法，同時，遇到難題不至於慌亂，能夠從容下手解題。
對於總結共性問題上，這里舉一小個例子，(呵呵，我當初總結出這個，並且和ka
oyan.com斑竹一具討論確定後三天，就在2002年交大第一題考出類似東東）比如樹的遍
歷，不管是遞歸還是非遞歸，也不管是線索樹，還是頭結點有父母信息的樹，它的遍歷其實就是一個尋找到遍歷的第
一個結點，然後再尋找它的後繼結點的過程，我們歸納到此處，就可以試著總結一下三種
遍歷的後繼結點是哪個，有幾種情況：
對於前序遍歷，它的後繼如下：
（1）若有左孩子，則後繼是左孩子；
（2）若無左孩子，有右孩子，則後繼是右孩子；
（3）若既無左孩子，又無右孩子，則是一片葉子；再討論：
（a）若是其父母的左孩子，且父母有右孩子，則後繼是父母的右孩子。
（b）若是其父母的左孩子，且父母無右孩子；
（c）若是其父母的右孩子。
b，c都表示這是某個節點的左子樹前序遍歷的最後一個節點，則需要找第一個有右子
樹的「左祖先」（定義「左祖先」，即找第一個使得當前節點在這個祖先的左子樹上），
然後後繼就是這個祖先的右孩子。
對於中序遍歷，它的後繼如下：
（1）如有右孩子，後繼是右孩子的最左下節點；
（2）若無右孩子，且是父母的左孩子，則後繼就是父母；
（3）若無右孩子，且是父母的右孩子，則一直上溯到第一個「左祖先」（定義如前）
則後繼就是這個祖先。若無這樣的祖先，說明已經遍歷完畢。
對於後序遍歷，它的後繼如下：
（1）若是父母的右孩子，則後繼是父母；
（2）若是父母的左孩子，且父母無右子樹，則後繼是父母；
（3）若是父母的左孩子，父母有右子樹，則後繼是父母右子樹的最先訪問到的節點（
指向父母的右子樹後，一直往左，若不行的話，往右一步，一直到葉子）
總結完了，想一想，我們還能得到哪些提示？經常有一類型題目，要求求某個結點
的直接前驅。其實求前序遍歷的前驅和求後序遍歷的後繼是一樣的，只不過把左換成右而
已，前序遍歷的求後繼和後序遍歷的求前驅、中序遍歷的求前驅和中序遍歷求後繼都有這
樣的對稱關系。因此，總結出共性的東西，許多題目就可以迎刃而解了。問一問讀到這里
的讀者，你現在能夠自己在腦子裡面，非常輕松地像上面那樣，把這個例子裡面的情況都
條理清楚地分析總結出來嗎？如果現在還不行，到考試之前，你必須掌握到這種程度，才
能得到一個自己很滿意的分數。
經過以上的三個過程復習，相信讀者對數據結構的掌握就可以到達比較高的水平了
，如果參加考試，獲得一個比較滿意的成績也很有希望了。當然，達到這一
步並不容易，大量的練習是真正掌握的必由之路。因此，我們建議大家能夠下功夫把本書
中的題目完整地做一遍。能夠真正把本書中的所有題都掌握，絕不僅僅意味著僅會了書中
這幾百道題目，而是意味著對數據結構這門課程的理解，以及對問題的分析能力都有很大
的提高，這樣在考場上即使遇到未曾見過的題目，也就可以從容應對了！