最短路徑演算法迷宮
⑴ 求一個求從迷宮的一點到另一點的最短路徑的遞歸演算法
typedef struct node
{
int i;
struct node **nearby;//相鄰結點可以有多個，所以這里用指針的指針
} MAPNODE;
MAPNODE a,b;
int minpath(a,b)//從a結點到b結點可以分成兩步，1.從a到b的相鄰結點。2.從相鄰結點到b結點，這就是一個遞歸的過程
{
int dis=0;
int min=999999;//一個足夠大的數據
MAPNODE **p;
if(a.i==b.i)//序號相同表示是同一結點，path為0
{
dis=0;
}
else
{
for(p=b.nearby;*p!=0;p++)
{
dis=0;
dis+=minpath(a,*p);
dis<min?min=dis:;
}
}
return dis;
}
⑵ 數據結構演算法 用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;
}
⑶ 〔C++演算法分析〕迷宮問題
在還沒學習bfs的情況下做到一個迷宮問題，於是的大概了解了一下DFS和BFS，就以本題為例子講一下我初識的bfs
/*
試題 : 迷宮
本題總分：15 分
【問題描述】
下圖給出了一個迷宮的平面圖，其中標記為 1 的為障礙旁握纖，標記為 0 的為可 以通行的地方。
010000
000100
001001
110000
迷宮皮滲的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這個它的上、下、左、右四個方向之一。
對於上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮，一運仿共10步。其中 D、U、L、R 分別表示向下、向上、向左、向右走。
對於下面這個更復雜的迷宮（30 行50 列），請找出一種通過迷宮的方式， 其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。
請注意在字典序中D<L<R<U。（如果你把以下文字復制到文本文件中，請務必檢查復制的內容是否與文檔中的一致。
在試題目錄下有一個文件 maze.txt， 內容與下面的文本相同）
【答案提交】
這是一道結果填空的題，你只需要算出結果後提交即可。
本題的結果為一個字元串，包含四種字母 D、U、L、R，
在提交答案時只填寫這個字元串，填寫多餘的內容將無法得分。
*/
#include
#include
#include
using namespace std;
const int N = 30;
const int M =50; //數據范圍
const int fx[4][2] = { 1, 0, 0, -1, 0, 1, -1, 0 }; //方向向量，直接按字典序排列
const char dic[5] = "DLRU"; //字典序
char maze[N+5][M+5]; //地圖
char path[N+5][M+5]; //上一步的方向
void bfs()
{
queue > q;
q.push(make_pair(1,1));
maze[1][1]= '1';
while(!q.empty())
{
intx = q.front().first;
inty = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
intxx = x + fx[i][0];
intyy = y + fx[i][1];
if(maze[xx][yy] == '0')
{
maze[xx][yy]= '1';
q.push(make_pair(xx,yy));
path[xx][yy]= i;
}
}
}
}
void print(int x, int y)
{
if(x != 1 || y != 1)
{
intt = path[x][y];
print(x- fx[t][0], y - fx[t][1]);
maze[x][y]= 1; //將走過的地方置1
cout<< dic[t];
}
}
int main()
{
freopen("text.ini","r", stdin);
memset(maze,'1', sizeof maze); //加圍牆
for(int i = 1; i <= N; i++)
cin>> maze[i]+1;
bfs();
memset(maze,0, sizeof maze); //初始化，0為牆，1為路徑
maze[1][1]= 1;
print(N,M); //輸出最短路徑字元，同時標記路徑為1
//輸出迷宮圖
cout<< endl;
for(int i = 0; i <= N + 1; i++)
{
for(int j = 0; j <= M + 1; j++)
{
if(i == 0 || i == N + 1 || j == 0 || j == M + 1) cout << "※"; //畫圍牆
elseif (maze[i][j] == 0) cout << "■"; //迷宮里的牆
elsecout << "□"; //最短路的路徑
}
cout<< endl;
}
cout<< "\nover" << endl;
while(1);
return0;
}
事例中，我們先將整個maze數組鋪滿全部范圍，來建立牆，然後再對maze數組賦值，來建立迷宮，從而達到，牆裹著迷宮的效果。
然後我們建立一個名為q的queue來保存我們現在所在的位置。
數組fx代表方向，dic代表方向的字元。
數組path記錄上一步的方向
尋路部分
首先將起點放入queue中，取得點之後，讓起點出隊，在吧起點堵死成牆。
然後從起點獲得的值去同時向外延伸，遇到牆不延伸，死路表示這條線終結，沒次延伸後，都把原來的點設置成牆。
在延伸的過程中，沒到一個點便堵死成牆，並且出隊，這樣防止一個點多重賦值。
因為是對目前隊列里所有的點同時延伸（雖然有先後順序，但是總會延伸完這一階段的點才會延伸下一階段的點），所以不必擔心走那條路會早一點到某一點，因為完到的，已經被堵死了。
在將所有起點能到達的點延伸完畢之後，隊列為空，進行結算。
如果起點能達到終點的話，終點的path必定有值，只需要在終點倒推即可得到答案。
畫圖部分
先把全體設置成牆，再按照path倒推，結果是路程全被篩選出來。
by：有我wa
⑷ 李氏迷宮演算法的發展
迷宮演算法最初是由C．Y．Lee提出的,又稱為李氏演算法或波擴法，其優點是只要最短路徑存在，就一定能找到，然而其缺點也是明顯的，對於n×n的網格空間，它需要O（n2）的運行時間和存儲空間並產生了較多的層間引線孔。
C.Y.LEE簡介:
William C.Y.Lee(威廉．C．Y．李)博士，國際著名科學家，教育家，近代移動通信奠基人之一。
李博士於1963年獲得美國Ohio State University電氣工程博士學位；1964～1979年，開創了美國貝爾試驗室下的移動無線電通信研究室；1979～1985年，任美國ITT公司國防通信部的尖端技術開發部主管；1985～2000年，任美國Vodafone AirTouch公司副總裁和首席科學家。2000～2005年，任美國LinkAir通信公司董事長，現任美國Treyspan公司董事長。
李博士因開發了商用的AMPS和CDMA技術而享譽全世界，在其幾十年的科研生涯中，獲得殊榮無數。1982年成為IEEE會員，1987年成為全美無線電俱樂部會員，1982～1998年應美國George Washington University邀請，主講最早的面向產業的蜂窩和移動通信課程。還有ITTDCD的技術貢獻獎(1984)，Ohio State University有突出貢獻的校友(1990)，IEEE VTSAvant Garde獎(1990)，美國CTIA的獎勵證書(1994)，IEEE車載技術協會技術服務獎(1996)，中美(SATEC)傑出貢獻證書(1997)以及貝爾試驗室致力服務獎(1998)，等等。李博士還是美國國家競爭委員會的會員，美國加利福尼亞州科學技術委員會成員，北京航空航天大學、西南交大的名譽教授。
李博士為蜂窩通信領域作出了巨大的貢獻。他的重要專著和教科書《無線與蜂窩通信》(1989年第1版，1997年第2版，本書是2006年第3版的中文版)風靡全球，已被翻譯成俄文版、漢語版、日語版、韓語版等多種文字。在該書第1版的序言里，李博士就明確闡述了他為蜂窩通信產業制定的目標：「讓我們攜起手來，使蜂窩產業發揮它最大的潛力，我們的目標是：在不遠的將來，讓攜帶型蜂窩電話把我們的通話遍及世界每一個角落。」
⑸ 如何用c語言實現求迷宮的最短路徑
#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定義迷宮，0表示能走的塊，1表示不能走，在外圍加上一圈不能走的塊
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //塊的位置
int pre; //本路徑中上一塊在隊列中的下標
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索演算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四個方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循環
}
}
}
return 0;
}
void print(int n) //輸出 路徑演算法
{
int k=n,j,m=1;
printf("\n");
do //將輸出的路徑上的所有pre改為-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮最短路徑如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}
⑹ 迷宮最短路徑
用堆棧不一定能得出最短路徑，改用隊列可以實現最短路徑，下面是《數據結構演算法與應用-C++語言描述》裡面的一段話。
[迷宮老鼠] 使用F I F O分枝定界，初始時取（1，1）作為E-節點且活動隊列為空。迷宮的位置（1 , 1）被置為1，以免再次返回到這個位置。（1，1）被擴充，它的相鄰節點（1，2）和（2，1）加入到隊列中（即活節點表）。為避免再次回到這兩個位置，將位置（ 1，2）和（2，1）置為1。
1 1 0
1 1 1
0 0 0
a）
1 1 1
1 1 1
0 0 0
b）
1 1 1
1 1 1
1 0 0
c）
節點（1，2）從隊列中移出並被擴充。檢查它的三個相鄰節點（見圖1 6 - 1的解空間），只有
（1，3）是可行的移動（剩餘的兩個節點是障礙節點），將其加入隊列，並把相應的迷宮位置置
為1，所得到的迷宮狀態如圖17-1b 所示。節點（1，2）被刪除，而下一個E-節點（2，1）將
會被取出，當此節點被展開時，節點（3，1）被加入隊列中，節點（3，1）被置為1，節點（2，
1）被刪除，所得到的迷宮如圖17-1c 所示。此時隊列中包含（1，3）和（3，1）兩個節點。隨
後節點（1，3）變成下一個E-節點，由於此節點不能到達任何新的節點，所以此節點即被刪除，
節點（3，1）成為新的E-節點，將隊列清空。節點（3，1）展開，（3，2）被加入隊列中，而
（3，1）被刪除。（3，2）變為新的E-節點，展開此節點後，到達節點（3，3），即迷宮的出口。
使用F I F O搜索，總能找出從迷宮入口到出口的最短路徑。
⑺ 迷宮問題（棧或隊列，最短路徑）（c語言）
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};
struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/
int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze
[N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*************建立迷宮*******************/
void initmaze(int maze
[N])
{
int i,j;
int m,n; //迷宮行,列
printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto
[N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北
initmaze(sto);//建立迷宮
printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}