回溯法介绍
深度优先搜索（缩写DFS）:
对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
回溯法:
把问题的解空间转化成了 图或者 树的结构表示，然后使用 深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
回溯法在编程中主要通过 递归来实现。
回溯法解决迷宫问题
下图中,左上角为迷宫起点,右下角为迷宫终点。
编程思路
(以c#语言为例,其他语言相似)
初始化需要设置的相关参数:
public Stack path = new Stack(); //一条找到的路径
public Stack bestPath = new Stack(); //最优路径
其中 bestPath 为最优路径结果, 而 path 为递归过程中存储路径的堆栈,是一个不断在变化与更新的量。
主要递归函数如下（程序主要展现思路）:
private void MazeTrack(int x, int y)
{
Point p = new Point(x, y);
path.Push(p);
mazeData[x, y] = 3;
//如果该位置是出口，输出结果
if (x == exitX && y == exitY)
{
//判断是否更优
if (bFrist)
{
//如果是找到的第一条路径，直接复制到最优路径
}
else
{
//不是第一条，则判断是否更短
//更短，复制到最优路径
}
}
//判断(x,y)位置的上、下、左、右是否可走
if ((x - 1) >= 0 && mazeData[x - 1, y] == 0)//上(x-1,y)；存在且可走
{
MazeTrack(x - 1, y);
}
if ((x + 1) < mazeHeight && mazeData[x + 1, y] == 0)//下(x+1,y)；存在且可走
{
MazeTrack(x + 1, y);
}
if ((y - 1) >= 0 && mazeData[x, y - 1] == 0)//左(x,y-1)；存在且可走
{
MazeTrack(x, y - 1);
}
if ((y + 1) < mazeWidth && mazeData[x, y + 1] == 0)//右(x,y+1)；存在且可走
{
MazeTrack(x, y + 1);
}
//上下左右均无法移动,则结束本层递归,返回上一节点
path.Pop();
mazeData[x, y] = 0; //设置为未走
}
Original: https://www.cnblogs.com/litecdows/p/16549010.html
Author: litecdows
Title: 回溯法：算法思路以及相关流程图的绘制
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/610462/
转载文章受原作者版权保护。转载请注明原作者出处！