剪枝算法
剪枝，常用于搜索算法的优化，即在在搜索过程中，提前剪去不可能的分支，减少工作量
生活中的常见的一些问题，经常有数量庞大的情况状态组合，无法全部覆盖到。或前继节点状态决定了后继节点的状态不在搜索范围内，这些情况下就应果断剪去无效/非最优分支，留下有效/最优分支
如上图所示为九宫格问题的部分分支扩展，可以看到分支数目极大，随着层数增大复杂度呈几何级数增长
所谓下棋，就是对每一步及之后可能的状态集合进行推演，选择对己方有利的局面，同时根据已经落下的棋子减掉“过期”的分支
1996年DeepBlue vs Kasprov、2016年AlphaGo vs柯洁 ……
剪枝算法没有所谓模板，应具体问题具体分析
实战题目
-
- 思路一：暴力求解，对每一层（行、列）进行简单遍历
- 思路二：用一维数组对状态进行保存
- 思路三：DFS深搜
一种DFS
def solveNQueens(self, n): if n<1: return [] self.result = [] self.cols = set();self.pie = set(); self.na = set() #na:捺，pie：撇 self.DFS(n, 0, []) return self.generate_result(n) def DFS(self, n, row, cur_ _state): if row >= n:# recursion terminator self. result. append(cur_ state) return for col in range(n): if col in self.cols or row + coL in self.pie or row - col in self.na: # go die! continue # update the flags self.cols.add(col) self.pie.add(row + col) self.na.add(row-col) self.DFS(n, row + 1, cur_ state + [col]) self.cols.remove(col) self.pie.remove(row + col) self.na.remove(row - col) def _ generate_ result(self, n): board=[] for res in self.result: for i in res: board.append("."* i + "Q"+'.'*(n-i-1)) return [board[i: i + n] for i in range(0, len(board), n)]另一种DFS
def solveNQueens(self, n): def DFS(queens, xy_ dif, xy_ sum): p = len(queens) if p==n: result.append(queens) return None for q in range(n): if q not in queens and p-q not in xy_ dif and p+q not in xy_sum: DFS(queens+[q], xy_dif+[p-q], xy_sum+ [p+q]) result = [] DFS([],[],[]) return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]- java版本：
public List<String[]> solveNQueens(int n) { List<String []>res = new ArrayList<>(); helper(0,new boolean[n], new boolean [2*n], new boo lean [2*n], new String[n],res); return res; } private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2,String[] board, List<String[]> res) { if (r == board.length) res.add( board.clone()); else { for (int C = 0; C < board.length; C++) { int id1=r-C+board.length,id2=2*board.length-r-C-1; if(!cols[c] && !d1[id1] && !d2 [id2]) { char[] row = new char [board. length]; Arrays.fill(row, '.'); row[c] = 'Q'; board[r] = new String( row); cols[c] = true; d1[id1] = true; d2 [id2] = true; helper(r+1, cols, d1, d2, board, res) ; cols[c] = false; d1[id1] = false; d2[id2] = false; } } } }
有效数独 所谓“有效数独”，指的是col[9]、row[9]、block[3][3]内不存在重复数字。和N皇后问题类似，大致思路也是搜索+剪枝，关键问题在于如何对数独中的元素进行有效地标记和判重
- 思路：两重for循环，统计行row[9]、列clo[9]以及小九格block[3][3]（9*9棋盘）中每个数字出现次数，判断是否出现重复。其中，小九格的映射关系是block[i/3][j/3]，row、col可设计为二维数组，第二维表示1-9的数字出现次数，也可设计为Set数组。
- 解数独
整体思路：将空格一个一个试着填入数字，发现冲突无解时再退回重新填- 基本思路：DFS对所有空格(j,j)进行枚举，每次枚举过程：
- 先判断j+1是否超限（超出右边界），若超限则i+=1，j=0，从下一行开始
- 再遍历1-9的数，若该数字有效（row[i]、col[j]、block[i/3][j/3]内均无重复的数）则填入，下一个空格
- 若1-9的数字都无效，则回退上一个空格，填入该空格下一个有效的数 加速思路：
- 先从那些已经确定较多的行，即选项少的空格入手，确定下来后总体扩展空间就小得多
- 遍历之前先做预处理，将每个空格处的有效数字先计算出来，遍历时直接从有效数字里面遍历即可。
- 使用高级的数据结构，比如dancing link
- 使用位运算判重……
- 简单行列遍历基础实现:
class Solution { public void solveSudoku(char[][] board) { if (board == null || board.length == 0) return; solve(board); } public boolean solve(char[][] board){ for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j]=='.') { for(char c='1';c<='9';c++){ if (isValid(board, i, j, c)) { board[i][j] = c; if (solve(board)) return true; else board[i][j] = '.'; //Otherwise go back } } return false; } } } return true; } private boolean isValid( char[][] board,int row,int col, char c){ for(int i = 0; i<9; i++){ if(board[i][col] != '.' && board[i][col] == c) return false;// check row if(board[row][i] != '.' && board[row][i] == c) return false;//check column if(board [3 * (row / 3) +i / 3][ 3 * (col / 3)+i % 3] != '.' && board [3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;//check 3*3 block } return true; } }
- 简单行列遍历基础实现:
- 基本思路：DFS对所有空格(j,j)进行枚举，每次枚举过程：