IT源码网

全排列 51 n皇后问题

itxm 2020年10月22日 编程语言 514 0

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]


解:这道题时典型的回溯法,把所有可能的情况都尝试一遍;写代码的时候要注意做选择和撤销选择

class Solution { 
public: 
    vector<vector<int>> permute(vector<int>& nums) { 
        vector<vector<int>> res; 
        vector<int> vec_fuben=nums; 
        AllPartion(res,vector<int>(),vec_fuben); 
        return res; 
    } 
 
    void AllPartion(vector<vector<int>> &res,vector<int> tmp_vec,vector<int>vec_fuben) 
    { 
        if(vec_fuben.size()==0) 
        { 
            res.emplace_back(tmp_vec); 
            return; 
        } 
        for(int i=0;i<vec_fuben.size();i++) 
        { 
            tmp_vec.emplace_back(vec_fuben[i]); 
            int tmp_value=vec_fuben[i]; 
            //做选择 
            vec_fuben.erase(vec_fuben.begin()+i); 
             
            AllPartion(res,tmp_vec,vec_fuben); 
            //撤销选择 
            vec_fuben.insert(vec_fuben.begin()+i,tmp_value); 
            tmp_vec.pop_back(); 
        } 
    } 
};

二。51n皇后问题 

 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

 

这个问题很经典了,简单解释一下:给你一个 N×N 的棋盘,让你放置 N 个皇后,使得它们不能互相攻击。

PS:皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

这个问题本质上跟全排列问题差不多,决策树的每一层表示棋盘上的每一行;每个节点可以做出的选择是,在该行的任意一列放置一个皇后。

直接套用框架:

vector<vector<string>> res; 
 
/* 输入棋盘边长 n,返回所有合法的放置 */ 
vector<vector<string>> solveNQueens(int n) { 
    // '.' 表示空,'Q' 表示皇后,初始化空棋盘。 
    vector<string> board(n, string(n, '.')); 
    backtrack(board, 0); 
    return res; 
} 
 
// 路径:board 中小于 row 的那些行都已经成功放置了皇后 
// 选择列表:第 row 行的所有列都是放置皇后的选择 
// 结束条件:row 超过 board 的最后一行 
void backtrack(vector<string>& board, int row) { 
    // 触发结束条件 
    if (row == board.size()) { 
        res.push_back(board); 
        return; 
    } 
     
    int n = board[row].size(); 
    for (int col = 0; col < n; col++) { 
        // 排除不合法选择 
        if (!isValid(board, row, col))  
            continue; 
        // 做选择 
        board[row][col] = 'Q'; 
        // 进入下一行决策 
        backtrack(board, row + 1); 
        // 撤销选择 
        board[row][col] = '.'; 
    } 
} 
/* 是否可以在 board[row][col] 放置皇后? */ 
bool isValid(vector<string>& board, int row, int col) { 
    int n = board.size(); 
    // 检查列是否有皇后互相冲突 
    for (int i = 0; i < n; i++) { 
        if (board[i][col] == 'Q') 
            return false; 
    } 
    // 检查右上方是否有皇后互相冲突 
    for (int i = row - 1, j = col + 1;  
            i >= 0 && j < n; i--, j++) { 
        if (board[i][j] == 'Q') 
            return false; 
    } 
    // 检查左上方是否有皇后互相冲突 
    for (int i = row - 1, j = col - 1; 
            i >= 0 && j >= 0; i--, j--) { 
        if (board[i][j] == 'Q') 
            return false; 
    } 
    return true; 
}

函数 backtrack 依然像个在决策树上游走的指针,通过 row 和 col 就可以表示函数遍历到的位置,通过 isValid 函数可以将不符合条件的情况剪枝:

 

 另外,拓展一下,

有的时候,我们并不想得到所有合法的答案,只想要一个答案,怎么办呢?比如解数独的算法,找所有解法复杂度太高,只要找到一种解法就可以。

其实特别简单,只要稍微修改一下回溯算法的代码即可:

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return true;
}
...
for (int col = 0; col < n; col++) {
...
board[row][col] = 'Q';

if (backtrack(board, row + 1))
return true;

board[row][col] = '.';
}

return false;
}
这样修改后,只要找到一个答案,for 循环的后续递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上,稍加修改,写一个解数独的算法?

三、最后总结
回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:

def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择
写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。

其实想想看,回溯算法和动态规划是不是有点像呢?我们在动态规划系列文章中多次强调,动态规划的三个需要明确的点就是「状态」「选择」和「base case」,是不是就对应着走过的「路径」,当前的「选择列表」和「结束条件」?

某种程度上说,动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质,可以用 dp table 或者备忘录优化,将递归树大幅剪枝,这就变成了动态规划。而今天的两个问题,都没有重叠子问题,也就是回溯算法问题了,复杂度非常高是不可避免的。

评论关闭
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!