分支限界---->15-谜问题
分支限界---->15-谜问题
小强斋太 发表于1年前
分支限界---->15-谜问题
  • 发表于 1年前
  • 阅读 39
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

15-谜问题

一、问题描述

在一个分成16格的方形棋盘上放有15块编了号的牌。对于这些牌给定的一种初始排列,要求通过一系列的合法移动将初始排列转换成目标排列。

合法移动:每次将一个邻接于空格的牌移动到空格位置

(注:并不是所有的初始状态都能变换成目标状态的)

二、如何判定目标状态在初始状态的状态空间中?

1.记POSITION(i)为编号为i的牌在初始状态中的位置;POSITION(16)表示空格的位置。

POSITION(1:16)=(1,5,2,3,7,10,9,13,14,15,11,8,16,12,4,6)

2.记LESS(i)是这样牌j的数目:j<i,但POSITION(j)> POSITION(i),即编号小于i但初始位置在i之后的牌的数目。

   例:LESS(1)=0; LESS(4)=1; LESS(12)=6

3.引入一个量X

如图所示,初始状态时,若空格落在橙色方格上,则X=1:若空格落在白色方格上,则X=0。

4.目标状态是否在初始状态的状态空间中的判别条件:

当且仅当 是偶数时,目标状态可由此初始状态到达。

三、成本估计函数

(X)是由根到结点X的路径长度

 是以X为根的子树中由X到目标状态的一条最短路径长度的估计值——至少应是能把状态X转换成目标状态所需的最小移动数。故,令

               =不在其目标位置的非空白牌数目

四、例子

 

共有 人打赏支持
粉丝 0
博文 181
码字总数 0
×
小强斋太
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: