迷宮演算法
A. 李氏迷宮演算法的發展
迷宮演算法最初是由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版的序言里，李博士就明確闡述了他為蜂窩通信產業制定的目標：「讓我們攜起手來，使蜂窩產業發揮它最大的潛力，我們的目標是：在不遠的將來，讓攜帶型蜂窩電話把我們的通話遍及世界每一個角落。」
B. 迷宮演算法問題
棧走到底也可以回過頭來繼續探索啊，要不怎麼叫深度【遍歷】。
C. 求解迷宮的遞歸演算法
#include<stdio.h>
#include<malloc.h>
#define M 10
#define N 10
struct node
{
int flag;
int x,y;
};
struct link
{
struct node lnode;
struct link *next;
struct link *pri;
};
struct link *head;
struct node maze[M][N];
int maze_flag[M][N]={{1,1,1,1,1,1,1,1,1,1},
{1,1,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}};
int judge(int i,int j);
void in_link(struct node nmaze);
void out_link();
void out_put();
void main()
{
int i,j;
head=(struct link *)malloc(sizeof(struct link));
head->next=head;
head->pri=head;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
}
}
printf("the maze is:\n");
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
head->next=(struct link *)malloc(sizeof(struct link));
head->pri=head->next;
head->next->pri=head;
head->next->next=head;
head->next->lnode.x=1;
head->next->lnode.y=1;
head->next->lnode.flag=1;
printf("wether to find the way?\n");
if(judge(1,1)==1)
printf("the end!\n");
}
int judge(int i,int j)
{
struct node (*pmaze)[N]=maze;
if(pmaze[i][j+1].flag==0)
{
j++;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
printf("goin to judge\n");
return(judge(i,j));
}
else
{
if(pmaze[i+1][j].flag==0)
{
i++;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
if(pmaze[i][j-1].flag==0)
{
j--;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
if(pmaze[i-1][j].flag==0)
{
i--;
if((pmaze[i][j].x==M-2)&&(pmaze[i][j].y==N-2))
{
printf("success to find the way!\n");
out_put();
return(1);
}
pmaze[i][j].flag=1;
in_link(pmaze[i][j]);
return(judge(i,j));
}
else
{
out_link();
struct link *q;
q=head;
while(q->next!=head)
{
q=q->next;
}
judge(q->lnode.x,q->lnode.y);
}
}
}
}
}
void in_link(struct node nmaze)
{
struct link *p;
p=head;
while(p->next!=head)
{
p=p->next;
}
p->next=(struct link *)malloc(sizeof(struct link));
p->next->pri=p;
head->pri=p->next;
p->next->next=head;
p=p->next;
p->lnode.x=nmaze.x;
p->lnode.y=nmaze.y;
p->lnode.flag=nmaze.flag;
}
void out_link()
{
struct link *p;
p=head;
while(p->next!=head)
{
p=p->next;
}
p->pri->next=p->next;
head->pri=p->pri;
free(p);
}
void out_put()
{
struct link *r;
r=head;
while(r->next!=NULL)
{
r=r->next;
printf("%2d%2d\n",r->lnode.x,r->lnode.y);
}
printf("%d%d\n",r->lnode.x,r->lnode.y);
}
D. 求走迷宮的演算法！（計算機的演算法）（編程也可以
我的思路：
按照人類走迷宮的方法，貼著左邊走，左邊有路就向左走，左邊沒路向前走，左邊前面都沒路向右走
機器人的應該是：1.判斷左邊是否有牆，無牆：機器人左轉，前進一步，繼續判斷左。。
2.左邊有牆，則判斷前方是否有牆，無則向前一步，跳回第一步
3.前方有牆（此時狀態是左有牆，前有牆），則向機器人右轉，跳回第一步
另外有個前提條件，機器人轉彎需要原地轉，有轉彎半徑的肯定不行。
還有個問題，就是機器人自己不知道自己已經從迷宮出來了，會一直走。。
E. 求迷宮演算法，c++語言
/*地圖路徑求解程序，用VC++編寫的，在TC下運行可能有問題的。
問題的情況可能是：不認識false和true，去掉下面定義的兩行前面的「/*」即可定義他們
也可能有變數名稱過長的錯誤，如果是那樣，就麻煩你自己修改變數名吧，把所有的變數名稱替換為少於8位元組的*/
#include<stdio.h>
#include<stdlib.h>
#define ROW 9/*定義行數*/
#define COL 13/*定義列數*/
///*#define false 0/*定義false為0，如果在c語言中需要這個，就把前面的「/*」去掉*/
///*#define true 1/*定義true為1，如果在C語言中需要這個，就把前面的「/*」去掉*/
typedef struct RowAndColPath{
int r;
int c;
}RowAndColPath;/*定義結構體實現走步過程的記錄*/
int Move[4][2]={{0,1},{1,0},{-1,0},{0,-1}};/*4個方向*/
RowAndColPath path[ROW*COL];/*走動過程的記錄*/
bool ResultFlag=false;/*找到解的標志*/
bool GettingPath(int step,int CurrentRow,int CurrentCol,int ResultRow,int ResultCol,int MapWay[][COL]);/*遞歸求解方法*/
void main()
{
int MapWay[ROW][COL]={
{1,1,1,1,1,1,1,1,0,1,1,1,1},
{0,0,0,1,1,0,0,0,0,1,1,1,1},
{1,1,0,1,1,1,1,1,0,0,1,1,1},
{1,1,0,0,0,0,1,1,1,0,1,1,1},
{1,1,0,1,1,0,0,0,0,0,0,0,1},
{1,1,0,0,1,1,1,1,1,1,1,0,1},
{1,1,1,0,0,0,0,0,0,1,1,0,1},
{1,1,1,0,1,1,1,1,0,0,0,0,1},
{1,1,1,0,0,0,1,1,1,1,1,1,1}};/*定義地圖*/
int CurrentRow=1,CurrentCol=0,ResultRow=0,ResultCol=8;/*定義初始和結束位置*/
path[0].r=CurrentRow;
path[0].c=CurrentCol;/*初始位置進入歷史的第一步*/
if(GettingPath(1,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay))/*如果走動成功*/
printf("恭喜！查找成功！\n");
else
printf("抱歉，查找失敗！\n");
}
bool GettingPath(int step,int CurrentRow,int CurrentCol,int ResultRow,int ResultCol,int MapWay[][COL])
{
int i,j;
for(i=0;i<4;i++)/*依次對4個方向搜索*/
{
if(ResultFlag)
return true;
CurrentRow+=Move[i][0];
CurrentCol+=Move[i][1];/*先按該方向前進一步*/
if((CurrentRow>=0)&&(CurrentRow<ROW)&&(CurrentCol>=0)&&(CurrentRow<COL))/*如果還在地圖內部*/
{
if(MapWay[CurrentRow][CurrentCol]==0)/*下一步可以走*/
{
for(j=0;j<step;j++)/*判斷是不是重復了以前走過的路*/
{
if((path[j].r==CurrentRow)&&(path[j].c==CurrentCol))
break;
}
if(j==step)/*如果沒有走過這個點，就走*/
{
path[step].r=CurrentRow;
path[step].c=CurrentCol;/*計入該步*/
step++;
if((CurrentRow==ResultRow)&&(CurrentCol==ResultCol))/*如果已到達目的地*/
{
ResultFlag=true;
printf("路徑如下：\n\n");
for(j=0;j<step;j++)
printf("第 %d 步：\t%d\t%d\n",j,path[j].r,path[j].c);
return true;
}
else
{
if(step>=ROW*COL)/*如果已經走遍了地圖，就宣布失敗*/
return 0;
if(!ResultFlag)
GettingPath(step,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay);/*沒有到達目的，繼續走*/
}
}
else/*如果已經走過這一點，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果該點不可走，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果該步出地圖了，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
if(ResultFlag)
return true;
return false;/*無路可走*/
}
F. 數據結構演算法（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[M][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還是不錯滴
}
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[M][N])
{
int i,j;
int m,n; //迷宮行,列 [/M]
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("你建立的迷宮為(最外圈為牆)...\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[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北 [/M]
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");
}
測試數據，演算法復雜度你就自己來寫吧，如果你連這都不自己做，那你一定是在應付作業。勸你還是自己運行測試一下吧，免得答辯時老師問你，什麼都不知道，那你就悲劇了。祝你好運！！
G. 迷宮演算法復雜度如何計算
迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。
H. 遞歸演算法解決迷宮問題
給你給偽演算法：（設坐標為x,y,坐標向右和下延生。） 函數： ｛ 判斷當前是不是（7,7)，如果是，表示走出迷宮。列印軌跡 1 嘗試往左先走一步（x-1，如果x小於0，或者對應位置標識為阻塞） 2 1如果成功，用本函數遞歸調用左走一步的坐標，並記下當前位置到軌跡列表。 3 嘗試往前先走一步（y+1，如果y小於0，或者對應位置標識為阻塞） 4 3如果成功，用本函數遞歸調用前走一步的坐標,並記下當前位置到軌跡列表。 5 嘗試往右先走一步（x+1，如果x小於0，或者對應位置標識為阻塞） 6 5如果成功，用本函數遞歸調用前走一步的坐標,並記下當前位置到軌跡列表。 如果是（0，0），表示沒有合適的路徑可走出迷宮。 如果不是（0，0），將軌跡列表最後一位彈出。 ｝
I. 迷宮問題演算法設計！！急急急（c語言）
額，又是課程設計。。。
迷宮類演算法，用棧，隊列來做。不過一般來隊列，因為隊列能夠在較短時間內求出最短路徑。
在網上搜下，很多的。。
你的要求很難達到。。。