迷宮演算法廣度優先

⑴ 廣度優先搜索代碼。也就是迷宮問題

這個bfs問題很容易掌握，是一種基礎演算法
首先記得添加<queue>隊列容器
建立一個隊列容器

之後 往裡面壓迷宮的起點 （通常是結構體）
之後在循環中加判斷 判斷當前取出的點是否能走，如果可以，壓入它四周的四個點（視題目情況 不一定是四周） 再進行下一輪循環
循環體一般是while (!q.empty())
循環一開始一般是 p=q.front(); //取出第一個元素
q.pop(); //刪除第一個元素

⑵ 深度優先和廣度優先 的區別 ，用法。

1、主體區別

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。

2、演算法區別

深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

3、用法

廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。

(2)迷宮演算法廣度優先擴展閱讀：

實際應用

BFS在求解最短路徑或者最短步數上有很多的應用，應用最多的是在走迷宮上，單獨寫代碼有點泛化，取來自九度1335闖迷宮一例說明，並給出C++/Java的具體實現。

在一個n*n的矩陣里走，從原點（0,0）開始走到終點（n-1,n-1），只能上下左右4個方向走，只能在給定的矩陣里走，求最短步數。n*n是01矩陣，0代表該格子沒有障礙，為1表示有障礙物。

int mazeArr[maxn][maxn]; //表示的是01矩陣int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向，int visit[maxn][maxn]; //表示該點是否被訪問過，防止回溯，回溯很耗時。核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。

⑶ 迷宮演算法復雜度如何計算

迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。

⑷ 演算法設計：求廣度優先搜索解決迷宮問題的思路

廣度優先一般就是使用隊列，創建一個隊列，然後開始搜索起始點四周的結點加入隊列，搜完一個結點後作出標記避免重復搜索，接著出隊列繼續搜索，知道搜索完隊列內的結點。
廣度優先就是先搜索四周的慢慢向四周擴展。

⑸ 廣度優先搜索C語言演算法

廣度優先搜索演算法，是按層遍歷各個結點，以求出最短或最優的解，
常用於計算路徑的最短距離，和最佳通路。
例如：迷宮的最短路徑計算，推箱子的移動最小步數等小游戲，都是按廣度搜索來進行的。

這個演算法是教程中很經典的，有很多例子和代碼。你可以好好研究！

如下是一段迷宮的最佳路徑求解演算法。
#include <stdio.h>

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

⑹ 求廣度優先演算法C++走迷宮程序，可以顯示路徑

一般迷宮尋路可以用遞歸的演算法，或者用先進後出的棧數據結構實現

用的是深度優先的演算法，可以尋找到走出迷宮的路徑

但本題要求求出最短的路徑，這就要使用廣度優先的演算法

一般在程序中需要用到先進先出的隊列數據結構

下面是程序的代碼，主要原理是用到

quei，quej和prep三個數組來構成隊列

分別儲存路徑的行，列坐標和上一個節點在隊列中的位置

大致演算法如下，右三個嵌套的循環實現

首先是第一個節點進入隊列

當隊列不空（循環1）

｛

遍歷隊列中每節點(循環2）

｛

將八個方向能夠走的節點加入隊列（循環3）

｝

舊的節點出列

｝

#include<iostream>
#include<ctime>
usingnamespacestd;

#defineMAXNUM50

voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];

srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數，太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}

//以上是輸入和迷宮生成，一下是走迷宮


intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭，隊列尾，隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列

intpos;//當前節點在隊列中的位置，
intii,jj,ni,nj;//當前節點的坐標，新節點的坐標
intdir;//移動方向

if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;


while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}

if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}

delete[]quei;
delete[]quej;
delete[]prep;
}

⑺ 迷宮演算法 上下左右 優先順序問題

迷宮一般採用遞歸演算法，而且出口位置在演算法開始時候是不知道的吧。而且迷宮的出口也不會固定到哪一個方向。如果採用枚舉方法一般是按順時針或者逆時針找，這樣才可以用循環來做，如果採用優先，只能將每個方向定位，設一個常量，那樣的話每次遞歸都要判斷一下，非常麻煩，估計還比不用優先還慢一些。

⑻ 關於廣度優先搜索演算法

廣度優先搜索演算法，是按層遍歷各個結點，以求出最短或最優的解，
常用於計算路徑的最短距離，和最佳通路。
例如：迷宮的最短路徑計算，推箱子的移動最小步數等小游戲，都是按廣度搜索來進行的。

這個演算法是教程中很經典的，有很多例子和代碼。你可以好好研究！

如下是一段迷宮的最佳路徑求解演算法。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

⑼ C語言用圖的廣度優先遍歷做漫步迷宮問題

這是我們老師給我們上數據結構課的課件

#include "stdio.h"
typedef int datatype; /*假定線性表元素的類型為整型*/
#define maxsize 1024 /*假定線性表的最大長度為1024*/
# define n 100 /* 圖的頂點最大個數 */
typedef char VEXTYPE; /* 頂點的數據類型 */
typedef float ADJTYPE; /* 權值類型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 頂點信息數組 */
ADJTYPE arcs[n][n] ; /* 邊權數組 */
int num ; /* 頂點的實際個數 */
}GRAPH;

/***********************1。置空圖**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}

/***********************2。求結點數**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}

/***********************3。創建圖**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("請輸入頂點數目：");
scanf("%d",&L->num);
printf("請輸入各頂點的信息(單個符號）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("請輸入邊權矩陣的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("圖已經創建完畢！");
}

/***********************4。圖的輸出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n圖的頂點數目為：%d",L.num);
printf("\n圖的各頂點的信息為：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n圖的邊權矩陣的信息為：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("圖已經輸出完畢！");
}

/***********************5。圖的深度周遊**********************/
void DFS(GRAPH g,int qidian,int mark[])
//從第qidian個點出發深度優先周遊圖g中能訪問的各個頂點
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。圖的深度周遊**********************/
void GraphDFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //隊列元素的數據類型
typedef struct
{
DATATYPE data[maxsize]; //隊中元素
int front,rear; //隊頭元素下標、隊尾元素後面位置的下標
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//將順序循環隊列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果順序循環隊列sq為空，成功返回1，否則返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//將順序循環隊列sq的隊頭元素保存到e所指地址，成功返回1，失敗返回0
{
if (QueueIsEmpty(sq))

else

}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//將元素x入隊列sq的隊尾，成功返回1，失敗返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//將隊列sq隊首元素出隊列，成功返回1,失敗返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。圖的廣度周遊**********************/
void BFS(GRAPH g,int v,int mark[])
//從v出發廣度優先周遊圖g中能訪問的各個頂點
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。圖的廣度周遊**********************/
void GraphBFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n廣度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}

/***********************主函數**********************/

void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}

⑽ 一般迷宮游戲用到什麼演算法

狀壓DP，或者記憶化搜索。
一般的就是F[i,j,k]表示站在i,j點，當前已經得到了k的狀態。然後轉移。