八數(shù)碼轉(zhuǎn)換問題……
經(jīng)典bfs……
關(guān)鍵問題:
1.狀態(tài)的保存(見longwuxu該題解題報(bào)告中的全排列Hash表示)
2.bfs中標(biāo)記數(shù)組的處理:
bfs中有兩個標(biāo)記數(shù)組,一個是標(biāo)記隊(duì)列中節(jié)點(diǎn)的標(biāo)記數(shù)組isadd[],另一個是標(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ì)列中不會出現(xiàn)重復(fù)的節(jié)點(diǎn),而用isvis標(biāo)記的時(shí)候隊(duì)列中會出現(xiàn)重復(fù)的
節(jié)點(diǎn)。所以前者要比后者的效率高,所占用的空間也要少……一般采用isadd[]數(shù)組標(biāo)記較優(yōu)
更多建議: