首页 > 代码库 > 搜索算法思考
搜索算法思考
概述：本文主要讲述一些搜索算法的使用，以及其中奥妙思想的思考。
一：广度搜索与深度搜索---BFS与DFS
1：实现算法导论中的BSF
#include <deque> #define MAX 1000000struct Node{ int d; int p; int color; int id;};int _tmain(int argc, _TCHAR* argv[]){ Node arrNode[8]; int arrGrid[8][8]; deque<Node> q; for(int i=0;i<8;i++) { arrNode[i].color=0; arrNode[i].d=MAX; arrNode[i].p=MAX; arrNode[i].id=i; } for(int i=0;i<8;i++) for(int j=0;j<8;j++) arrGrid[i][j]=0; arrGrid[0][1]=1; arrGrid[0][3]=1; arrGrid[1][2]=1; arrGrid[3][4]=1; arrGrid[3][5]=1; arrGrid[4][5]=1; arrGrid[4][6]=1; arrGrid[5][6]=1; arrGrid[5][7]=1; arrGrid[6][7]=1; arrNode[0].color=1; arrNode[0].d=0; q.push_back(arrNode[0]); while(!q.empty()) { Node u=q.front(); q.pop_front(); for(int i=0;i<8;i++) { if(arrGrid[u.id][i]==1||arrGrid[i][u.id]==1) { Node v=arrNode[i]; if(v.color==0) { arrNode[v.id].color=1; arrNode[v.id].p=u.id; arrNode[v.id].d=u.d+1; q.push_back(arrNode[v.id]); } arrNode[u.id].color=2; } } } return 0;}
2：实现算法导论中的DSF
int Map[6][6];int Visit[6];int Pre[6];int Dis[6];int Fin[6];int time;void DFS();void DFSVisit(int u);int _tmain(int argc, _TCHAR* argv[]){ for(int i=0;i<6;i++) for(int j=0;j<6;j++) Map[i][j]=0; Map[0][1]=1; Map[0][2]=1; Map[1][3]=1; Map[2][1]=1; Map[3][2]=1; Map[4][3]=1; Map[4][5]=1; Map[5][5]=1; for(int i=0;i<6;i++) { Visit[i]=0; Pre[i]=-1; Dis[i]=0; Fin[i]=0; } time=0; DFS(); for(int i=0;i<6;i++) { cout<<Dis[i]<<"/"<<Fin[i]<<" "; } cout<<endl; for(int i=0;i<6;i++) { cout<<Pre[i]<<" "; } cout<<endl; char cc; cin>>cc; return 0;}//6个点的深度DFS；；；；void DFS(){ for(int u=0;u<6;u++) if(Visit[u]==0) DFSVisit(u);}void DFSVisit(int u){ Visit[u]=1;//表示灰色 time++; Dis[u]=time; for(int i=0;i<6;i++) { if(Visit[i]==0&&Map[u][i]>0) { Pre[i]=u; DFSVisit(i); } } Visit[u]=2;//为黑色 time++; Fin[u]=time;}
共同点思想：不会陷入死循环，通过标记为黑而达到；都会搜索到通过非白达到。也就是需要达到全部搜索到则需要对节点标识位；使用结构体数据结构表示，用矩阵表示图；
不同点：BSF是一层一层的搜索，每次弄一次层，就必须知道该层所有房间；
DFS是像走迷宫，直到碰到墙位置才停住，而返回前一个元素，选择没有走过的路。这样可以全部走完整个地图。
搜索:这种适合枚举中选出自己想要的情况。
第二：Bellman_Ford算法与Dijkstra算法
1：Bellman_Ford算法
思想：从某个源头出发，寻找到达各个点的最小距离。会得到一个最小路径的树；
显然：该最小路径中，不能存在环，比如是正环，则通过取掉一条边而导致会变小，从而矛盾；
若为负环：则通过不断走环值，也会导致值变小，而矛盾。
那么最小路径存在可能性就是不存在环路，那么这个最小路径表明是简单路径，对于点是V个的，又是简单路径，显然二点只有一个路径，则只能是V-1个边了。----针对这V-1个边，是路径中最小的情况，那么通过松弛，由于每次松弛都会得到一个边，故而需要V-1次松弛。由于V-1次松弛就能够得到V-1边。每次松弛都是对整个边的。
复杂度是O（VE）
实现思想：边用结构体来表示；点结构体的数组表示含有前驱和距离，下标为点标号；通过V-1次松弛达到求出了每个点的最小距离，以及一颗最小路径树。---可以判断出是否存在最小路径，可以求出最小路径-----且对边权值没有要求，有向。
实现如下：
#define MAX 1000000struct Node{ int d; int p;};struct Edge{ int u; int v; int w;};int _tmain(int argc, _TCHAR* argv[]){ Node node[5]; Edge edge[10]; for(int i=0;i<5;i++) { node[i].d=MAX; node[i].p=MAX; } node[0].d=0;//源 edge[0].u=0; edge[0].v=1; edge[0].w=6; edge[1].u=0; edge[1].v=2; edge[1].w=7; edge[2].u=1; edge[2].v=3; edge[2].w=5; edge[3].u=1; edge[3].v=4; edge[3].w=-4; edge[4].u=1; edge[4].v=2; edge[4].w=8; edge[5].u=2; edge[5].v=3; edge[5].w=-3; edge[6].u=2; edge[6].v=4; edge[6].w=9; edge[7].u=3; edge[7].v=1; edge[7].w=-2; edge[8].u=4; edge[8].v=0; edge[8].w=2; edge[9].u=4; edge[9].v=3; edge[9].w=7; for(int i=0;i<4;i++) {//V-1次 for(int j=0;j<10;j++) { int sum=node[edge[j].u].d+edge[j].w; if(sum<node[edge[j].v].d) { node[edge[j].v].d=sum; node[edge[j].v].p=edge[j].u; } } } for(int j=0;j<10;j++) { int sum=node[edge[j].u].d+edge[j].w; if(sum<node[edge[j].v].d) { cout<<"False"<<endl; return 0; } } cout<<"True"<<endl; return 0;}
2：Dijkstra算法
思想：该算法没有上个算法通用，但是效率高，时间复杂度可达到O(Vlg(V)+E);但是有限定，就是权重不能为负值。
过程思想：从源头出发，对每个节点处的边松弛，直到最后。由于是正值，所以又是从源头开始的，一旦确定它了，那么它就是最小距离了，因为不会通过环而让其更小了，这是因为没有负值的边。-----每次确定是取没有确定的最小值作为这个确定值。
实现如下：
#define MAX 1000000struct Node{ int d; int p; int color;};int _tmain(int argc, _TCHAR* argv[]){ int edge[5][5]; for(int i=0;i<5;i++) for(int j=0;j<5;j++) edge[i][j]=MAX; edge[0][1]=10; edge[0][2]=5; edge[1][2]=2; edge[1][3]=1; edge[2][1]=3; edge[2][3]=9; edge[2][4]=2; edge[3][4]=4; edge[4][0]=7; edge[4][3]=6; Node node[5]; for(int i=0;i<5;i++) { node[i].d=MAX; node[i].p=MAX; node[i].color=0; } node[0].d=0; for(int i=0;i<5;i++) { //取最小值 int minid; int min=MAX+100; for(int j=0;j<5;j++) { if(min>node[j].d&&node[j].color==0) { min=node[j].d; minid=j; } } node[minid].color=1; //松弛 for(int j=0;j<5;j++) { if(edge[minid][j]+node[minid].d<node[j].d&&node[j].color==0) { node[j].d=edge[minid][j]+node[minid].d; node[j].p=minid; } } } return 0;}