利用BFS算法解八數(shù)碼問題
在3*3的方格上放著1-8數(shù)碼，有一空格為0變化規(guī)則為空格可以和上，下，右，左四個相鄰的數(shù)字互換，
至到和目標(biāo)狀態(tài)相等，
每一種狀態(tài)用一個結(jié)點(diǎn)表示
而每個結(jié)點(diǎn)每次變化最多有四種結(jié)點(diǎn)，將這些結(jié)點(diǎn)依次入隊(duì)列中，
例如初始結(jié)點(diǎn)S0,入隊(duì)列后出隊(duì)，將S0變化最多產(chǎn)生的四種結(jié)點(diǎn)S01,S02,S03,S04依次入隊(duì)列中，
當(dāng)S01出隊(duì)后，產(chǎn)生的四種結(jié)點(diǎn)S11，S12，S13，S14(實(shí)際上不會有四種結(jié)點(diǎn))依次入隊(duì)，
每次出隊(duì)時與結(jié)束結(jié)點(diǎn)相比較，如果相等則退出，
為了，防止已經(jīng)入隊(duì)的結(jié)點(diǎn)再次入隊(duì)，(這樣會造成列循環(huán)),將每次入隊(duì)的結(jié)點(diǎn)設(shè)置一個標(biāo)識號，
四種變化即:向上，向下，向右，向左，我們要求向上和向下互斥，向右和向左互斥
標(biāo)簽：
BFS
數(shù)碼
算法
上傳時間：
2015-04-24
上傳用戶：sdq_123
