迷宫算法回溯
❶ c++迷宫回溯算法问题 为什么一地次执行if（ok!=1） mase[x][y]=0;这条语句后没有返回main函数
你这个是递归算法啊，当它第一次运行完后，肯定是返回上一次递归进来的地方啦
❷ 回溯算法的基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
❸ 请教高手C++数据结构回溯算法解，迷宫问题
//迷宫用栈做的
#include "stdio.h"
#include "stdlib.h"
#define INITSIZE 100
#define STACKINCRESMENT 10
#define WALL 9999
struct stack
{
int *base;
int *top;
int size;
};
struct mi
{
int val;
bool tag;
int di;
};
void init_stack(stack *);
void push(stack*,int);
int pop(stack*);
int getop(stack*);
int palace(stack*, mi p[10][10]);
int main()
{
int e;
int ch;
struct mi p[10][10];
for(int i=0;i<10;i++)
{
p[0][i].val = 0;
p[i][0].val = 0;
p[9][i].val = 0;
p[i][9].val = 0;
}
for(int j=1;j<9;j++)
{
for(int k=1;k<9;k++)
{
p[j][k].val = 1;
}
}
p[1][3].val = p[1][7].val =0;
p[2][3].val = p[2][7].val =0;
p[3][5].val = p[3][6].val =0;
p[4][2].val = p[4][3].val = p[4][4].val =0;
p[5][4].val = 0;
p[6][2].val = p[6][6].val =0;
p[7][2].val = p[7][3].val = p[7][4].val =0;
p[7][6].val = p[7][7].val =0;
p[8][1].val = 0;
for(int m=0;m<10;m++)
{
for(int n=0;n<10;n++)
{
printf(" %d ",p[m][n]);
p[m][n].tag =0;
p[m][n].di =0;
}
printf("\n");
}
struct stack *s = (stack*)malloc(sizeof(stack));
init_stack(s);
palace(s, p);
printf("\none path is: \n");
for(int a=0;*s->base<89;s->base++)
{
printf("-a");
printf("%d",*s->base);
}
return 0;
}
void init_stack(stack *s)
{
s->base = (int*)malloc(INITSIZE*sizeof(stack));
if(!s->base) printf("malloc error:");
*s->base++ = 0;//栈底为0
s->top = s->base;
s->size = INITSIZE;
}
void push(stack* s, int e)
{
if(s->top - s->base >= INITSIZE)
{
s->base = (int*)realloc(s->base,(s->size+STACKINCRESMENT)*sizeof(stack));
s->top = s->base + s->size;
s->size += STACKINCRESMENT;
}
*s->top++ = e;
}
int pop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
e = *--s->top;
*s->top = NULL;
return e;
}
int getop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
stack *p = s;
e = *(--p->top);
++p->top;
return e;
}
int palace(stack* s, mi p[10][10])
{
int i=1;
int j=1;
int k;
int r;
push(s,i*10+j);
j++;
do
{
r=getop(s);
if(r==88) return 0;
if(p[i][j].val>0 && p[i][j].di<1)
{
push(s,i*10+j);
p[i][j].tag = 1;
p[i][j].di = 1;
j++;
}
else
{
k = getop(s);
i = k/10;
j = k%10;
if(p[i][j].di==1 && (p[i][j].val>0))
{
p[i][j].di++;
i++;
}
if(p[i][j].di==2 && (p[i][j].val>0))
{
p[i][j].di++;
j--;
if(p[i][j].di>0) { k = pop(s);}
}
}
}while(1);
}
❹ 求走迷宫问题的算法，要求用非递归回溯的方法写
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 "stdafx.h"
#include <iostream>
#include "cmath"
#include <fstream>
using namespace std ;
int ROW ;
int COL ;
int **g_pRoom ;
// 回溯法注意标记已访问过的节点。。。。。不然就会进入重复操作将栈用空。。。。。。。。
struct Point
{
Point( int xx = 0, int yy = 0 ):x(xx),y(yy) { }
int x ;
int y ;
} ;
int g_nMax = 0 ;
Point g_pResult[100] ;
int g_nCount ;
Point g_pStart ;
Point g_pEnd ;
Point g_pOrient[4] = { Point(-1, 0 ) , Point( 0 ,1 ) , Point( 1 ,0 ) , Point( 0 , -1 ) } ;
bool Read_data( ifstream &file )
{
if( file.eof() )
return false ;
g_nMax = 0 ;
g_nCount = 0 ;
file>>ROW>>COL ;
g_pRoom = new int*[ROW] ;
g_pStart = g_pEnd = Point( -1, -1 ) ;
for( int i = 0 ; i < ROW ; i++ )
g_pRoom[i] = new int[COL] ;
for( int i = 0 ; i < ROW ; i++ )
for( int j = 0 ; j < COL ; j++ )
{
file>>g_pRoom[i][j] ;
if( g_pRoom[i][j] == -1 )
{
g_pStart.x = j ;
g_pStart.y = i ;
}
else if( g_pRoom[i][j] == -2 )
{
g_pEnd.x = j ;
g_pEnd.y = i ;
}
}
if( g_pStart.x == -1 || g_pEnd.x == -1 )
{
cout<<" the data errror !\n" ;
return false ;
}
return true ;
}
void Dateback( Point pStart )
{
static Point Stack[1000] ;
static int nTop = 0 ;
static int Apple = 0 ;
if( pStart.x == g_pEnd.x && pStart.y == g_pEnd.y )
{
if( Apple + 2 > g_nMax )
{
g_nMax = Apple + 2 ;
for( int i = 0 ; i < nTop ; i++ )
g_pResult[i] = Stack[i] ;
g_nCount = nTop ;
} // ....
}
else
{
for( int i = 0 ; i < 4 ; i++ )
{
Point s ;
s.x = pStart.x + g_pOrient[i].x ;
s.y = pStart.y + g_pOrient[i].y ;
if( s.x >= 0 && s.x < COL && s.y >= 0 && s.y < ROW && g_pRoom[s.y][s.x] != 0 )
{
Apple += g_pRoom[s.y][s.x] ;
Stack[nTop++] = s ;
int temp = g_pRoom[s.y][s.x] ;
g_pRoom[s.y][s.x] = 0;
Dateback( s ) ;
nTop-- ;
g_pRoom[s.y][s.x] = temp ;
Apple -= g_pRoom[s.y][s.x] ;
}
}
}
}
int main()
{
ifstream file("data.txt") ;
Read_data(file) ;
Dateback( g_pStart ) ;
cout<<g_nMax ;
cout<<"("<<g_pStart.y<<","<<g_pStart.x<<")"<<" " ;
for( int i = 0 ; i < g_nCount ; i++ )
cout<<"("<<g_pResult[i].y<<","<<g_pResult[i].x<<")"<<" " ;
return 0 ;
}
❼ 请问什么是回溯算法
回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
❽ c语言 迷宫问题
第一个我会
srand((int)time(0));
for(i=0;i<N;i++)
for(j=0;j<=N;j++)
{
a[j][i]=rand()/((32767-1)/2);
}
需要带个time.h的头文件
#include<stdio.h>
#include<stdlib.h>
#define n1 10
#define n2 10
typedef struct node
{
int x; //存x坐标
int y; //存Y坐标
int c; //存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右
}linkstack;
linkstack top[100];
//迷宫矩阵
int maze[n1][n2]={1,1,1,1,1,1,1,1,1,1,
0,0,0,1,0,0,0,1,0,1,
1,1,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,0,
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 i,j,k,m=0;
main()
{
//初始化top[],置所有方向数为左
for(i=0;i<n1*n2;i++)
{
top[i].c=1;
}
printf("the maze is:\n");
//打印原始迷宫矩阵
for(i=0;i<n1;i++)
{
for(j=0;j<n2;j++)
printf(maze[i][j]?"* ":" ");
printf("\n");
}
i=0;top[i].x=1;top[i].y=0;
maze[1][0]=2;
/*回溯算法*/
do
{
if(top[i].c<5) //还可以向前试探
{
if(top[i].x==5 && top[i].y==9) //已找到一个组合
{
//打印路径
printf("The way %d is:\n",m++);
for(j=0;j<=i;j++)
{
printf("(%d,%d)-->",top[j].x,top[j].y);
}
printf("\n");
//打印选出路径的迷宫
for(j=0;j<n1;j++)
{
for(k=0;k<n2;k++)
{
if(maze[j][k]==0) printf(" ");
else if(maze[j][k]==2) printf("O ");
else printf("* ");
}
printf("\n");
}
maze[top[i].x][top[i].y]=0;
top[i].c = 1;
i--;
top[i].c += 1;
continue;
}
switch (top[i].c) //向前试探
{
case 1:
{
if(maze[top[i].x][top[i].y+1]==0)
{
i++;
top[i].x=top[i-1].x;
top[i].y=top[i-1].y+1;
maze[top[i].x][top[i].y]=2;
}
else
{
top[i].c += 1;
}
break;
}
case 2:
{
if(maze[top[i].x-1][top[i].y]==0)
{
i++;
top[i].x=top[i-1].x-1;
top[i].y=top[i-1].y;
maze[top[i].x][top[i].y]=2;
}
else
{
top[i].c += 1;
}
break;
}
case 3:
{
if(maze[top[i].x][top[i].y-1]==0)
{
i++;
top[i].x=top[i-1].x;
top[i].y=top[i-1].y-1;
maze[top[i].x][top[i].y]=2;
}
else
{
top[i].c += 1;
}
break;
}
case 4:
{
if(maze[top[i].x+1][top[i].y]==0)
{
i++;
top[i].x=top[i-1].x+1;
top[i].y=top[i-1].y;
maze[top[i].x][top[i].y]=2;
}
else
{
top[i].c += 1;
}
break;
}
}
}
else //回溯
{
if(i==0) return; //已找完所有解
maze[top[i].x][top[i].y]=0;
top[i].c = 1;
i--;
top[i].c += 1;
}
}while(1);
}
你两个程序合并一下就行了
❾ 迷宫算法 上下左右 优先级问题
迷宫一般采用递归算法，而且出口位置在算法开始时候是不知道的吧。而且迷宫的出口也不会固定到哪一个方向。如果采用枚举方法一般是按顺时针或者逆时针找，这样才可以用循环来做，如果采用优先，只能将每个方向定位，设一个常量，那样的话每次递归都要判断一下，非常麻烦，估计还比不用优先还慢一些。