递归回溯法叫称为试探法,按选优条件向前搜索,当搜索到某一步,发现原先选择并不优或达不到目标时,就退回一步重新选择。这里有一个非常经典的例子叫“骑士巡逻问题”,这个例子应该更容易帮助你理解什么是递归回溯法。
所谓“骑士巡逻问题”是指按照国际象棋中骑士(Knight,走法类似于中国象棋中的“马”)的走法,一个骑士从棋盘的某一个格子出发,走遍整个棋盘的每一个方格,而且每个格子只能够经过一次,找出可能的线路和走法。如果骑士从某个格子出发,走完所有格子后最终能回到这个出发的格子,称这种巡逻方式为“封闭式巡逻”,否则称为“开放式巡逻”。国际象棋的棋盘是 \small{8 \times 8} 的方格,一共有26,534,728,821,064种封闭式巡逻,有19,591,828,170,979,904种开放式巡逻。对于下面的缩小为 \small{5 \times 5} 的棋盘,下面的动图给出了骑士的一种巡逻方案。
这里顺便吐槽一下,知乎回答问题时插入图片居然不支持gif,这里只能给一个gif图片的链接,图片来自于维基百科,可能需要科学一下才能看到。
下面用 Python 给出了“骑士巡逻问题”的代码,用其他语言书写本质上也没有什么差别。
SIZE = 5
def show_board(board, totals=[0]):
"""显示棋盘和第几种走法"""
totals[0] += 1
print(f'第{totals[0]}种走法: ')
for row in board:
for col in row:
print(str(col).center(4), end='')
print()
def patrol(board, row=0, col=0, step=1):
"""用递归回溯的方式搜索所有的巡逻方式
:param board: 棋盘(用嵌套列表表示)
:param row: 骑士准备巡逻的位置对应的行
:param col: 骑士准备巡逻的位置对应的列
:param step: 序号(按巡逻的顺序依次标记)
"""
if row >= 0 and row < SIZE and col >= 0 and col < SIZE and board[row][col] == 0:
# 如果row和col都在棋盘范围以内且对应的格子没有巡逻过就标记它
board[row][col] = step
if step == SIZE * SIZE:
# 所有的格子都被标记(一次巡逻完成)就输出棋盘
show_board(board)
# 向下一个格子继续巡逻(国际象棋的骑士可以往八个方向进行)
# 巡逻方向不同row和col的变化就不同,但step都是统一加1
patrol(board, row - 2, col - 1, step + 1)
patrol(board, row - 1, col - 2, step + 1)
patrol(board, row + 1, col - 2, step + 1)
patrol(board, row + 2, col - 1, step + 1)
patrol(board, row + 2, col + 1, step + 1)
patrol(board, row + 1, col + 2, step + 1)
patrol(board, row - 1, col + 2, step + 1)
patrol(board, row - 2, col + 1, step + 1)
# 八个方向都行不通或者所有格子已经巡逻完毕就回到上一步(回溯)
# 回溯时要记得清除之前标记的step,标记为0相当于格子未被巡逻
board[row][col] = 0
def main():
# 初始化棋盘(每个格子都标为0表示没有巡逻过)
board = [[0] * SIZE for _ in range(SIZE)]
patrol(board)
if __name__ == '__main__':
main()
看看上面的代码是否能够帮助你更好的理解递归回溯算法。有一个小建议,给你的代码增加一些断点,然后用调试模式运行代码,通过单步执行并观察你的函数调用栈以及相关变量的值,就能更好的理解整个代码是如何运转起来的。
最后,还是给你一个C++版本的代码,我不确定你写的C还是C++,我也很久没有写过C++的代码了,下面的代码倒是可以运转起来的,但是不知道写得是否精准,你自己甄别吧。
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 5;
void show_board(const vector<vector<int> >& board) {
static int total = 0;
cout << "第" << ++total << "种走法: " << endl;
for (const auto& row : board) {
for (const auto& col : row) {
cout << setw(4) << col;
}
cout << endl;
}
}
void patrol(vector<vector<int> >& board, int row = 0, int col = 0, int step = 1) {
if (row >= 0 && row < SIZE && col >= 0 && col < SIZE && board[row][col] == 0) {
board[row][col] = step;
if (step == SIZE * SIZE) {
show_board(board);
}
patrol(board, row - 2, col - 1, step + 1);
patrol(board, row - 1, col - 2, step + 1);
patrol(board, row + 1, col - 2, step + 1);
patrol(board, row + 2, col - 1, step + 1);
patrol(board, row + 2, col + 1, step + 1);
patrol(board, row + 1, col + 2, step + 1);
patrol(board, row - 1, col + 2, step + 1);
patrol(board, row - 2, col + 1, step + 1);
board[row][col] = 0;
}
}
int main() {
vector<vector<int> > board(SIZE, vector<int>(SIZE, 0));
patrol(board);
return 0;
}
写到这里就顺便吐槽一下C++,用嵌套容器时两个大于号放一起会跟 >> 运算符冲突,原来的解决方案是在两个大于号中间添加一个空格,但这样会让整个代码看起来丑陋无比,就像我上面代码中写的那样,真心不喜欢!我记得从什么时候开始,C++是不是编译的时候加个参数 -std 就可以解决这个问题,具体是怎么操作的我也没啥印象了,如果有大佬知道这个问题的解决方案和背后的道理,也请大家不吝赐,感谢!
编辑于 2024-03-24 11:07・IP 属地四川