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


参考建模原文
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;         //设置为未走
}

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

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/278822.html

(0)
上一篇 2022年8月4日
下一篇 2022年8月4日

相关推荐

发表回复

登录后才能评论