1、“八”數(shù)碼問(wèn)題的寬度優(yōu)先搜索與深度優(yōu)先搜索我在觀看視頻和查看大學(xué)課本及網(wǎng)上搜索等資料才對(duì)“八”數(shù)碼問(wèn)題有了更進(jìn)一步的了解和認(rèn)識(shí)。一、“八”數(shù)碼問(wèn)題的寬度優(yōu)先搜索步驟如下：1、判斷初始節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若初始節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)則搜索過(guò)程結(jié)束；若不是則轉(zhuǎn)到第2步；2、由初始節(jié)點(diǎn)向第1層擴(kuò)展，得到3個(gè)節(jié)點(diǎn)：2、3、4；得到一個(gè)節(jié)點(diǎn)即判斷該節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若2、3、4節(jié)點(diǎn)均不是目標(biāo)節(jié)點(diǎn)則轉(zhuǎn)到第3步；3、從第1層的第1個(gè)節(jié)點(diǎn)向第2層擴(kuò)展，得到節(jié)點(diǎn)5；從第1層的第2個(gè)節(jié)點(diǎn)向第2層擴(kuò)展，得到3個(gè)節(jié)點(diǎn)：6、7、8；從第1層的第3個(gè)節(jié)點(diǎn)向第2層擴(kuò)展得到節(jié)點(diǎn)9；得到一個(gè)節(jié)點(diǎn)即判斷該節(jié)點(diǎn)是否為

2、目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若6、7、8、9節(jié)點(diǎn)均不是目標(biāo)節(jié)點(diǎn)則轉(zhuǎn)到第4步；4、按照上述方法對(duì)下一層的節(jié)點(diǎn)進(jìn)行擴(kuò)展，搜索目標(biāo)節(jié)點(diǎn)；直至搜索到目標(biāo)節(jié)點(diǎn)為止。二、“八”數(shù)碼問(wèn)題的深度優(yōu)先搜索步驟如下：、設(shè)置深度界限，假設(shè)為5；2、判斷初始節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若初始節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)則搜索過(guò)程結(jié)束；若不是則轉(zhuǎn)到第2步；3、由初始節(jié)點(diǎn)向第1層擴(kuò)展，得到節(jié)點(diǎn)2，判斷節(jié)點(diǎn)2是否為目標(biāo)節(jié)點(diǎn)；若是則搜索過(guò)程結(jié)束；若不是，則將節(jié)點(diǎn)2向第2層擴(kuò)展，得到節(jié)點(diǎn)3；4、判斷節(jié)點(diǎn)3是否為目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若不是則將節(jié)點(diǎn)3向第3層擴(kuò)展，得到節(jié)點(diǎn)4；5、判斷節(jié)點(diǎn)4是否為目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若不是則將節(jié)點(diǎn)4

3、向第4層擴(kuò)展，得到節(jié)點(diǎn)5；6、判斷節(jié)點(diǎn)5是否為目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若不是則結(jié)束此輪搜索，返回到第2層，將節(jié)點(diǎn)3向第3層擴(kuò)展得到節(jié)點(diǎn)6；7、判斷節(jié)點(diǎn)6是否為目標(biāo)節(jié)點(diǎn)，若是則搜索過(guò)程結(jié)束；若不是則將節(jié)點(diǎn)6向第4層擴(kuò)展，得到節(jié)點(diǎn)7；8、判斷節(jié)點(diǎn)7是否為目標(biāo)節(jié)點(diǎn)，若是則結(jié)束搜索過(guò)程；若不是則將節(jié)點(diǎn)6向第4層擴(kuò)展得到節(jié)點(diǎn)8；9、依次類推，知道得到目標(biāo)節(jié)點(diǎn)為止。三、上述兩種搜索策略的比較在寬度優(yōu)先搜索過(guò)程中，擴(kuò)展到第26個(gè)節(jié)點(diǎn)時(shí)找到了目標(biāo)節(jié)點(diǎn)；而在深度優(yōu)先搜索過(guò)程中，擴(kuò)展到第18個(gè)節(jié)點(diǎn)時(shí)得到了目標(biāo)節(jié)點(diǎn)。在寬度優(yōu)先搜索過(guò)程中，需要遍歷目標(biāo)節(jié)點(diǎn)所在層之前每層的所有節(jié)點(diǎn)，即需要遍歷所有的分支。而深度優(yōu)先搜索過(guò)程中，則不需要遍歷這么多的節(jié)點(diǎn)。所以，在“八”數(shù)碼問(wèn)題的求解過(guò)程中，深度優(yōu)先搜索的效率明顯比寬度優(yōu)先搜索的效率要高。一般情況下，深度優(yōu)先適合深度大的樹(shù)，不適合廣度大的樹(shù)，廣度優(yōu)先則正好相反。所謂深度大的樹(shù)就是指起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的中間節(jié)點(diǎn)多的樹(shù)（可以理解成問(wèn)題有很多中間解，這些解都可以認(rèn)為是部分正確的，但要得到完全正確的結(jié)果目標(biāo)節(jié)點(diǎn)，就必須先依次求出這些中間解）。所謂廣度大的樹(shù)就是指起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的可能節(jié)點(diǎn)很多的樹(shù)（可以理解成問(wèn)題有很多可能解，這些解要么正確，要么錯(cuò)誤。要得到完全正確的結(jié)果目標(biāo)節(jié)點(diǎn)，就必須依次判斷這些可能解是否正確）。多數(shù)情況下