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