15-谜问题的可达性判定

摘要：

定义了15-谜问题的6个动作规则,在此基础上证明了15-谜问题解的存在性判定的充分必要条件,其充分性的证明过程是一个构造性证明方法,提供了求解15-谜问题的一个解的可实现算法;同时,对此结论进行了扩展,对于给定的一初始格局和任一目标格局,证明了初始格局可达目标格局的的充分必要条件,其结论有助于构造问题的状态空间与限界函数.这两个结论从理论上完全解决了15-谜问题,对获得最优算法提供了理论基础.

关键词：15-谜问题、格局、可达性、算法

所属期刊栏目：33

分类号：TP301.6(计算技术、计算机技术)

资助基金：四川省应用基础研究计划03226125

在线出版日期：2004-12-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：604-607