首页 > 代码库 > C程序设计的抽象思维-回溯算法-迷宫问题
C程序设计的抽象思维-回溯算法-迷宫问题
【迷宫问题】
两种方法：1. 堆栈回溯，2.递归回溯。
【算法1---堆栈回溯】
计算机解迷宫时，通常用的是"试探和回溯"的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。
1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；
2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；
3．所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。
由此，求迷宫中一条路径的算法的基本思想是：
若当前位置"可通"，则纳入"当前路径"，并继续朝"下一位置"探索；若当前位置"不可通"，则应顺着"来的方向"退回到"前一通道块"，然后朝着除"来向"之外的其他方向继续探索；若该通道块的四周四个方块均"不可通"，则应从"当前路径"上删除该通道块。
设定当前位置的初值为入口位置；
do{
若当前位置可通，
则{
将当前位置插入栈顶； // 纳入路径
若该位置是出口位置，则算法结束；
// 此时栈中存放的是一条从入口位置到出口位置的路径
否则切换当前位置的东邻方块为新的当前位置；
}
否则
{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则{ 删去栈顶位置； // 从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
} while (栈不空)；
【算法1代码(转)】
#include <stdio.h>
#define WALL 0 //墙
#define CORRIDOR 1 //通道
#define PATH 9 //为路径上的一块
#define TRIED 2 //
#define ROW_NUM 7 //迷宫数组行数
#define COL_NUM 13 //列数
#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
typedef struct
{
int row;
int col;
}PosType;
typedef struct
{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的坐标
int di; //当前通道块的方向
}SElemType;
typedef struct
{
SElemType S[MAXSIZE];
int top;
}MazeType;
//迷宫
int grid[ROW_NUM][COL_NUM]={{1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
//当前位置是否可以通过
bool Valid(PosType pos)
{
if(pos.row>=0&&pos.row<=ROW_NUM&&pos.col>=0&&pos.col<=COL_NUM&&grid[pos.row][pos.col]==CORRIDOR)
return TRUE;
else
return FALSE;
}
void FootPrint(PosType pos)//留下足迹
{
grid[pos.row][pos.col]=PATH;
}
void Undo(PosType pos) //留下不能通过的标识
{
grid[pos.row][pos.col]=TRIED;
}
//当前位置的下一个位置
PosType NextPos(PosType cur,int di)
{
PosType next;
switch(di)
{
case 0: //东
next.row=cur.row;
next.col=cur.col+1;
break;
case 1: //南
next.row=cur.row+1;
next.col=cur.col;
break;
case 2: //西
next.row=cur.row;
next.col=cur.col-1;
break;
case 3: //北
next.row=cur.row-1;
next.col=cur.col;
break;
}
return next;
}
//是否到达终点
bool Done(PosType cur,PosType end)
{
if(cur.row==end.row&&cur.col==end.col)
return TRUE;
else
return FALSE;
}
//寻找迷宫路径
bool MazePath(MazeType &path,PosType start,PosType end)
{
SElemType e;
path.top=-1;
int step=1;
PosType curpos=start;
do
{
if(Valid(curpos))
{
FootPrint(curpos);
e.ord=step;
e.di=0;
e.seat=curpos;
path.S[++path.top]=e;
if(Done(curpos,end))
return TRUE;
curpos=NextPos(curpos,0);
step++;
}
else
{
if(path.top>-1)//棧不空
{
e=path.S[path.top--];
while(e.di==3&&path.top>-1)
{
Undo(e.seat);
e=path.S[path.top--];
}
if(e.di<3)
{
e.di++;
path.S[++path.top]=e;
curpos=NextPos(e.seat,e.di);
}
}//if
}//else
}while(path.top>-1);
return FALSE;
}
//输出路径
void PrintPath(MazeType path)
{
int i=0;
while(i<=path.top)
{
printf("第%d步:(%d,%d)\n",path.S[i].ord,path.S[i].seat.row,path.S[i].seat.col);
i++;
}
}
//输出路径
void PrintPath2()
{
for(int i=0;i<ROW_NUM;i++)
for(int j=0;j<COL_NUM;j++)
if(grid[i][j]==PATH)
printf("(%d,%d)\n",i,j);
}
int main()
{
MazeType path;
PosType start={0,0},end={6,12};
if(MazePath(path,start,end))
PrintPath(path);
else
printf("not reachable!\n");
PrintPath2();
}【算法2--递归回溯】
利用迷宫地图数据来保存路径信息，相对压栈方法节省内存。前提是迷宫地图数据必须是可写的。
【算法2代码】
#include <stdio.h>
#include <stdlib.h>
#define ROW_NUM 7
#define COL_NUM 13
#define WALL 0 //墙
#define CORRIDOR 1 //通道
#define PATH 2 //已经走过的路径位置
typedef struct{
int x;
int y;
}pointT;//坐标
typedef enum {North, East, South, West} directionT; //方向
typedef enum {false, true} bool;
int grid[ROW_NUM][COL_NUM]={{1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}};//迷宫
pointT startpt = {0, 0}; //入口
pointT endpt = {6, 12}; //出口
static bool OutsideMaze(pointT pt) //判断是否到达出口
{
if(pt.x == endpt.x && pt.y == endpt.y)
return true;
return false;
}
static void MarkSquare(pointT pt) //标记走过的位置
{
grid[pt.x][pt.y] = PATH;
}
static void UnmarkSquare(pointT pt) //清除标记
{
grid[pt.x][pt.y] = CORRIDOR;
}
static bool CorridorExits(pointT pt, directionT dir) //前进方向是否为通道
{
switch(dir){
case North :
if(grid[pt.x][pt.y - 1] == CORRIDOR && pt.y > 0)
return true;
break;
case East :
if(grid[pt.x + 1][pt.y] == CORRIDOR && pt.x < ROW_NUM - 1)
return true;
break;
case South :
if(grid[pt.x][pt.y + 1] == CORRIDOR && pt.y < COL_NUM - 1)
return true;
break;
case West :
if(grid[pt.x - 1][pt.y] == CORRIDOR && pt.x > 0)
return true;
break;
}
return false;
}
static pointT AdjacentPoint(pointT pt, directionT dir) //前进的位置
{
pointT newpt;
newpt = pt;
switch(dir){
case North: newpt.y--; break;
case East: newpt.x++; break;
case South: newpt.y++; break;
case West: newpt.x--; break;
}
return (newpt);
}
static bool SolveMaze(pointT pt) //解决迷宫函数
{
directionT dir;
if(OutsideMaze(pt))
{
MarkSquare(pt);
return true;
}
MarkSquare(pt);
for(dir = North; dir <= West; dir++){
if(CorridorExits(pt, dir)){
if(SolveMaze(AdjacentPoint(pt, dir))){
return true;
}
}
}
UnmarkSquare(pt);
return false;
}
static void printPath() //打印
{
int i, j;
for(i = 0; i < ROW_NUM; i++){
for(j =0; j < COL_NUM; j++)
printf("%d ", grid[i][j]);
printf("\n");
}
}
int main()
{
SolveMaze(startpt);
printPath();
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。