标题:用状态空间法求解9-宫图问题的理论研究
作者:韩爱丽
作者机构:[韩爱丽] 山东大学威海分校计算机系, 威海, 山东 264209, 中国
来源:山东大学学报. 工学版
出版年:2004
卷:34
期:4
页码:51-54
关键词:智能计算; 状态空间; 9-宫图
摘要:对用状态空间法求解9-宫图问题时的状态变化规律进行研究.通过研究发现,对于9-宫图问题的任意实例,当其逆序数为偶数时,状态总是由逆序数为偶数的一 个状态到达逆序数为偶数的另一个状态,并且总能在有限步内把棋子按次序排列好;当其逆序数为奇数时,状态总是由逆序数为奇数的一个状态到达逆序数为奇数的 另一个状态,并且总是不能把棋子按次序排列好,但总能到达状态12345687.通过理论证明,指出9-宫图问题的状态空间由两个连通分支组成:逆序数为 偶数的连通分支E和逆序数为奇数的连通分支O.若9-宫图实例的初始状态和目标状态位于不同的连通分支,则实例无解;若9-宫图实例的初始状态和目标状态 位于同一连通分支,则必可在有限步内求得实例的解.
收录类别:CSCD
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=SDGY200404012&DbName=CJFQ2004
TOP