解决迷宫问题（曲折游戏）
4.60/5 (8投票s)
本文使用启发式搜索解决了迷宫问题。
引言
人工智能的一个问题是解决曲折游戏（迷宫）。它定义了必须以各种方式解决的状态空间。为了解决这个问题并解释游戏规则，我将解释解决方案。
问题规则
- 这个游戏可以定义在一个有限的空间内，其中一个空间用于主棋盘。
- 在本文中，我们考虑 N*N 数组的棋盘。
- 棋盘的行和列被视为围绕棋盘的行和列。
- 棋盘只能从起点到终点有唯一一条路径。
- 只允许向前和向下移动。
- 必须考虑一个起点。
- 考虑一条从起点到终点的路径。
- 在此算法中不允许返回路径。
- 在每种情况下，只允许两种移动中的一种。
- 允许显示输出的行和列是所经过的路径。
算法问题求解
- 在此算法中，将首先检查第一行和下一列。
- 如果没有，则根据行和列的数量将它们添加到堆栈中。
- 如果行已关闭，则检查列。
- 如果路径已关闭，则此棋盘游戏设计未满足且有误。因此没有解决方案。
- 如果路径已打开，则当前行和列将存储在堆栈中，算法将检查第一层。
- 每一次重复都会检查算法的整个过程。
- 输出存储在堆栈中显示。
在此方法中，使用广度优先搜索（BFS）来遍历路线。由于问题的性质，该算法是信息化的。伪代码解决方案如下
Do
If next row is 0 add row
Else
If next column is 0 add column
Else
If row and col is final element Return true
Else
Return not solve
提供了求解曲折路径的算法。该算法是最简单的算法之一，可确保是否存在任何输出。在算法的后期阶段，将返回已提出的一些问题。要找到最短路径，算法也可以提出。
该算法基于本文中提出的所有问题。程序流程图已呈现。
代码分析
它由两层组成
- 表示层
- 业务层
大多数订单都在输出层中传递。为了遵守规则，已经创建了一个单一的业务对象层（抽象）。程序用于跟踪已创建的堆栈数据结构。规则也充分遵循了从用户角度隐藏数据的要求。为了访问数组的单个元素，使用了访问器（accessor）。
项目定义并定义了一个名为 Mazebusiness 的类。以下代码定义了堆栈所需的变量。行和列的维护变量被定义为每个堆栈的顶部。主范围存储数组也已定义。
//stack size
int SIZE = 20;
//max row and column
int max = 6;
//min row and column
int min = 0;
// int array stack row
int[] stack1 = new int[20];
//int array stack column
int[] stack2 = new int[20];
// int top of stacks and keep value col and row
int tos1, tos2, col, row;
// main board array
int[,] array = new int[6, 6];
构造函数
此类在构造函数中为棋盘定义了初始值零。稍后使用另一个方法来定义元素以获得期望的结果。两个数组的值都保持堆栈为零。每个堆栈的高度也为零。行和列定义为零。
//constructor
// put zero in all element of main array
// set zero in stacks
//set zero top of stacks and row and column
public MazeBusiness()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
array[i, j] = 0;
for (int i = 0; i <= SIZE - 1; i++)
{
stack1[i] = 0;
stack2[i] = 0;
}
tos1 = 0;
tos2 = 0;
col = 0;
row = 0;
}
CreateBoard()
元素函数不改变主路径。此路径可以轻松检测。
//initialize main board array
//at first set 1 around board
//set board by default values
public void CreateBoard()
{
for (int i = 0; i < 5; i++)
{
array[0, i] = 1;
array[i, 0] = 1;
array[5, i] = 1;
array[i, 5] = 1;
}
//set 1 , 2..5 element to 1
for (int i = 2; i < 5; i++)
array[1, i] = 1;
//set 2 , 2..5 element to 1
for (int i = 2; i < 5; i++)
array[2, i] = 1;
//set 4 , 2..5 element to 1
for (int i = 1; i < 4; i++)
array[4, i] = 1;
}
PrintBoard()
此函数显示原始数组。输出是原始数组的函数，用于显示表示层。
//return print able board at string
public string PrintBoard()
{
string Temp = string.Empty;
for (int i = 1; i < 5; i++)
{
for (int j = 1; j < 5; j++)
Temp += " " + array[i, j];
Temp += "\r\n";
}
return Temp;
}
Pushr()
此函数接收一个数值输入，并将值存储在保存行的堆栈中。
//push cha in row stack
public void pushr(int cha)
{
if (tos1 == SIZE)
{
return;
}
stack1[tos1] = cha;
tos1++;
}
popr()
此函数返回存储在行堆栈中的值。
//pop from row stack
public int popr()
{
if (tos1 == 0)
{
return -1;
}
tos1--;
return stack1[tos1];
}
Pushc()
此函数接收一个数值，并将获得的值存储在保存列的堆栈中。
//push cha in column stack
public void pushc(int chb)
{
if (tos2 == SIZE)
{
return;
}
stack2[tos2] = chb;
tos2++;
}
popc()
此函数返回存储在行堆栈中的值。
//pop from column stack
public int popc()
{
if (tos2 == 0)
{
return -1;
}
tos2--;
return stack2[tos2];
}
cpopr()
此函数返回堆栈中的第一行。
//return top of row stack
public int cpopr()
{
return stack1[tos1];
}
cpopc()
此函数返回堆栈中的第一列。
//return top of column stack
public int cpopc()
{
return stack2[tos2];
}
set()
该函数将行和列数组初始化为起点。
//initialize 1,1 for start
public void set()
{
row = 1;
col = 1;
pushr(row);
pushc(col);
}
Addr()
此函数增加行值。
// add row pointer
public void addr()
{
row++;
}
Addc()
此函数增加列值。
//add column pointer
public void addc()
{
col++;
}
minr()
此函数减少行值。
// reduce row value
public void minr()
{
row--;
}
minc()
此函数减少列值。
//reduce column value
public void minc()
{
col--;
}
checker()
此函数检查下一行的值。如果值为零，则存在路径。主棋盘的边行和列也远小于此。
// check next row element is 0?
public int checkar()
{
int a = 0;
a = row;
a++;
if ((array[a, col] == 0) && (a < max))
return 1;
else
return 0;
}
checkac()
此函数检查下一列。如果值为零，则存在路径。它也应该远小于主棋盘的行和列边界。
// check next column element is 0?
public int checkac()
{
int a = 0;
a = col;
a++;
if ((array[row, a] == 0) && (a < max))
return 1;
else
return 0;
}
retr()
此函数返回行。
//get row value
public int retr()
{
return row;
}
retc()
此函数返回列值。
//get column value
public int retc()
{
return col;
}
printoutput()
此函数将堆栈作为算法遍历的路径返回。
// Print value in stack row and column
public string printOutPut()
{
string Temp = string.Empty;
for (int i = 0; tos1 != 0; i++)
Temp += popr() + " , " + popc() + "\r\n";
return Temp;
}
表示层
此层的行和列在程序中决定了提供合适类型的输出数据表。在第一个示例中，业务对象被创建并在此原型上实现所有操作。变量根据需要定义。
调用 CreateBoard() 和 set() 方法来设置主棋盘的行数和列数。创建了两个变量来跟踪进出标志的移动。
//create instance
MazeBusiness maze = new MazeBusiness();
//create default board
// we can change value of this method for change maze way.
maze.CreateBoard();
//print board
lblOutPut3.Text = maze.PrintBoard();
//initialize pointer
maze.set();
//define flag and move counter
int exit = 0, counter = 0;
在下一部分中，使用 while-do 循环来遍历路线。在此循环中，根据第一篇文章中陈述的要求，检查是否存在路径。继续将行和列压入堆栈，并在路径不合适时显示消息。
//Each time a row and the column was closed and had reached the end of the array
//output is displayed
//check next row.
//check next column.
//if true add to stack.
// else return no slution.
do
{
counter++;
//check next row
if (maze.checkar() == 1)
{
maze.addr();
maze.pushr(maze.retr());
maze.pushc(maze.retc());
}
else
//check next column
if (maze.checkac() == 1)
{
maze.addc();
maze.pushr(maze.retr());
maze.pushc(maze.retc());
}
else
//check end of array?
if (maze.retr() == 4 && maze.retc() == 4)
{
exit = 1;
lblIsSolution.Text = "Resolved";
}
else
{
exit = 1;
lblIsSolution.Text = "Not resolved";
}
//while() check end of array and exit flag
} while (maze.retr() != 5 && maze.retc() != 5 && exit == 0);
//print stacks value. the way of maze
lblOutPut.Text = maze.printOutPut();
//display count maze movement
lblOutPut2.Text = counter.ToString();
最后显示所经过路径的输出。此外，还可以显示运动方向是否已解决以及路线是否已解决。输出如下图所示
