/****************************************/ 回溯法控制流程一 将栈置为空; while(还没找到解) { //进入下一阶段; 将此阶段的第一个选择压入栈中; while(栈顶的选择不可行) { while(栈顶的选择为最后一个选择) { 弹栈; //回溯; if(栈为空) return 无解; } 将栈顶修改为其下一个选择; } } return 有解; 例子八皇后: check函数初步实现: bool check(Gstack<int> const& board) { //栈顶刚放置了一个新皇后,检查这个皇后是否安全; int row = board.size() - 1; for(int k = 1; --row >= 0; ++k) if( (board[row] == board.top() ) || (board[row] == board.top() + k) || (board[row] == board.top() - k) ) return false; return true; } 八皇后问题初步解: int const num_queens = 8; int const zero = 0; int const seven = num_queens - 1; bool eight_queen() { Gstack<int> board(num_queens); while(board.size() < num_queens) { board.push(zero); for(; !check(board); ++board.top()) { while(board.top() >= seven){ //top为最后一个选择; board.pop(); if(board.empty()) return false; //无解; } } } write_board(board); //输出解; return true; } /******************************************************/ /*********************************************************/ 回溯法控制流程二: 将栈置为空; while(还没找到解) { //进入下一阶段; x = 此阶段第一个选择; while(x不可行) { while( x为本阶段的最后选择) { if(栈为空) return 无解; x =栈顶元素; 弹栈;//回溯; } x = x的下一个选择; } 将x压栈; } return 有解; 八皇后例子: 改进的check函数: int const num_queens = 8; int const zero = 0; int const seven = num_queens - 1; //对角线条数; int const fifteen = 2*num_queens - 1; bool column_free[num_queens]; bool diag_free[fifteen]; //正对角线; bool inv_diag_free[fifteen]; //反对角线; //检查位置(i,j)是否安全; bool check(int i, int j) { return column_free[j] && diag_free[i + j] && inv_diag_free[seven + i - j]; } 设置和移除皇后: void set_queen(int i, int j) { //在(i,j)上设置一个皇后; column_free[j] = inv_diag_free[seven + i - j] = diag_free[i + j] = false; } void remove_queen(int i, int j) { //将(i,j)上的皇后移除; column_free[j] = inv_diag_free[seven + i - j] = diag_free[i + j] = true; } 改进后的八皇后问题解: bool eight_queen2() { fill_n(column_free, num_queens, true); fill_n(diag_free, fifteen; true); fill_n(inv_diag_free, fifteen, true); Gstack<int> board(num_queens); while(board.size() < num_queens) { for(int j = zero; !check(board.size(), j); ++j){ while(j >= seven) { if(board.empty()) return false; //无解; j = board.top(); board.pop(); remove_queen(board.size(), j); } } set_queen(board.size(), j); board.push(j); } write_board(board); //输出解; return true; //有解; } /******************************************************/ |
|