1 前言
三阶数字华容道问题又称八数码问题，目前解决数字华容道问题的方法主要有DFS、贪婪算法、A算法等。DFS时间复杂度较高，贪婪算法和A算法都能得到一个有效解，但都不是最优解。笔者通过大量实验，使用BFS进行数据预处理后，能够得到最优解。
（1）定义：
状态(S)：每个棋盘的布局称为一个状态，其中状态 [[1,2,3],[4,5,6],[7,8,9]] 称为零状态
代价(C)：从当前状态到零状态所需的最小步数
相连：若状态S1可以通过一步到达状态S2，则称S1与S2相连，每个状态最多与4个状态相连
可达性：若状态S1可以通过有限步到达状态S2，则称S1与S2可达（并不是所有状态都是可达的）
连通集：将所有可达的状态归位一类，称为连通集，一共有2个连通集，每个连通集中有 9!/2=181,440 个状态
本博客只讨论与零状态可达的状态。
（2）算法描述：
- 预处理：从零状态开始，使用BFS遍历每个状态，在遍历的同时，给每个状态标记遍历的层号（零状态为第0层），即代价。为防止重复遍历某些状态，使用一个字典保存遍历过的状态及其对应层号，即 q_tab={s1:c1, s2:c2, ..., s181440:c181440}。
- 归位：在q_tab 中查找与当前状态相连的状态的代价，选择代价最小的状态作为下一步决策。
项目打包->三阶数字华容道最优解（更新版）
项目界面
2 实验
笔者工作空间如下：
2.1 数据预处理
通过 BFS 构建 q_tab 表，即“状态->代价”映射表
Generator.py
import numpy as np
class Generator:
def __init__(self):
self.n=3 #棋盘阶数
self.N=self.n*self.n #棋盘中棋子个数（包含空格）
self.dict={} #用于判重
self.que_qi=[] #用于广度优先搜索中，辅助队列(存储棋盘)
self.que_bk=[] #用于广度优先搜索中，辅助队列（存储空格）
self.que_lv=[] #用于广度优先搜索中，辅助队列（存储层数）
self.deep=31 #遍历深度
self.X=[-1,-self.n,1,self.n] #棋子移动方位
self.qi_init="" #初始棋盘布局
for i in range(1,self.N+1):
self.qi_init+=str(i)
def move(self,qi,blank,x,level): #将空格 blank 移向 x 位置
if x<0 or x>=self.N or blank==x:
return
if abs(blank%self.n-x%self.n)>1:
return
if blank<x:
temp=qi[:blank]+qi[x]+qi[blank+1:x]+qi[blank]+qi[x+1:]
else:
temp=qi[:x]+qi[blank]+qi[x+1:blank]+qi[x]+qi[blank+1:]
if temp in self.dict:
return
self.dict[temp]=level+1
self.que_qi=[temp]+self.que_qi
self.que_bk=[x]+self.que_bk
self.que_lv=[level+1]+self.que_lv
def bfs(self): #广度优先搜索
self.que_qi=[self.qi_init]+self.que_qi
self.que_bk=[self.N-1]+self.que_bk
self.que_lv=[0]+self.que_lv
self.dict[self.qi_init]=0
lv=0
while lv<self.deep and self.que_qi!=[]:
qi=self.que_qi.pop()
bk=self.que_bk.pop()
lv=self.que_lv.pop()
direction=np.random.permutation(4) #生成0~3的随机排列
for i in direction:
x=bk+self.X[i]
self.move(qi,bk,x,lv)
def save_jie3(self): #保存样本数据
num=len(self.dict)
data=np.zeros((num,self.N))
label=np.zeros(num)
i=0
for k in self.dict:
label[i]=self.dict[k]
for j in range(self.N):
data[i][j]=float(k[j])
i+=1
np.savez("jie3.npz",data=data,label=label)
def save_q_tab(self): #保存Query表
k=list(self.dict.keys())
v=list(self.dict.values())
np.savez("q_tab.npz",k=k,v=v)
def save_txt(self): #保存为TXT文档
file=open("jie3.txt",'w')
s=""
for k in self.dict:
v=self.dict[k]
for i in range(self.N):
s+=k[i]+' '
s+=str(v)+'\n'
file.write(s)
file.flush()
file.close()
gen=Generator()
gen.bfs()
gen.save_jie3()
gen.save_q_tab()
gen.save_txt()
运行 Generator.py 文件后，生成 q_tab.npz 和 jie3.txt 两个文件。q_tab.npz 保存了“状态 -> 代价”的映射，jie3.txt 的部分内容如下：
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 9 7 8 6 1
1 2 3 4 5 6 7 9 8 1
1 2 9 4 5 3 7 8 6 2
1 2 3 4 9 5 7 8 6 2
1 2 3 4 5 6 9 7 8 2
1 2 3 4 9 6 7 5 8 2
1 9 2 4 5 3 7 8 6 3
....................
9 8 7 6 5 4 3 2 1 28
....................
6 8 7 2 5 1 3 4 9 30
6 4 9 8 5 7 3 2 1 30
6 4 7 8 5 9 3 2 1 31
8 6 7 2 5 4 3 9 1 31
状态[[9,8,7],[6,5,4],[3,2,1]] 竟然不是最难的状态，最难的状态只有2个，只需31步，并且这2个状态还不对称，还挺有趣的。
最难的2个棋盘状态
笔者统计了一下，代价均值：21.97，中位数：22（出现23952次），众数：24（出现24047次）
代价分布图如下：
2.2 归位
（1）预测下一步的方向
Prediction.py
import numpy as np
class Prediction:
def __init__(self):
self.n=3
self.N=self.n*self.n
q_tab=np.load('q_tab.npz')
k=q_tab['k']
v=q_tab['v']
self.q_tab=dict(zip(k,v)) #构建Q表
self.X=[-1,0,1,0]
self.Y=[0,-1,0,1]
def pre_step(self,x): #预测状态 x 对应的步数
x=x.reshape(1,-1)
k=""
for i in range(self.N):
k+=str(x[0,i])
v=self.q_tab.get(k,-1)
return v
def pre_next(self,sta,bk_x,bk_y,bk_x_p,bk_y_p): #预测下一步往哪个方向走
step=[10000,10000,10000,10000]
direction=np.random.permutation(4) #生成0~3的随机排列
for i in direction:
x=bk_x+self.X[i]
y=bk_y+self.Y[i]
if x<0 or x>=self.n or y<0 or y>=self.n or x==bk_x_p and y==bk_y_p:
continue
t=sta[x][y]
sta[x][y]=self.N
sta[bk_x][bk_y]=t
step[i]=self.pre_step(sta)
sta[x][y]=t
sta[bk_x][bk_y]=self.N
return np.argmin(step)
（2）棋盘逻辑类
Qipan.py
import numpy as np
from Prediction import Prediction
class Qipan:
def __init__(self):
self.n=3
self.N=self.n*self.n
self.init=np.arange(1,self.N+1).reshape(self.n,self.n)
self.qipan=self.init.copy()
self.bk_x=self.n-1
self.bk_y=self.n-1
self.bk_x_p=-1
self.bk_y_p=-1
self.pre=Prediction()
self.started=False #标记是否开始
self.X=[-1,0,1,0]
self.Y=[0,-1,0,1]
def make_qipan(self): #生成随机棋盘
max_step=np.random.randint(40000,80000) #随机生成移动棋子步数
step=0
while step<max_step or self.qipan[self.n-1][self.n-1]!=self.N:
i=np.random.randint(4)
x=self.bk_x+self.X[i]
y=self.bk_y+self.Y[i]
self.move(x,y)
step+=1
self.bk_x_p=-1
self.bk_y_p=-1
self.step=0 #提示计步
self.started=True #标记是否开始
def move(self,x,y): #移动棋子
if x<0 or x>=self.n or y<0 or y>=self.n:
return
self.qipan[self.bk_x][self.bk_y]=self.qipan[x][y]
self.qipan[x][y]=self.N
self.bk_x_p=self.bk_x
self.bk_y_p=self.bk_y
self.bk_x=x
self.bk_y=y
def is_finish(self): #判断游戏是否结束
for i in range(self.n):
for j in range(self.n):
if self.qipan[i][j]!=self.init[i][j]:
return False
return True
def show(self): #打印当前棋盘状态
s=""
for i in range(self.n):
for j in range(self.n):
if self.qipan[i][j]==self.N:
s+=" "
else:
s+=str(self.qipan[i][j])+" "
s+="\n"
print(s)
def tips(self): #提示一步
i=self.pre.pre_next(self.qipan,self.bk_x,self.bk_y,self.bk_x_p,self.bk_y_p)
x=self.bk_x+self.X[i]
y=self.bk_y+self.Y[i]
self.move(x,y)
self.step+=1
print("step",self.step)
self.show()
（3）棋盘显示类
img目录里的图片
MyFrame.py
import wx
from Qipan import Qipan
import threading
import time
class MyFrame(wx.Frame):
def __init__(self,parent=None,id=-1):
wx.Frame.__init__(self,parent,id,title='数字华容道',size=(370,450))
panel=wx.Panel(self)
self.qipan=Qipan()
self.bt_start=wx.Button(panel,size=(80,45),label='开始')
self.bt_start.Bind(wx.EVT_BUTTON,self.OnClickStart)
self.label_step=wx.StaticText(panel,label="0")
font_lab=wx.Font(18,wx.DEFAULT,wx.FONTSTYLE_NORMAL,wx.NORMAL)
self.label_step.SetFont(font_lab)
hsizer=wx.BoxSizer(wx.HORIZONTAL)
hsizer.Add(self.bt_start,proportion=0,flag=wx.RIGHT|wx.ALIGN_CENTER,border=100)
hsizer.Add(self.label_step,proportion=0,flag=wx.ALL|wx.ALIGN_CENTER,border=20)
grid_sizer=wx.GridSizer(3,3,2,2) #3*3网格，组件边界为2
base_path='..\\img\\q_'
self.img_id=[]
self.bmp_qi=[]
for i in range(self.qipan.n):
img_t=[]
bmp_t=[]
for j in range(self.qipan.n):
img_t+=[wx.Image(base_path+str(i*self.qipan.n+j+1)+'.png', wx.BITMAP_TYPE_PNG).Rescale(100, 100).ConvertToBitmap()]
bmp_t+=[wx.StaticBitmap(panel,-1,img_t[j])]
grid_sizer.Add(bmp_t[j],0)
self.img_id+=[img_t]
self.bmp_qi+=[bmp_t]
vsizer=wx.BoxSizer(wx.VERTICAL)
vsizer.Add(hsizer,0,wx.ALIGN_CENTER|wx.ALIGN_TOP)
vsizer.Add(grid_sizer,0,wx.ALIGN_CENTER)
panel.SetSizer(vsizer)
def OnClickStart(self,event):
if self.qipan.is_finish(): #开局
self.qipan.make_qipan()
self.draw()
self.label_step.SetLabel(str(self.qipan.step))
threading.Thread(target=self.demo).start()
self.bt_start.SetLabel("暂停")
elif not self.qipan.started: #开始
self.qipan.started=True
self.bt_start.SetLabel("暂停")
else: #暂停
self.qipan.started=False
self.bt_start.SetLabel("开始")
def update(self):
while self.qipan.started==False:
time.sleep(0.2)
self.qipan.tips()
x=(self.qipan.qipan[self.qipan.bk_x_p][self.qipan.bk_y_p]-1)//self.qipan.n
y=(self.qipan.qipan[self.qipan.bk_x_p][self.qipan.bk_y_p]-1)%self.qipan.n
self.bmp_qi[self.qipan.bk_x_p][self.qipan.bk_y_p].SetBitmap(self.img_id[x][y])
self.bmp_qi[self.qipan.bk_x][self.qipan.bk_y].SetBitmap(self.img_id[self.qipan.n-1][self.qipan.n-1])
self.label_step.SetLabel(str(self.qipan.step))
def demo(self):
while self.qipan.is_finish()==False:
time.sleep(0.8)
self.update()
print("success!")
self.qipan.started=False
self.bt_start.SetLabel("开始")
def draw(self):
for i in range(self.qipan.n):
for j in range(self.qipan.n):
x=(self.qipan.qipan[i][j]-1)//self.qipan.n
y=(self.qipan.qipan[i][j]-1)%self.qipan.n
self.bmp_qi[i][j].SetBitmap(self.img_id[x][y])
app=wx.App()
frame=MyFrame()
img=wx.Image()
frame.Show()
app.MainLoop()
演示
本项目采用多线程实现：主线程负责监听用户动作（点击“开始/暂停”按钮），子线程负责棋盘更新。
3 改进
受强化学习中DQN学习Q表的启发，笔者尝试使用神经网络映射 q_tab 表。基于神经网络的方法和使用 q_tab 表差不多，主要差别是：在预处理阶段，加了神经网络训练；在归位时，不在q_tab 表中查找代价，而是在神经网络中映射代价。神经网络的网络参数空间为2041KB，q_tab 表的空间为7088KB，这样节省了不少内存空间。
样本、DNN参数、q_tab
笔者使用5层 DNN 训练“状态->代价”网络，网络参数：(9500+500)+(500500+500)+(500500+500)+(50032+32)=522,032个参数，学习率为0.002，迭代200次，得到准确率为90%，均方差为0.4。笔者尝试过采用CNN训练，但效果并不好，可能是因为图像中，连续几个像素有误对预测影响不大，但棋盘状态某个维度稍有变动，对代价影响较大。考虑到当前状态与零状态之间的距离和代价存在相关性，笔者尝试了RBF网络，但效果仍不理想。
DNN 网络结构
（1）训练DNN
DNN.py
import tensorflow as tf
import numpy as np
from keras.utils import to_categorical
class DNN:
def __init__(self,data,label,lr=0.01,train_step=1000):
self.n=3 #阶数
self.N=self.n*self.n #棋子个数（包含空格）
self.data=data #训练集
self.label=to_categorical(label) #标签(one_hot编码)
self.size=len(label) #训练集大小
self.batch_size=425 #训练批次大小
self.batch_num=self.size//self.batch_size+1 #训练批次数
self.lr=lr #学习率
self.train_step=train_step #训练步数
#生成每一批次的样本
def next_batch(self,batch_size):
index=np.random.randint(0,self.size,batch_size)
return self.data[index],self.label[index]
#初始化权值函数
def weight_variable(self,shape):
initial=tf.truncated_normal(shape,stddev=0.1)
return tf.Variable(initial)
#初始化偏置值函数
def bias_vairable(self,shape):
initial=tf.constant(0.1,shape=shape)
return tf.Variable(initial)
def train(self):
x=tf.placeholder(tf.float32,[None,9])
y=tf.placeholder(tf.float32,[None,32])
w_fc1=self.weight_variable([9,500])
b_fc1=self.bias_vairable([500])
w_fc2=self.weight_variable([500,500])
b_fc2=self.bias_vairable([500])
w_fc3=self.weight_variable([500,500])
b_fc3=self.bias_vairable([500])
w_fc4=self.weight_variable([500,32])
b_fc4=self.bias_vairable([32])
h_fc1=tf.nn.tanh(tf.matmul(x,w_fc1)+b_fc1)
h_fc2=tf.nn.sigmoid(tf.matmul(h_fc1,w_fc2)+b_fc2)
h_fc3=tf.nn.relu(tf.matmul(h_fc2,w_fc3)+b_fc3)
h_fc4=tf.matmul(h_fc3,w_fc4)+b_fc4
loss=tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits_v2(labels=y,logits=h_fc4))
train=tf.train.AdamOptimizer(self.lr).minimize(loss)
accuracy=tf.reduce_mean(tf.cast(tf.equal(tf.argmax(h_fc4,1),tf.argmax(y,1)),tf.float32))
mse=tf.reduce_mean(tf.cast(tf.square(tf.argmax(h_fc4,1)-tf.argmax(y,1)),tf.float32))
init=tf.global_variables_initializer()
with tf.Session() as sess:
sess.run(init)
x_test,y_test=self.next_batch(50000)
for epoch in range(self.train_step):
for i in range(self.batch_num):
x_,y_=self.next_batch(self.batch_size)
sess.run(train,feed_dict={x:x_,y:y_})
acc,m=sess.run([accuracy,mse],feed_dict={x:x_test,y:y_test})
print("epoch:",epoch,"accuracy:",acc,"mse:",m)
self.w_fc1,self.b_fc1,self.w_fc2,self.b_fc2,self.w_fc3,self.b_fc3,self.w_fc4,self.b_fc4=\
sess.run([w_fc1,b_fc1,w_fc2,b_fc2,w_fc3,b_fc3,w_fc4,b_fc4],feed_dict={x:x_test,y:y_test})
def predict(self,x):
h_fc1=tf.nn.tanh(tf.matmul(x,self.w_fc1)+self.b_fc1)
h_fc2=tf.nn.sigmoid(tf.matmul(h_fc1,self.w_fc2)+self.b_fc2)
h_fc3=tf.nn.relu(tf.matmul(h_fc2,self.w_fc3)+self.b_fc3)
h_fc4=tf.matmul(h_fc3,self.w_fc4)+self.b_fc4
pre=tf.argmax(h_fc4,1)
with tf.Session() as sess:
pre=sess.run(pre)
return pre
def save_para(self):
np.savez("jie3_dnn.npz",w_fc1=self.w_fc1,b_fc1=self.b_fc1,w_fc2=self.w_fc2,b_fc2=self.b_fc2,\
w_fc3=self.w_fc3,b_fc3=self.b_fc3,w_fc4=self.w_fc4,b_fc4=self.b_fc4)
temp=np.load('jie3.npz')
data=temp['data']
label=temp['label']
dnn=DNN(data,label,0.002,200)
dnn.train()
dnn.save_para()
x=np.array([[1,2,3,4,5,9,7,8,6]],dtype='float32')
step=dnn.predict(x)
（2）预测
Prediction.py
import numpy as np
import tensorflow as tf
class Prediction:
def __init__(self):
self.n=3
self.N=self.n*self.n
temp=np.load('jie3_dnn.npz')
self.w_fc1=temp['w_fc1']
self.b_fc1=temp['b_fc1']
self.w_fc2=temp['w_fc2']
self.b_fc2=temp['b_fc2']
self.w_fc3=temp['w_fc3']
self.b_fc3=temp['b_fc3']
self.w_fc4=temp['w_fc4']
self.b_fc4=temp['b_fc4']
self.X=[-1,0,1,0]
self.Y=[0,-1,0,1]
def pre_step(self,x):
x=x.reshape(1,-1).astype('float32')
h_fc1=tf.nn.tanh(tf.matmul(x,self.w_fc1)+self.b_fc1)
h_fc2=tf.nn.sigmoid(tf.matmul(h_fc1,self.w_fc2)+self.b_fc2)
h_fc3=tf.nn.relu(tf.matmul(h_fc2,self.w_fc3)+self.b_fc3)
h_fc4=tf.matmul(h_fc3,self.w_fc4)+self.b_fc4
pre=tf.argmax(h_fc4,1)
with tf.Session() as sess:
pre=sess.run(pre)
return pre
def pre_next(self,sta,bk_x,bk_y,bk_x_p,bk_y_p):
step=[10000,10000,10000,10000]
for i in range(4):
x=bk_x+self.X[i]
y=bk_y+self.Y[i]
if x<0 or x>=self.n or y<0 or y>=self.n or x==bk_x_p and y==bk_y_p:
continue
t=sta[x][y]
sta[x][y]=self.N
sta[bk_x][bk_y]=t
step[i]=self.pre_step(sta)
sta[x][y]=t
sta[bk_x][bk_y]=self.N
return np.argmin(step)
声明：本文转自三阶数字华容道最优解
![[前端也需要学一点设计]_色彩篇_如何创建色盘](https://img2022.cnblogs.com/blog/1735896/202204/1735896-20220428143452046-666091067.png)
