走迷宮演算法
示例：
#coding:UTF-8
globalm,n,path,minpath,pathnum
m=7
n=7
k=[0,1,2,3,4,5,6,7]#循環變數取值范圍向量
a=[[0,0,1,0,0,0,0,0],
[1,0,1,0,1,1,1,0],
[0,0,0,0,1,0,0,0],
[1,1,1,1,1,0,0,0],
[0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0]]#迷宮矩陣
b=[[1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]] #狀態矩陣
path=[]
minpath=[]
min=10000
step=0
pathnum=0
#print(a)
#print(b)
defnextone(x,y):
globalpath,minpath,m,n,min,step,pathnum
if(x==0)and(y==0):
path=[]
step=0
if(x==m)and(y==n):
pathnum+=1
print("step=",step)
print("path=",path)
ifstep<min:
min=step
minpath=path[:]
else:
if(x+1ink)and(yink):
if(b[x+1][y]==0)and(a[x+1][y]==0):
b[x+1][y]=1
path.append([x+1,y])
step+=1
nextone(x+1,y)
step-=1
path.remove([x+1,y])
b[x+1][y]=0#回溯
if(xink)and(y+1ink):
if(b[x][y+1]==0)and(a[x][y+1]==0):
b[x][y+1]=1
path.append([x,y+1])
step+=1
nextone(x,y+1)
step-=1
path.remove([x,y+1])
b[x][y+1]=0#回溯
if(x-1ink)and(yink):
if(b[x-1][y]==0)and(a[x-1][y]==0):
b[x-1][y]=1
path.append([x-1,y])
step+=1
nextone(x-1,y)
step-=1
path.remove([x-1,y])
b[x-1][y]=0#回溯
if(xink)and(y-1ink):
if(b[x][y-1]==0)and(a[x][y-1]==0):
b[x][y-1]=1
path.append([x,y-1])
step+=1
nextone(x,y-1)
step-=1
path.remove([x,y-1])
b[x][y-1]=0#回溯
nextone(0,0)
print()
print("min=",min)
print("minpath=",minpath)
print("pathnum=",pathnum)
㈡ 求走迷宮問題的演算法，要求用java寫的
public class Maze { private int[][] maze = null;
private int[] xx = { 1, 0, -1, 0 };
private int[] yy = { 0, 1, 0, -1 };
private Queue queue = null; public Maze(int[][] maze) {
this.maze = maze;
queue = new Queue(maze.length * maze.length);
} public void go() {
Point outPt = new Point(maze.length - 1, maze[0].length - 1);
Point curPt = new Point(0, 0);
Node curNode = new Node(curPt, null);
maze[curPt.x][curPt.y] = 2;
queue.entryQ(curNode); while (!queue.isEmpty()) {
curNode = queue.outQ();
for (int i = 0; i < xx.length; ++i) {
Point nextPt = new Point();
nextPt.x = (curNode.point).x + xx[i];
nextPt.y = (curNode.point).y + yy[i];
if (check(nextPt)) {
Node nextNode = new Node(nextPt, curNode);
queue.entryQ(nextNode);
maze[nextPt.x][nextPt.y] = 2;
if (nextPt.equals(outPt)) {
java.util.Stack<Node> stack = new java.util.Stack<Node>();
stack.push(nextNode);
while ((curNode = nextNode.previous) != null) {
nextNode = curNode;
stack.push(curNode);
}
System.out.println("A Path is:");
while (!stack.isEmpty()) {
curNode = stack.pop();
System.out.println(curNode.point);
}
return;
}
}
}
}
System.out.println("Non solution!");
} private boolean check(Point p) {
if (p.x < 0 || p.x >= maze.length || p.y < 0 || p.y >= maze[0].length) {
return false;
}
if (maze[p.x][p.y] != 0) {
return false;
}
return true;
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new Maze(maze).go();
} private class Queue { Node[] array = null;
int size = 0;
int len = 0;
int head = 0;
int tail = 0; public Queue(int n) {
array = new Node[n + 1];
size = n + 1;
} public boolean entryQ(Node node) {
if (isFull()) {
return false;
}
tail = (tail + 1) % size;
array[tail] = node;
len++;
return true;
} public Node outQ() {
if (isEmpty()) {
return null;
}
head = (head + 1) % size;
len--;
return array[head];
} public boolean isEmpty() {
return (len == 0 || head == tail) ? true : false;
} public boolean isFull() {
return ((tail + 1) % size == head) ? true : false;
}
} private class Node { Point point = null;
Node previous = null; public Node() {
this(null,null);
} public Node(Point point, Node node) {
this.point = point;
this.previous = node;
}
} private class Point { int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
}
}
㈢ 電腦鼠走迷宮中迷宮搜索演算法都有哪些
左手法則、右手法則，中左、中右法則，中心演算法，洪水演算法，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版的序言里，李博士就明確闡述了他為蜂窩通信產業制定的目標：「讓我們攜起手來，使蜂窩產業發揮它最大的潛力，我們的目標是：在不遠的將來，讓攜帶型蜂窩電話把我們的通話遍及世界每一個角落。」
㈤ 用java語言控制小機器人走迷宮的演算法
我昨天剛寫了個走迷宮的界面(一個初始小球，一個目標小球，隨機在界面種生成障礙(迷宮圖)，然後初始小球移動到目標小球那)，不知道是否跟你的想法一樣。用的是回溯法(目前我只知道這個演算法走迷宮)，你可以查下。PS:我電腦沒聯網不能把代碼給你…QQ254774042。
㈥ 求走迷宮問題的演算法，要求用非遞歸回溯的方法寫
public class MyMaze { private class Point { //自定義數組下標記錄類型 int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
} private int[][] maze = null; //迷宮圖
private java.util.Stack<Point> stack = new java.util.Stack<Point>();
//保存路徑的棧 public MyMaze(int[][] maze) {
this.maze = maze;
} public void go() {
Point out = new Point(maze.length-1, maze[0].length-1); //出口
Point in = new Point(0,0); //入口
Point curNode = in; //當前點為入口
Point nextNode = null; //下一個訪問點(目標點) while(!curNode.equals(out)) {
nextNode = new Point(curNode.x,curNode.y); //設置目標點為當前點，便於下面偏移
if((curNode.x+1)<maze.length&&maze[curNode.x+1][curNode.y]==0) { //如果下方是空的，則目標點向下偏移
nextNode.x++;
} else if((curNode.y+1)<maze[0].length&&maze[curNode.x][curNode.y+1]==0) { //如果右邊是空的，則目標點向右偏移
nextNode.y++;
} else if((curNode.x-1)>=0&&maze[curNode.x-1][curNode.y]==0) { //如果上方是空的，則目標點向上偏移
nextNode.x--;
} else if((curNode.y-1)>=0&&maze[curNode.x][curNode.y-1]==0) { //如果左邊是空的，則目標點向左偏移
nextNode.y--;
} else { //這里是沒有路的狀態
maze[curNode.x][curNode.y] = 3; //標記為死路
if(stack.isEmpty()) { //判斷棧是否為空
System.out.println("Non solution");
return;
}
curNode = stack.pop(); //彈出上一次的點
continue; //繼續循環
} //如果有路的話會執行到這里
stack.push(curNode); //當前點壓入棧中
maze[curNode.x][curNode.y] = 2; //標記為已走
curNode = nextNode; //移動當前點
} if(nextNode.equals(out)) {
stack.push(nextNode); //將出口點添加到當前路勁中
maze[nextNode.x][nextNode.y] = 2; //標記為已走
}
System.out.println("\n該迷宮的一條可行路勁為：");
System.out.println("\n"+stack);
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new MyMaze(maze).go();
}
}
㈦ 迷宮演算法問題
棧走到底也可以回過頭來繼續探索啊，要不怎麼叫深度【遍歷】。
㈧ 數據結構與演算法實驗題 簡單的走迷宮
哥們你福大的吧！
㈨ 迷宮演算法
#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還是不錯滴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[M][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[M][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");
}
㈩ 迷宮演算法復雜度如何計算
迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。