A – EIGHT
2018-06-15 14:31 更新
八數(shù)碼轉(zhuǎn)換問題……
經(jīng)典bfs……
關(guān)鍵問題：
1.狀態(tài)的保存（見longwuxu該題解題報(bào)告中的全排列Hash表示）
2.bfs中標(biāo)記數(shù)組的處理：
bfs中有兩個(gè)標(biāo)記數(shù)組，一個(gè)是標(biāo)記隊(duì)列中節(jié)點(diǎn)的標(biāo)記數(shù)組isadd[]，另一個(gè)是標(biāo)記已訪問節(jié)
點(diǎn)標(biāo)記數(shù)組isvis[]。前者在入隊(duì)列的時(shí)候進(jìn)行標(biāo)記，而后者則要在出隊(duì)列的時(shí)候才進(jìn)行標(biāo)記
用isadd標(biāo)記的時(shí)候隊(duì)列中不會(huì)出現(xiàn)重復(fù)的節(jié)點(diǎn)，而用isvis標(biāo)記的時(shí)候隊(duì)列中會(huì)出現(xiàn)重復(fù)的
節(jié)點(diǎn)。所以前者要比后者的效率高，所占用的空間也要少……一般采用isadd[]數(shù)組標(biāo)記較優(yōu)
經(jīng)典bfs……
關(guān)鍵問題：
1.狀態(tài)的保存（見longwuxu該題解題報(bào)告中的全排列Hash表示）
2.bfs中標(biāo)記數(shù)組的處理：
bfs中有兩個(gè)標(biāo)記數(shù)組，一個(gè)是標(biāo)記隊(duì)列中節(jié)點(diǎn)的標(biāo)記數(shù)組isadd[]，另一個(gè)是標(biāo)記已訪問節(jié)
點(diǎn)標(biāo)記數(shù)組isvis[]。前者在入隊(duì)列的時(shí)候進(jìn)行標(biāo)記，而后者則要在出隊(duì)列的時(shí)候才進(jìn)行標(biāo)記
用isadd標(biāo)記的時(shí)候隊(duì)列中不會(huì)出現(xiàn)重復(fù)的節(jié)點(diǎn)，而用isvis標(biāo)記的時(shí)候隊(duì)列中會(huì)出現(xiàn)重復(fù)的
節(jié)點(diǎn)。所以前者要比后者的效率高，所占用的空間也要少……一般采用isadd[]數(shù)組標(biāo)記較優(yōu)
以上內(nèi)容是否對(duì)您有幫助：
更多建議：