迷宮演算法回溯
❶ 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);
}
你兩個程序合並一下就行了
❾ 迷宮演算法 上下左右 優先順序問題
迷宮一般採用遞歸演算法，而且出口位置在演算法開始時候是不知道的吧。而且迷宮的出口也不會固定到哪一個方向。如果採用枚舉方法一般是按順時針或者逆時針找，這樣才可以用循環來做，如果採用優先，只能將每個方向定位，設一個常量，那樣的話每次遞歸都要判斷一下，非常麻煩，估計還比不用優先還慢一些。