在线不卡日本ⅴ一区v二区_精品一区二区中文字幕_天堂v在线视频_亚洲五月天婷婷中文网站

  • <menu id="lky3g"></menu>
  • <style id="lky3g"></style>
    <pre id="lky3g"><tt id="lky3g"></tt></pre>

    算法|八皇后問題理解回溯法

    算法|八皇后問題理解回溯法

    回溯算法從空解開始,并逐步擴(kuò)展該解。搜索遞歸地通過各種不同的構(gòu)造解決方案的路徑。

    例如,考慮計(jì)算n皇后問題:在n*n的棋盤上放置彼此不受攻擊的n個(gè)皇后。

    (皇后可以攻擊在同一行、同一列、同一斜線上的棋子)

    按以上規(guī)則:同一行或同一列或同一斜線上只能有一個(gè)皇后,同一行或同一列上必須有一個(gè)皇后。

    n皇后問題的解空間是一棵n叉樹,樹的深度為n。

    當(dāng)n為4時(shí),有兩種可能的解決方案:

    八皇后問題對(duì)于每一行是否可以放置皇后,可用一個(gè)規(guī)模為8的循環(huán)去判斷。每一行的判斷操作相同,如果操作完成了8行(放置了8個(gè)皇后),便求出了一個(gè)解。所以該問題可以用遞歸去做。如果某一行全部位置無法放置皇后時(shí),沒必要繼續(xù)深入,可以回溯到上一步,也就是使用回溯法。對(duì)于非尾遞歸,遞歸函數(shù)回退時(shí),遞歸點(diǎn)后面的代碼就是遞歸函數(shù)回退后執(zhí)行的部分。對(duì)于八皇后問題,上述的循環(huán)可以判斷某行下一列是否可以放置皇后,而上一列放置皇后的操作進(jìn)行逆操作后便完成了回溯(遞歸有天然的回退階段)。

    八皇后問題的暴力枚舉搜索或遞歸解法會(huì)形成一個(gè)棵8叉完全樹,回溯解法可以通過約束條件避免一些搜索繼續(xù)深入,形成一棵8叉不完全樹。

    為簡(jiǎn)便起見,我們可以用四皇后問題去理解,然后泛化到一般的情況。

    在底層,前三種配置是非法的,因?yàn)榛屎髠兓ハ喙?。然而,第四種配置是有效的,可以通過在棋盤上再放置兩個(gè)皇后來擴(kuò)展到完整的解決方案。只有一種方法可以放置剩下的兩個(gè)皇后。

    如下面左圖所示:

    從y=0,x=0開始,search(0)遞歸調(diào)用search(1)(x=2,y=1),遞歸調(diào)用search(2)

    當(dāng)y=2,x=3時(shí),遞歸函數(shù)search(2)執(zhí)行完畢,回退到search(1),x=0,逆操作,循環(huán)到x=3……

    code demo:

    #include #define n 4int column[n*2] = {0};int diag1[n*2] = {0};int diag2[n*2] = {0};int count = 0;void search(int y) { if (y == n) { count++; return; } for (int x = 0; x < n; x++) { if (column[x] || diag1[x+y] || diag2[x-y+n-1]) continue; column[x] = diag1[x+y] = diag2[x-y+n-1] = 1; search(y+1); column[x] = diag1[x+y] = diag2[x-y+n-1] = 0; // 回退時(shí)的逆操作,下一輪循環(huán)x++ } return;}main(){ search(0); printf("%d",count); getchar();}/*n=4, 2n=8, 92n=16, 14772512*/

    搜索從調(diào)用search(0)開始。棋盤的大小為n*n,代碼計(jì)算要計(jì)數(shù)的解決方案數(shù)。

    代碼假設(shè)棋盤的行和列編號(hào)從0到n-1。當(dāng)使用參數(shù)y調(diào)用函數(shù)搜索時(shí),它會(huì)在行y上放置皇后,然后使用參數(shù)y-1調(diào)用自身。然后,如果y=n,則已找到解決方案,變量count增加1。

    數(shù)組column跟蹤包含皇后的列,數(shù)組diag1和diag2跟蹤對(duì)角線。不允許在已包含皇后的列或?qū)蔷€中添加其他皇后。例如,4*4棋盤編號(hào)如下,當(dāng)x、y取不同的值時(shí),對(duì)應(yīng)列方向column[x]、”/”方向上diag1[x+y]、””方向上diag2[x-y+4-1]的取值為0時(shí)表示無皇后:

    y 2,x=3

    回溯。

    y 1,x=3

    ……

    count=1。

    回溯到下面綠色點(diǎn):

    繼續(xù)逐步回溯:

    ……

    count=2。

    繼續(xù)逐步回溯,最后count=2。

    可視化操作的網(wǎng)頁地址:

    https://pythontutor.com/render.html#mode=display

    -End-

    鄭重聲明:本文內(nèi)容及圖片均整理自互聯(lián)網(wǎng),不代表本站立場(chǎng),版權(quán)歸原作者所有,如有侵權(quán)請(qǐng)聯(lián)系管理員(admin#wlmqw.com)刪除。
    用戶投稿
    上一篇 2022年8月22日 09:10
    下一篇 2022年8月22日 09:10

    相關(guān)推薦

    • 存儲(chǔ)過程語法(sql server存儲(chǔ)過程語法)

      今天小編給各位分享存儲(chǔ)過程語法的知識(shí),其中也會(huì)對(duì)sql server存儲(chǔ)過程語法進(jìn)行解釋,如果能碰巧解決你現(xiàn)在面臨的問題,別忘了關(guān)注本站,現(xiàn)在開始吧! oracle存儲(chǔ)過程基本語法…

      2022年11月26日
    • 百度關(guān)鍵詞快速排名的4大原理解析(百度怎么刷關(guān)鍵詞)

      近期百度公告驚雷算法2.0,升級(jí)之快還是第一次吧,看來百度對(duì)于刷點(diǎn)擊行為是零容忍了。之前尹華峰SEO技術(shù)博客介紹過一篇如何使用刷點(diǎn)擊工具,其實(shí)市面上有很多這類SEO快速排名的軟件,…

      2022年11月25日
    • 淘寶直播開通后帶貨鏈接怎么做(淘寶直播需要開通淘寶店鋪嗎)

      直播帶貨無論是對(duì)于商家來說還是主播收益都是非??捎^的,所以不少平臺(tái)都有直播帶貨功能,一些小伙伴也想加入淘寶直播,那么淘寶直播開通后帶貨鏈接怎么做?下面小編為大家?guī)硖詫氈辈ラ_通后帶…

      2022年11月24日
    • 不思議迷宮圍棋少年答題答案大全 東郭棋院題目答案匯

      不思議迷宮圍棋少年活動(dòng)中的答題答案是什么?完成答題之后是可以得到很多獎(jiǎng)勵(lì)的,活動(dòng)中的答題題目有很多,這些題目的詳情小編已經(jīng)分享在下面,另外關(guān)于圍棋少年全部答題的答案下面也有介紹,幫…

      2022年11月23日
    • 快手限流多久能解除(快手限流什么意思)

      我相信很多人都看中了快手平臺(tái)的商機(jī),都爭(zhēng)先恐后地想要搶占機(jī)會(huì),可一些人剛剛作出一點(diǎn)成績(jī),就被降權(quán)了,自己也不知道什么原因。所以今天就來聊聊快手賬號(hào)降權(quán)操作分享,趕快來看看避免違規(guī)!…

      2022年11月23日
    • Win11 22H2再出新問題Bug:無法彈出USB設(shè)備

      作為Windows 11的首次大更新,在Win11 22H2發(fā)布后并沒有帶來預(yù)想的場(chǎng)景,各種問題頻現(xiàn)成為了一種常態(tài)。 近日有消息稱,Win11 22H2存在一個(gè)占用沖突Bug,當(dāng)用…

      2022年11月22日
    • 馬斯克凌晨一點(diǎn)半曬“代碼審查”現(xiàn)場(chǎng),編排他的段子比瘋狂星期四還多

      夢(mèng)晨 Pine 發(fā)自 凹非寺 量子位 | 公眾號(hào) QbitAI 每一個(gè)真正會(huì)寫代碼的人,請(qǐng)?jiān)谙挛?點(diǎn)到總部10層報(bào)到。 每一個(gè)真正會(huì)寫代碼的人,請(qǐng)?jiān)谙挛?點(diǎn)到總部10層報(bào)到。 馬斯…

      2022年11月21日
    • 美團(tuán)月付300小額取現(xiàn)?美團(tuán)月付取現(xiàn)300不見了

      很多上班族每天都在使用美團(tuán)點(diǎn)外賣,你知道美團(tuán)現(xiàn)在推出了一款類似花唄的產(chǎn)品嗎?可以在美團(tuán)消費(fèi)的時(shí)候先消費(fèi)后還款,叫做美團(tuán)月付,是美團(tuán)推出的一款消費(fèi)型產(chǎn)品,不能直接提現(xiàn)到銀行卡,只能用…

      2022年11月21日
    • 3階魔方教程 1~7步驟(魔方教程一步一步圖解)

      基礎(chǔ)層先魔方復(fù)原法 by信手拈花 0. 魔方轉(zhuǎn)動(dòng)的公式表示和復(fù)原步驟 0. 1魔方轉(zhuǎn)動(dòng)的公式表示 魔方轉(zhuǎn)動(dòng)的公式表示 0. 2層先法魔方復(fù)原步驟 層先法魔方復(fù)原步驟 讓我開始魔方復(fù)…

      2022年11月18日
    • 沒帶卡怎么在ATM機(jī)取款(無卡取款怎么操作)

      刷臉消費(fèi)支付已經(jīng)十分方便,最近不少銀行根據(jù)這種刷臉技術(shù),提供了刷臉存取款的業(yè)務(wù)。我們不需要帶卡,就可以直接刷臉取款。下面讓我們來看看具體怎么操作。 刷臉取款怎么操作? 【1】我們找…

      2022年11月17日

    聯(lián)系我們

    聯(lián)系郵箱:admin#wlmqw.com
    工作時(shí)間:周一至周五,10:30-18:30,節(jié)假日休息