推 love5566188:喔喔~我懂了謝謝B大,一開始也有這樣想但不確定. 02/06 23:55
→ love5566188:畫完這串葡萄也太大了吧= =考試卷都快塞不下了 02/07 00:01
推 rayway30419:至少沒叫你剪枝XD 02/07 11:39
※ 引述《love5566188 (I'dont kown)》之銘言：
: http://0rz.tw/iP0Xy
: 我想問第9題第三小題
: (iii)The above backtracking algorithm can be formulated as a depth-first
: search of the state space tree with backtracking. What is the state space
: tree of the 4-Queens problem?
: 這題的state space tree要怎麼求出,而又代表著什麼意思?
: (抱歉題目圖不太會用,所以直接貼網址)
不清楚你對state space tree的了解有多少
就先當作你全不懂 寫詳細些
要求state space tree感覺還蠻夭壽的，畫出來很大一串葡萄
它代表著什麼意思，就是每個node記錄著目前解的情況，
從root到leaf就是一組解
以這題來說root就設為空棋盤，沒放任何queen
第一個child設為(1,1)，也就是在(1,1)處放第一個queen
root
/
(1,1)
接著由(1,1)這個node往下走繼續解
接著試著擺(2,1)這位置 [同row不能放所以(1,X)都不用考慮]
root
/
(1,1)
/
(2,1)
我們發現(2,1)不能放queen，因此以(2,1)為root的subtree也不用展開了
回到(2,1)的parent(1,1)繼續，下個要試的是(2,2)，發現也不行
到(2,3)才發現可以
root
/
(1,1)
/ \ \
(2,1)(2,2)(2,3)
所以繼續從(2,3)往下.....
直到放置完4個queen，就產生一組解了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.174.14.16