搜索算法合集
By DijkstraPhoenix
深度优先搜索 (DFS)
引入
如果现在有一个迷宫，怎样走路径最短？
方法
走迷宫最简朴粗暴的方法式什么呢？当然是把所有路都走一遍啦！
如果是手动计算的话，可能会把你手指累得抽筋，但电脑不会，电脑具有强盛的算力，这种暴力的事情当然是交给电脑做啦。
深搜的本质：一条路走到底，走到死胡同再往回走，回到上一个岔口继续走，直到找到精确的路
现实上，任何一条路都可以看做是一个只有一个岔口的分岔路，所以不必要把路和岔口分开计算。
那么刚才的例子应该是这么走（数字代表第几次尝试）现实上岔口走的顺序是任意的，方法不唯一。
概念：从死胡同返回的步调叫做回溯
由于深搜不能包管第一次找到的路径为最短路径，所以必要统计所有门路
深搜一样平常使用递归实现，走过的每个位置都要打上标记，同一条路不能再走一遍
主算法代码:
[code]int maze[MAXN][MAXN];//存储迷宫 0表现当前节点可以走，1表现不能走bool vis[MAXN][MAXN];//打标记const int dx[]={1,0,-1,0};const int dy[]={0,1,0,-1};//位移数组，分别对应 上右下左（如果是八向移动的话要改成对应的）int n,m,stx,sty,edx,edy;//地图长宽以及出发点和尽头的坐标int ans=0x7f7f7f7f;//最短距离，要初始化为极大值void dfs(int x,int y,int z)//x和y是当前位置的坐标，z是走过的步数{ if(x==edx&&y==edy)//到了尽头 { ans=min(ans,z);//更新答案（如果答案还是极大值，说明无法到达尽头） return; } vis[x][y]=true;//打标记 for(int i=0;in>>m>>t; cin>>stx>>sty>>edx>>edy; for(int i=1;i>xjx>>xjy; maze[xjx][xjy]=1; } vis[stx][sty]=1; dfs(stx,sty); cout |
