回溯法

回溯的基本原理

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间的任意一个节点时，先判断该节点是否包含问题的解。如果确定不包含，跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

回溯法解问题的所有解时，必须回溯到根节点，且根节点的所有子树都被搜索后才结束。

回溯法解问题的一个解时，只要搜索到问题的一个解就可结束。

回溯的基本步骤

定义问题的解空间(我理解的解空间就是目标问题的内容，或者说是目标问题解的集合。)
确定易于搜索的解空间结构
以深度优先搜索的策略搜索解空间，并在搜索过程中尽可能避免无效搜索

例题

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

A B T G

C F C S

J D E H

代码实现

#include<iostream>
using namespace std;

//探测下一个字符是否存在
bool hasPathCore(const char* matirix,int rows,int cols,
    int row,int col, const char* str,int& pathLength,bool* visited)
{   
    //已经到达字符串结束符,说明前面已经判断完成
    if (str[pathLength] == '\0')
    {
        return true;
    }

    bool haspath = 0;

    //判断当前该点是否合法
    //在矩阵内 & 是指定内容(内容) & 没被访问过
    if (row >= 0 && row < rows && col >= 0 
        && col < cols && matirix[row * cols + col ]== str[pathLength]  
        && !visited[row * cols + col])
    {
        //进入到这里说明当前位置的字符串符合目标str的第几个，判断下一个是否也符合
        //str索引++
        pathLength++;
        //当前结点设置被访问过
        visited[row * col + col] = 1;       
        //递归实现

        /*      
        就是说，选择了一个点，如果周围的周围的周围.......符合，
        也就是说着条路能走通，会一路到return true(str结尾——str[pathLength] == '\0'),
        然后逐层通过return haspath(1)返回到调用处，
        最后再return haspath(1),回到一开始调用该函数的位置，即hasPath中的调用处，
        成功找到路径。
        */

        //向四周判断
        //看有没有符合的点
        haspath = hasPathCore(matirix, rows, cols, row, col - 1, str, pathLength, visited)
            || hasPathCore(matirix, rows, cols, row - 1, col, str, pathLength, visited)
            || hasPathCore(matirix, rows, cols, row, col + 1, str, pathLength, visited)
            || hasPathCore(matirix, rows, cols, row + 1, col, str, pathLength, visited);
        //有一个符合条件即可
        if (!haspath)//如果一个符合的点都没有
        {
            --pathLength;//str索引回退，
            visited[row * cols * +col] = 0;//当前结点周围走不通，标记为未访问，判断其他(方向)的点。
        }
    }
    return haspath;
}

//主体实现流程
bool hasPath(const char* matirix,int rows,int cols,const char* str)
{
    //参数错误
    if (!matirix || rows <= 0 || cols <= 0 || !str)
    {
        return false;
    }
    //bool值矩阵，大小同给定的字符矩阵，标记该位置是否走过
    bool* visited = new bool[cols * rows];
    memset(visited, 0, cols * rows);//初始化为0，未访问过

    int pathLength = 0;

    //遍历矩阵中的每一个点，分别从该点开始出发，判断路径
    for (int row = 0; row < rows; row++)
    {
        for (int col = 0; col < cols; col++)
        {
            if (hasPathCore(matirix, rows,cols, row, col, str, pathLength, visited))
            {
                return true;
            }
        }
    }   
    delete[] visited;
    return false;
}

//通用单元测试代码(便于多种情况测试)
void Test(const char* TestTitle, const char* dest,const char* str,int rows, int cols, bool HopeResult)
{
    cout << "预计结果为" << HopeResult << " ";
    if (hasPath(dest, rows, cols, str) == HopeResult)
    {
        cout << TestTitle << "与预计结果相同" << endl;
    }
    else
    {
        cout << TestTitle << "与预计结果不同" <<  endl;
    }
}
int main(void)
{
    /*
        "ABTG
         CFCS
         JDEH";
    */
    const char* TestTitle = "测试1";
    const char* dest = "ABTGCFCSJDEH";
    const char* str = "BFCEH";
    Test(TestTitle, dest, str, 3, 4, 1);
    return 0;
}

小结

我理解的回溯法就是深度优先搜索的应用，深度优先搜索就是，一个问题的解决路径有多个岔路口，选择其中的一个一直走到底，找到最终解就return true,不行就回退，判断下一个岔路口，直到找到解，否则一直找不到就return了false。

而广度优先算法就是，同时选择多个岔路口，从一边开始，逐层判断，它们是否能够走通(找到解)。

以起点开始辐射式的开始遍历(逐层)。感谢这位up主的分享——相关视频。

目录CONTENT

【算法】回溯法

回溯法

评论区