走迷宫算法
示例：
#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)左右。
只要记录走到每一格的最优解就可以了。
最好不要用深度优先搜索。用广度优先的实现方便。