三阶数字华容道最优解

#三阶数字华容道最优解| 来源: 网络整理| 查看: 265

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=self.N or blank==x: return if abs(blank%self.n-x%self.n)>1: return if blank

【本文地址】

公司简介

联系我们