算法详解之回溯法具体实现

确定性算法一般都是利用了数据的某些特殊结构，或者特定的规律，因此算法的速度会很快，但是对于一些问题，无法利用这些特殊信息，这时候我们只能用搜索的方式来解决。回溯法就是这样一种搜索方法，它一般用于解决组合和排列问题，主要是枚举出所有可能的解，再判断哪些是符合条件的。以下是回溯法具体实现的攻略。

一、回溯法的概念

回溯法，也叫试探法，是一种有序的、系统的、逐步地搜索答案的方法。适用于问题的解空间庞大，采用穷举法难以解决的情况，又称为“回溯搜索法”或“深度优先搜索法”。

回溯法的基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。可以看做是深度优先搜索的一种特殊情况。

二、回溯法的基本流程

确定问题的解空间；
确定活节点：活节点表示当前问题还没有彻底解决，仍需要进一步搜索的节点；
利用剪枝函数避免无效搜索，即将不能成为正确答案的路径及时删除，只保留有可能搜索到正确答案的活节点；
对活节点进行搜索，若找到解答案，则提取解并停止搜索；若未找到解，则继续往下搜索；
恢复现场，回溯到上一步，对下一个活节点进行搜索；
判断是否已经搜索完所有的节点，如果已经搜索完毕，则结束搜索并输出最终解，否则返回到第三步。

三、回溯法的实现

回溯法大致有两种实现方式：递归和非递归，其中递归实现方式较为容易理解。

1. 递归实现

递归实现回溯法主要包含如下三个步骤：

确定递归边界条件；
枚举解空间，对每个候选解进行验证和剪枝；
对剩余解空间进行递归处理。

以求解n皇后问题为例，代码如下：

void NQueen(int n, int cur) //n表示问题规模，cur表示正在处理哪一行
{
    if(cur > n) //递归边界条件
    {
        PrintSolution(); //输出解
        return;
    }
    for(int i=1; i<=n; i++) //枚举解空间
    {
        if(isValidPos(i, cur)) //验证
        {
            board[cur] = i; //记录解
            NQueen(n, cur+1); //递归处理剩余解空间
            board[cur] = 0; //恢复现场
        }
    }
}

其中isValidPos(i,cur)用于验证当前位置是否为可行解，board表示棋盘，board[cur]表示第cur行皇后的位置。

2. 非递归实现

非递归实现回溯法主要借助栈，以求解迷宫问题为例，代码如下：

void SolveMaze(Point start, Point end)
{
    stack<Point> s; //用栈保存通路
    s.push(start);
    maze[start.x][start.y] = '#'; //将起点标记为已访问
    while(!s.empty())
    {
        Point p = s.top();
        if(p==end)
        {
            PrintPath(s); //输出通路
            return;
        }
        bool found = false;
        for(int i=0; i<4; i++) //枚举解空间
        {
            Point next = p + moves[i];
            if(isValidPos(next) && maze[next.x][next.y]==' ')
            {
                s.push(next); //入栈
                maze[next.x][next.y] = '#'; //标记为已访问
                found = true;
                break;
            }
        }
        if(!found)
        {
            s.pop(); //回溯
        }
    }
}

其中isValidPos和moves是用于验证相邻节点是否可行的函数，PrintPath用于输出通路。maze表示迷宫，'#'表示已经访问过的节点，' '表示未访问过的节点。

四、示例说明

示例1：求解数独

数独是一种数字游戏，要求在一个9×9的宫格中，填入数字1~9，使每行、每列、每个宫格内的数字都不能重复。实现代码如下：

void Sudoku(int cur)
{
    if(cur > 80) //递归边界条件
    {
        PrintSudoku(); //输出答案
        return;
    }
    int row = cur / 9;
    int col = cur % 9;
    if(sudoku[row][col] != 0) //已经有数字的格子不用处理
    {
        Sudoku(cur+1);
        return;
    }
    for(int i=1; i<=9; i++)
    {
        if(isValidNumber(row, col, i)) //验证是否为可行解
        {
            sudoku[row][col] = i; //记录解
            Sudoku(cur+1); //递归
            sudoku[row][col] = 0; //恢复现场
        }
    }
}

其中isValidNumber用于验证当前位置是否可以填入数字i。

示例2：解数独

同样是数独问题，但是无法通过backtracking回溯法求解。解决方法是同时采用backtracking和广度优先搜索，实现代码如下：

bool SolveSudoku()
{
    queue<Board> q;
    q.push(sudoku);
    while(!q.empty())
    {
        Board board = q.front();
        q.pop();
        int r, c;
        if(FindUnassignedLocation(board, r, c)) //查找待处理位置
        {
            for(int num=1; num<=9; num++)
            {
                if(isValidNumber(board, r, c, num)) //验证是否为可行解
                {
                    board[r][c] = num; //记录解
                    q.push(board); //加入待处理队列
                    board[r][c] = 0; //恢复现场
                }
            }
        }
        else //解已经找到
        {
            sudoku = board;
            return true;
        }
    }
    return false;
}

其中isValidNumber用于验证当前位置是否可以填入数字num，FindUnassignedLocation用于查找待处理位置，Board是9×9数组类型。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：算法详解之回溯法具体实现 - Python技术站