算法5：回溯算法

深藏阁楼爱情的钟 2023-03-01 14:56 63阅读 0赞

## 1. 回溯算法：本质上就是一个决策树的遍历过程。全排列 ##

void *res = []
    def backtrack(路径, 选择列表):
        if （满足结束条件）
            res.push(路径) //将满足条件的排列推进返回列表
            return res
        for （选择;选择列表;）
            做选择
            backtrack(路径;选择列表;)//递归推进
            撤销选择

其中需要理解透彻的就是 **递归前后的选择与撤销选择，** 回溯的思想就是返回，即进行了选择之后，在递归返回的时候对之前的选择进行撤销，这是回溯算法的精华所在。

看着很迷，不急，来一个全排列的问题，什么都清楚了。

## 2. 全排列问题 ##

**Leecode 46 全排列：给定一个 没有重复数字的序列，返回其所有可能的全排列。**  
学过排列组合的我们都很清楚排列组合的算法，也即是默认 1 位不变，交换2、3位，然后保持 2 不变，交换1、3位，依次保持 3 位不变，交换1、2位，这样就可以得出所有的排列组合。  
**用算法的思路：**  
我们定义递归函数 `backtrack(first, output)` 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：

1.  如果 first==n，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。
2.  如果 first<n，我们要考虑这第 first 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 vis\[\] 来标记已经填过的数，那么在填第first 个数的时候我们遍历题目给定的 n个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 `backtrack(first + 1, output)`。搜索回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。  
    **伪代码如下：**

void res[];
    void backtrace(first,output)
    {
        
    	if(first == n)
    		res.push(output); 
    		return res:
    	for(int i = first; i < n ; i++)
    	{
        
    		do_something();//选择
    		backtrace(first+1,output);
    		~do_something();//取消选择
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70]  
**代码：**  
permute.cpp

static vector<vector<int>> res;
    
    void backtrace(vector<vector<int>> &arr,vector<int> &output, int first,int len)
    {
        
    	if (first == len)
    	{
        
    		res.push_back(output);//递归到最后一步才将排列推送进最后的返回数组中
    		return;
    	}
    	for (int i = first; i < len; i++)
    	{
        
    		swap(output[i],output[first]);//作好选择之后，进入递归
    		backtrace(res, output, first + 1, len);
    		swap(output[i],output[first]);//递归之后，返回最初的状态，所以需要对之前的操作进行撤销，或者弥补。
    	}
    }
    
    vector<vector<int>> permute(vector<int> &arr)//返回全排列
    {
        
    	backtrace(res, arr, 0, arr.size());
    	return res;
    }

mian.cpp

vector<int> arr = {
         1,2,3 };
    	vector<vector<int>> res = permute(arr);
    	int n = 1;
    	for (size_t i = 0; i < res.size(); i++)
    	{
        
    		for (size_t j = 0; j < res[0].size(); j++)
    		{
        
    			cout << res[i][j] << " ";
    			
    			if (n++ == 3)
    			{
        
    				cout << '\n';
    				n = 1;
    			}
    		}
    	}

## 3. N皇后问题 ##

题目描述：给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。  
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘\*’ 分别代表了皇后和空位。  
皇后不能在同一行，同一列，以及同一对角斜线上。  
SolveNQueens.cpp

bool IsValid(vector<string> &board, int rows, int col)
        {
        
            int n = board.size();
            if (n == 0) return false;
            //检查同列
            for (int i = 0; i < rows; i++) {
        
                if (board[i][col] == 'Q') {
        
                    return false;
                }
            }
            //右上对角线
            for (int i = rows - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        
                if (board[i][j] == 'Q') {
        
                    return false;
                }
            }
            //左上对角线
            for (int i = rows - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        
                if (board[i][j] == 'Q') {
        
                    return false;
                }
            }
            return true;
        }
        
        void backtrace(vector<string> &board, int rows,vector<vector<string>> &res)
        {
        
            //返回条件
            if (rows == board.size())
            {
        
            	res.push_back(board);
                return;
            }
            //for 选择
            for (size_t col = 0; col < board[rows].size(); col++)
            {
        
                while (!IsValid(board, rows, col))
                {
        
                    col++;
                }
                //做选择与撤销选择
                board[rows][col] = 'Q';
                backtrace(board, rows + 1,res);
                board[rows][col] = '.';
            }
        }
        
        vector<vector<string>> solveNQueens(int n) {
        
            vector<vector<string>> res;
            //初始化棋盘
            vector<string> board(n, string(n, '.'));
            backtrace(board, 0,res);
            return res;
        }

main.cpp

int main()
    {
        
    	int n = 1;
    	vector<vector<string>> res = SolveNQueens(8);
    	for (size_t i = 0; i < res.size(); i++)
    	{
        
    		for (size_t j = 0; j < res[0].size(); j++)
    		{
        
    			string str = res[i][j];
    			StringCout(str);
    		}
    		cout <<"第"<< n++ <<"种"<<endl;
    		cout << "           " << endl;
    	}
    }

输出一共92种 8 皇后的解法。  
![在这里插入图片描述][20200729184850298.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dKUUpGSg_size_16_color_FFFFFF_t_70]: /images/20230208/e1f82403d37d458db596fdd56ebb05e7.png
[20200729184850298.png]: /images/20230208/ffbbb89c899349b0affe8656d53a2cd0.png