共性算法
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）若是父母的左孩子，父母有右子树，则后继是父母右子树的最先访问到的节点（
指向父母的右子树后，一直往左，若不行的话，往右一步，一直到叶子）
总结完了，想一想，我们还能得到哪些提示？经常有一类型题目，要求求某个结点
的直接前驱。其实求前序遍历的前驱和求后序遍历的后继是一样的，只不过把左换成右而
已，前序遍历的求后继和后序遍历的求前驱、中序遍历的求前驱和中序遍历求后继都有这
样的对称关系。因此，总结出共性的东西，许多题目就可以迎刃而解了。问一问读到这里
的读者，你现在能够自己在脑子里面，非常轻松地像上面那样，把这个例子里面的情况都
条理清楚地分析总结出来吗？如果现在还不行，到考试之前，你必须掌握到这种程度，才
能得到一个自己很满意的分数。
经过以上的三个过程复习，相信读者对数据结构的掌握就可以到达比较高的水平了
，如果参加考试，获得一个比较满意的成绩也很有希望了。当然，达到这一
步并不容易，大量的练习是真正掌握的必由之路。因此，我们建议大家能够下功夫把本书
中的题目完整地做一遍。能够真正把本书中的所有题都掌握，绝不仅仅意味着仅会了书中
这几百道题目，而是意味着对数据结构这门课程的理解，以及对问题的分析能力都有很大
的提高，这样在考场上即使遇到未曾见过的题目，也就可以从容应对了！