回溯法：算法思路以及相关流程图的绘制

本文主要是介绍回溯法：算法思路以及相关流程图的绘制，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

参考建模原文
2020国赛B题
参考文章1

回溯法介绍

深度优先搜索（缩写DFS）:
对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

回溯法:
把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

回溯法在编程中主要通过递归来实现。

回溯法解决迷宫问题

下图中,左上角为迷宫起点,右下角为迷宫终点。

编程思路

(以c#语言为例,其他语言相似)

初始化需要设置的相关参数:

public Stack<Point> path = new Stack<Point>(); //一条找到的路径
public Stack<Point> bestPath = new Stack<Point>(); //最优路径

其中 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;         //设置为未走
}

这篇关于回溯法：算法思路以及相关流程图的绘制的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！