(八皇后问题分析)回溯法两种控制流程

来源：百度文库 编辑：神马文学网 时间：2024/06/13 12:05:49
/****************************************/回溯法控制流程一

将栈置为空；
while(还没找到解)
{ //进入下一阶段；
    将此阶段的第一个选择压入栈中；
    while(栈顶的选择不可行)
    {
       while(栈顶的选择为最后一个选择)
       {
          弹栈； //回溯；
          if(栈为空)
              return 无解；
       }
       将栈顶修改为其下一个选择；
    }
}
return 有解；


例子八皇后：
check函数初步实现：
bool check(Gstack 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 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 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; //有解；
}/******************************************************/
(八皇后问题分析)回溯法两种控制流程 递归法，八皇后问题 回溯法旅行售货员问题 皇后问题 MapServer流程概要分析 SEO流程分析 从JSF的切入点控制JSF流程 ANT（1.6）高级特性：流程控制 设计流程的研究分析 设计流程的研究分析 大学生创业流程全分析 大学生创业流程全分析 远程教育的质量控制问题 (回溯法1) 催眠童年回溯 催眠童年回溯 催眠前世回溯疗法 发现问题，分析问题，解决问题 JR - 精品文章 - ANT（1.6）高级特性流程控制 工作流模式详解之流程控制模式(2) IT流程控制及自动化解决方案 NetIQ? Aegis 程序流程控制——Select Case语句 大股东控制与内部人控制的比较分析 从六个角度分析流程建模