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