回溯法

发表于 | 更新于: | 分类于 | 热度: ℃
字数统计: 1,984 | 阅读时长 ≈ 9

回溯法

回溯法可以看成蛮力法的升级版，主要是在搜索过程中寻找问题的解，当发现已经不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步进行选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法过程：

  • 针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
  • 确定结点的扩展搜索规则。
  • 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

面试题：矩阵中的路径

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

A B T G
C F C S
J D E H

思路：由于矩阵的第一行第二个字母’b’的路径’bfce’的第一个字符相等，我们就从这里开始分析。根据题目要求，我们此时有3个选项，分别是向左边到达字母’a’,向右边到达字母’t’，向下到达字母’f’。我们先尝试选项’a’,由于此时不能得到路径’bfce’，因此不得不回到结点’b’尝试下一个选项’t’，同样，经过结点也不能得到路径’bfce’，因此再次回到结点’b’尝试下一个选项’f’。

在结点’f’我们也有三个选项，向左右都能到达’c’，向下到达子字母‘d’。我们先选择向左到达字母’c’,由于只有一个选择，即向下到达字母’j’。但是无法到达路径’bfce’，我们只好回溯到上一个结点’f’尝试下一个选项，即向右到达结点’c’。

根据这个规则，一直寻找，知道满足约束条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <stdio.h>
#include<string.h>
#include <stack>
using namespace std;
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,
                 const char* str, int& pathLength, bool *visited);
bool hasPath(const char* matrix, int rows, int cols, const char* str)
{
    if(matrix == nullptr || rows<1 || cols<1 || str == nullptr)
        return false;
    bool *visited = new bool[rows * cols];
    memset(visited, 0, rows*cols);
    int pathLength = 0;
    for(int row=0; row<rows; ++row)
    {
        for(int col=0; col<cols; ++col)
        {
            if(hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited))
            {
                return true;
            }
        }
    }
    delete[] visited;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,
                 const char* str, int& pathLength, bool *visited)
{
    if(str[pathLength] == '\0')
        return true;
    bool hasPath = false;
    if(row>=0 && row<rows && col>=0 && col<cols && matrix[row*cols+col] == str[pathLength] && !visited[row*cols+col])
    {
        ++pathLength;
        visited[row*cols+col] = true;
        hasPath = hasPathCore(matrix, rows, cols, row, col-1,
                str, pathLength, visited)
                ||hasPathCore(matrix, rows, cols, row, col+1,
                str, pathLength, visited)
                ||hasPathCore(matrix, rows, cols, row-1, col,
                str, pathLength, visited)
                ||hasPathCore(matrix, rows, cols, row+1, col,
                str, pathLength, visited);
        if(!hasPath)
        {
            --pathLength;
            visited[row*cols+col] = false;
        }
    }
    return hasPath;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//===============测试代码=============
void Test(const char* testName, const char* matrix, int rows, int cols, const char* str, bool expected)
{
    if(testName != nullptr)
        printf("%s begins: ", testName);
    if(hasPath(matrix, rows, cols, str) == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}
//ABTG
//CFCS
//JDEH
//BFCE
void Test1()
{
    const char* matrix = "ABTGCFCSJDEH";
    const char* str = "BFCE";
    Test("Test1", matrix, 3, 4, str, true);
}
//ABCE
//SFCS
//ADEE
//SEE
void Test2()
{
    const char* matrix = "ABCESFCSADEE";
    const char* str = "SEE";
    Test("Test2", matrix, 3, 4, str, true);
}
//AAAA
//AAAA
//AAAA
//AAAAAAAAAAAA
void Test3()
{
    const char* matrix = "AAAAAAAAAAAA";
    const char* str = "AAAAAAAAAAAA";
    Test("Test3", (const char*) matrix, 3, 4, str, true);
}
//ABCE
//SFCS
//ADEE
//SEE
void Test4()
{
    const char* matrix = "ABCESFCSADEE";
    const char* str = "ABFB";
    Test("Test4", matrix, 3, 4, str, false);
}
int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    return 0;
}

面试题：机器人的运动范围

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

思路：和上一道题类似，这个方格也可以看做是一个m*n的矩阵。同样在这个矩阵中，除了边界上的格子外，其他格子都有四个相邻的格子。机器人的坐标从(0,0)开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的位数来判断机器人能否进入。如果机器人能够进入坐标为(i, j)的格子，则再判断他能否进入4个相邻的格子(i, j-1),(i-1, j). (i, j+1)和(i+1, j)。

1
2
3
4
5
6
7
#include <iostream>
#include <stdio.h>
using namespace std;
int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited);
bool check(int threshold, int rows, int cols, int row, int col, bool* visited);
int getSum(int number);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int movingCount(int threshold, int rows, int cols)
{
    if(threshold<0 || rows<1 || cols<1)
        return false;
    bool* visited = new bool[rows*cols];
    for(int i=0; i<rows*cols; ++i)
        visited[i] = false;
    int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
    delete[] visited;
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited)
{
    int count = 0;
    if(check(threshold, rows, cols, row, col, visited))
    {
        visited[row*cols+col] = true;
        count =1+movingCountCore(threshold, rows, cols,
              row, col-1, visited)
              + movingCountCore(threshold, rows, cols,
              row-1, col, visited)
              + movingCountCore(threshold, rows, cols,
              row, col+1, visited)
              + movingCountCore(threshold, rows, cols,
              row+1, col, visited);
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
bool check(int threshold, int rows, int cols, int row, int col,
    bool* visited)
{
    if(row >= 0 && row < rows && col >= 0 && col < cols
        && getSum(row) + getSum(col) <= threshold
        && !visited[row* cols + col])
        return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
int getSum(int number)
{
    int sum = 0;
    while(number>0)
    {
        sum += number % 10;
        number = number/10;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// ====================测试代码====================
void Test(char* testName, int threshold, int rows, int cols, int excepted)
{
    if(testName != nullptr)
         printf("%s begins: ", testName);
    if(movingCount(threshold, rows, cols) == excepted)
        printf("Test Passed.\n");
    else
        printf("Test Failed.\n");
}
// 方格多行多列
void Test1()
{
    Test("Test1", 5, 10, 10, 21);
}
// 方格多行多列
void Test2()
{
    Test("Test2", 15, 20, 20, 359);
}
// 方格只有一行，机器人只能到达部分方格
void Test3()
{
    Test("Test3", 10, 1, 100, 29);
}
// 方格只有一行，机器人能到达所有方格
void Test4()
{
    Test("Test4", 10, 1, 10, 10);
}
// 方格只有一列，机器人只能到达部分方格
void Test5()
{
    Test("Test5", 15, 100, 1, 79);
}
// 方格只有一列，机器人能到达所有方格
void Test6()
{
    Test("Test6", 15, 10, 1, 10);
}
// 方格只有一行一列
void Test7()
{
    Test("Test7", 15, 1, 1, 1);
}
// 方格只有一行一列
void Test8()
{
    Test("Test8", 0, 1, 1, 1);
}
// 机器人不能进入任意一个方格
void test9()
{
    Test("Test9", -10, 10, 10, 0);
}
int main()
{
    /**
    int threshold, rows, cols;
    cin>>threshold;
    cin>>rows;
    cin>>cols;
    cout<<movingCount(threshold, rows, cols);
    int n;
    cin>>n;
    cout<<getSum(n)<<ends;
    **/
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
    test9();
    return 0;
}
-------------本文结束感谢您的阅读-------------
很有帮助，打赏感谢！
分享到： QQ好友 微信 新浪微博 有道云笔记 豆瓣 收藏夹 复制网址 一键分享 更多
0%