回溯法——以皇后擺放問題為例

回溯法(98條消息) （新手向）遞歸與回溯算法學(xué)習(xí)（一）——n位逐位整除數(shù)_TripleGold.的博客-CSDN博客

算法思想：

（通用的解題法）窮舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)不滿足求解條件時(shí)就回退，嘗試其他路徑

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、金塔網(wǎng)絡(luò)推廣、小程序設(shè)計(jì)、金塔網(wǎng)絡(luò)營銷、金塔企業(yè)策劃、金塔品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供金塔建站搭建服務(wù)，24小時(shí)服務(wù)熱線：028-86922220，官方網(wǎng)址：chinadenli.net

回溯法的解題步驟：

針對(duì)給定問題確定問題的解空間樹，至少包含問題的一個(gè)解或者最優(yōu)解
確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則
以深度優(yōu)先搜索解空間樹，并采取剪枝手段。

框架：

非遞歸回溯框架

int x[n]    //x存放解向量，全局變量
void backtrack(int n){
    int i = 1;      //根節(jié)點(diǎn)的層次為1
    while(i>=1){    //尚未回溯到頭        
    if(ExistSubNode(t)){    //當(dāng)前結(jié)點(diǎn)存在子節(jié)點(diǎn)
        for(j=下界;j<=上界;j++){    //對(duì)于子集樹，j從0到1循環(huán)
            x[i]取一個(gè)可能的值;
            if(constraint(i)&&bound(i)){    //x[i]滿足約束條件和界限函數(shù)
                if(x是一個(gè)可行的解)
                    輸出x;
                else i++;   //進(jìn)入下一個(gè)層次
            }
        }
    }
    else i--;   //不存在子節(jié)點(diǎn)，返回上一層
    }
}

遞歸回溯框架

int x[n]
void backtrack(int i){
    if(i>n)     //搜索葉子結(jié)點(diǎn)，輸出一個(gè)可行解
        輸出結(jié)果;
    else{
        for(j=下界;j<=上界;j++){    //用j枚舉i所有可能的路徑
            x[i] = j;   //產(chǎn)生一個(gè)可能的解分量
            ...
            if(constraint(i)&&bound(i))
                backtrack(i+1)  //滿足約束條件繼續(xù)下一層
        }
  }
}

result = []
def backtrack(路徑, 選擇列表):
   if 滿足結(jié)束條件:
     result.add(路徑)
     return
    
   for 選擇 in 選擇列表:
     做選擇
     backtrack(路徑, 選擇列表)
     撤銷選擇
?

例題：皇后擺放問題：

題目描述

國際象棋的棋盤可以看做是一個(gè) 8 × 8 的矩陣，上面每一個(gè)格子僅能放一枚棋子，現(xiàn)在給出一個(gè) 8 × 8 的由 0 和 1 組成的矩陣，代表象棋棋盤，1 代表當(dāng)前位置放置了一個(gè)皇后，0 則代表什么都沒有放，上面有 n（n 為小于 8 的正整數(shù)）個(gè)位置已經(jīng)放上了皇后棋子（相互之間不沖突，合理擺放），現(xiàn)在另外給你 8 - n 個(gè)皇后，問你有多少合理的擺法。

輸入描述

一個(gè) 8 × 8 的由 0 和 1 組成的矩陣。

輸出描述

一個(gè)整數(shù)，為擺放的種類數(shù)。

樣例輸入

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

樣例輸出

問題分析

判斷某位置是否可以擺放皇后

假設(shè)i行j列處已擺放上一個(gè)皇后，則下面擺放的皇后(x,y)則不能在i行和j列(即x!=i && y!=j)，且不能在已擺放皇后對(duì)角線上(即abs(x-i)!=abs(y-j))。

搜索算法

通過初始化，我們可以知道哪些位置有了皇后。通過一個(gè)路徑數(shù)組path[9]來記錄（1~8）行哪一列有皇后。還未探索到的行，數(shù)組賦值0。

用回溯法，從第一行開始往下，測試1~8列是否能夠擺放，能則繼續(xù)往下探索，不能則返回上一層。

AC代碼：

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std; 
?
int path[9];
//判斷某位置是否可以擺放皇后
bool pd(int x){
  for(int i=1;i<=8;i++){
    if(path[i]!=0 &&i!=x && (path[i]==path[x] || abs(i-x)==abs(path[i]-path[x]))){
      return false;
     }
   }
  return true;
}
//搜索算法
void backtrace(int x,int &sum){
  if(x==9){
    sum++;
    return;
   }
  if(!path[x]){
    for(int i=1;i<=8;i++){
?
      path[x] = i;
      if(pd(x)) backtrace(x+1,sum);
      path[x] = 0;
     }
   }
  else backtrace(x+1,sum);
}
?
int main(){
  int x,sum = 0;
  memset(path,0,sizeof(path));
  for(int i=1;i<9;i++){
    for(int j=1;j<9;j++){
      cin>>x;
      if(x==1){
        path[i]=j; 
       }
     }
   }
  backtrace(1,sum);
  cout<<sum<<endl;
  return 0;
}

當(dāng)前標(biāo)題：回溯法——以皇后擺放問題為例
網(wǎng)站網(wǎng)址：http://chinadenli.net/article38/dsoipsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、企業(yè)建站、品牌網(wǎng)站設(shè)計(jì)、軟件開發(fā)、網(wǎng)頁設(shè)計(jì)公司、移動(dòng)網(wǎng)站建設(shè)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区