跳转至

4.3 回溯法

回溯法可以看作是暴力法的升级版,它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案,回溯法非常适合由多个步骤组成的问题,并且每个步骤都有多个选项。

当我们在某一步选择了其中一个选项时,就进入下一步,然后又面临新的选项,我们就这重复选择,直到最终的状态。

用回溯法解决问题的所有选项可以形象地用树状结构表示。 在某一步有n个可能的选项,那么该步骤可以看成是树状结构中的一个节点,每个选项看成树中节点连接线,经过这些连接线到达该节点的n个子节点。 树的叶节点对应着最终状态,如果在叶节点的状态满足题目的约束条件,那么我们找到了一个可行的解决方案。

如果在叶节点的状态不满足约束条件,那么只好回溯到它的上一个节点再尝试其他的选项,如果上一个节点所有可能的选项都已经试过,并且不能到达满足约束条件的终结状态,则再次回溯到上一个节点,如果所有节点的所有选项都已经尝试过仍然不能到达满足约束条件的终结状态,则该问题无解。

以面试题12为例,分析用回溯法解决问题的过程

面试题12: 矩阵中的路径

Question

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。 路径可以从矩阵的任意一格开始,每一步都可以在矩阵中向左,右,上,下移动一格,

如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。 例如,在下面的 3x4 的矩阵中包含一条字符串 "bfce" 的路径,但矩阵中不包含 "abfb" 的路径,

因为字符串的第一个字符b占据了矩阵中的第一行第二个格子后,路径不能再次进入这个格子。

Tip

这是一个可以用回溯法解决问题的典型题,首先,在矩阵中任选一个格子作为路径的起点,假设矩阵中某个格子的字符为ch,并且这个格子将对应于路径上的第i个字符,如果路径上的第i个字符不是ch,那么这个格子不可能处在路径上的第i个位置。 如果路径上的第i个字符正好是ch,那么到相邻的格子寻找路径上的第 i+1 个字符。 除矩阵边界上的格子之外,其他格子都有4个相邻的格子,重复这个过程,直到路径上的所有字符都在矩阵中找到相应的位置。

由于回溯法的递归特性,路径可以被看成一个栈,当在矩阵中定位了路径中的前n个字符之后,再与第n个字符对应的格子的周围都没有找到第n+1个字符,这时候只好在路径上回到第 n-1 个字符,重新定位第 n 个字符。

由于路径不能重复进入矩阵的格子,所以还需要定义和字符矩阵大小一样的布尔值矩阵,用来标识路径是否已经进入了这个格子。

Answer

完整的代码: 矩阵中的路径

测试用例

  • 功能测试,在多行多列的矩阵中输入存在或不存的路径
  • 边界值测试,矩阵中只有一行一列, 矩阵中所有字母都相同
  • 特殊输入,输入空指针

本题考点

  • 考查应聘者对回溯法的理解,通常在二维矩阵上找路径这类问题都可以应用回溯法解决
  • 考查应聘者对数组的编程能力,我们一般都把矩阵看成一个二维数组,只有对数组的特性充分了解,才有可能快速,正确的实现回溯法的代码

面试题13: 机器人的运动范围

Question

地上有一个 m 行 n 列的方格。 一个机器人从坐标(0, 0) 的格子开始移动,它每次可以向左,右,上,下移动一格,但不能进入坐标和列坐标的数位之和大于k的格子; 例如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18, 但它不能进入方格(35, 38), 因为3+5+3+8=19,请问该机器人能够到达多少个格子?

Tip

和前面的题目类似,这个方格可以看成一个m*n的矩阵,同样,在这个矩阵中,除边界上的格子之外,其他格子都有4个相邻的格子。 机器人从坐标开始移动,当它准备进入坐标(i, j)的格子时,通过检查坐标的数位和来判断机器人是否能够进入。 如果机器人能够进入坐标(i, j) 的格子,则再继续判断它周围的四个格子,因此,我们可以用如下的代码来回溯。

Answer

bool pointLessK(int r, int c, int k)
{
    if (r < 0 || c < 0)
        return false;

    if (k < 0)
        return true;

    while (r > 0)
    {
        k -= (r % 10);
        r /= 10;
    }
    if (k < 0)
        return false;

    while (c > 0)
    {
        k -= (c % 10);
        c /= 10;
    }

    if (k < 0)
        return false;
    return true;
}

int RobotActionRangeCore(const int k, int* matrix, const int row, const int col, int r, int c, int* visited)
{
    int count = 0;
    if (r >= 0 && r < row && c >= 0 && c < col
        && visited[r * col + c] == 0 && pointLessK(r, c, k)
        )
    {
        count++;
        visited[r * col + c] = 1;

        // 上下左右四个方向能走到则一直递归
        count = count + RobotActionRangeCore(k, matrix, row, col, r-1, c, visited)
            + RobotActionRangeCore(k, matrix, row, col, r, c+1, visited)
            + RobotActionRangeCore(k, matrix, row, col, r+1, c, visited)
            + RobotActionRangeCore(k, matrix, row, col, r, c-1, visited);
    }
    return count;
}

int getRobotActionRange(int k, int* matrix, int row, int col)
{
    if (matrix == nullptr || row < 1 || col < 1)
        throw exception("InValid Params");

    int* visited = new int[row * col];
    memset(visited, 0, row * col * sizeof(int));
    int count = RobotActionRangeCore(k, matrix, row, col, 0, 0, visited);
    delete[] visited;
    return count;
}

完整代码: 机器人移动范围

测试用例

  • 功能测试,多行多列,k位正数
  • 边界值测试,只有一行,或只有一列,k 等于0
  • 特殊输入测试,k为负数

本题考点

  • 对回溯法的理解,通常物体或者人在二维方格运动这类的问题都可以用回溯法解决
  • 数组编程能力的考查