利用BFS算法解八数码问题
在3*3的方格上放着1-8数码,有一空格为0变化规则为空格可以和上,下,右,左四个相邻的数字互换,
至到和目标状态相等,
每一种状态用一个结点表示
而每个结点每次变化最多有四种结点,将这些结点依次入队列中,
例如初始结点S0,入队列后出队,将S0变化最多产生的四种结点S01,S02,S03,S04依次入队列中,
当S01出队后,产生的四种结点S11,S12,S13,S14(实际上不会有四种结点)依次入队,
每次出队时与结束结点相比较,如果相等则退出,
为了,防止已经入队的结点再次入队,(这样会造成列循环),将每次入队的结点设置一个标识号,
四种变化即:向上,向下,向右,向左,我们要求向上和向下互斥,向右和向左互斥
标签:
BFS
数码
算法
上传时间:
2015-04-24
上传用户:sdq_123