走迷宫 分支限界 广度优先搜索

问题描述

 输入一m×n的矩阵，0表示可以经过的路径，1表示障碍物不可经过。并输入起点坐标s_x,s_y，终点坐标f_x,f_y，试判断能否由起点到达终点，并计算最短路径。

算法思想

 对于寻找路径，很容易想到深搜或者广搜两种方式完成，对于这两种方法都可以完成此目标，因为我们想要用分支限界，因此在这里我们选择广搜。对于计算最短路径，我们可以结合分支限界的思想，采取一定的剪枝策略，减去一定不是问题的解或者不是最优解的分支，以降低算法的时空复杂度从而提升效率。

实现过程

1.创建一个队列Q，初始时将起始位置入队；
2.进入循环，只要队列不为空，就出队队首元素，判断队首元素是否为目标终点，如果是则更新beststep即当前最优路径的长度,否则以队首元素作为扩展结点进行扩展；
3.具体扩展思路：
 在此之前我们还需要一个标记数组以判断标记已经走过的路。然后进行扩展，就是将扩展结点的四个儿子进行判断是否入队，即当前队首元素的上下左右四个方位一一进行判断，如果已经走过或者为障碍物，则不可行，如果可行并且到儿子位置的路径小于当前已经找到的最优路径还要近的话，说明此位置有可能成为我们要寻找的最最优路径上的点，于是入队该位置结点；
4.对于剪枝函数，可根据如下进行设计。当前步数小于最优解步数且该位置合法时，才进入子树进行寻找；

Code

#include"stdio.h"
#include"iostream"
using namespace std;

#define Maxn 9999

typedef struct pos
{
	int x;
	int y;
	int step;
}P;

int M[Maxn][Maxn]; // 迷宫数组
int visit[Maxn][Maxn]; // 标记已经走过的地方 用来剪枝
int m,n; // 行 列
int s_x,s_y,f_x,f_y;// 起点 终点
int beststep = Maxn; // 最优路径步数 初始无穷

int direction[4][2]={{0,-1},{1,0},{0,1},{-1,0}};// 左 下 右 上
// 判断位置是否合法
bool isValid(int x,int y)
{
	if(x<0||y<0||x>=m||y>=n)
		return false;
	else if(M[x][y]==1||visit[x][y]==1)
		return false;
	return true;
}
// 广搜遍历 队列实现 分支限界
bool bfs(int s_x,int s_y,int f_x,int f_y)
{
	P Q[Maxn];// 队列
	int front=0,rear=0;
	P now,next;
	now.x = s_x;
	now.y = s_y;
	now.step = 0;
	Q[rear++] = now;
	while(front!=rear)
	{
		now = Q[front++];
		if(now.x==f_x&&now.y==f_y)
		{
			beststep = now.step;
		}
		for(int i=0;i<4;i++)
		{
			next.x = now.x+direction[i][0];
			next.y = now.y+direction[i][1];
			next.step = now.step+1;
			if(isValid(next.x,next.y)&&next.step<beststep)
			{
				visit[next.x][next.y]=1;
				Q[rear++] = next;
			}
		}
	}
	if(beststep == Maxn)
		return false;
	else
		return true;
}

void main()
{
	int i,j;
	cin>>m>>n;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			cin>>M[i][j];
	}
	cout<<endl;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			cout<<M[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"start"<<endl;
	cin>>s_x>>s_y;
	cout<<"final"<<endl;
	cin>>f_x>>f_y;
	bool res = bfs(s_x,s_y,f_x,f_y);
	if(res)
	{
		cout<<"Arrived!"<<endl;
		cout<<"min step is:"<<beststep<<endl;
	}
	else
		cout<<"Can't touch!"<<endl;
}