文档章节

分支限界---->15-谜问题

小强斋太
 小强斋太
发布于 2016/11/09 20:08
字数 401
阅读 141
收藏 0

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转换成目标状态所需的最小移动数。故,令

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

四、例子

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/18/5637082.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
算法设计与分析复习——第六章:分支先结法

第六章:分支先结法 1,请简述分支限界法的算法思想以及两种主要的实现方法。 答:分支限界法的算法思想是在问题的解空间树上以广度优先或最小耗费(最大效益)优先方式搜索问题的满足约束条...

科技小能手
2017/11/12
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
五大常用算法:分治、动态规划、贪心、回溯、分支限界

分治:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 http://www.cnblogs.com/ste...

毛朱
2015/09/11
2.5K
0
回溯算法之购物车(0-1 背包问题)

1、问题(参考趣学算法) 2、分析 3、代码实现 #include include using namespace std; define MAX_NUM 200 //商品的个数,载物车最大承受重量int n = 0, W = 0;//当前载物车里面的总重量和总...

u011068702
05/10
0
0
算法设计策略----回溯法和分枝限界法

显示约束和解空间:规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题,显示约束规定了所有可能的元组,他们组成问题的候选解集,被称为该问题实例的解空间。 隐式约束和判定函数...

Superheros
03/10
5
0

没有更多内容

加载失败,请刷新页面

加载更多

区块链入门教程以太源码分析accounts包简介

兄弟连区块链教程以太源码分析accounts包简介 accounts包实现了eth客户端的钱包和账户管理。 账号的数据结构: typeAccount struct {Address common.Address `json:"address"` // Ether...

兄弟连区块链入门教程
21分钟前
0
0
sed命令详解及运用

10月17日任务 9.4/9.5 sed 9.3、正则介绍 - sed命令(上) sed是流编辑器,默认不编辑源文件,是以行为单位从源文件抽取数据,进而处理再输出于屏幕上;可能有的人说那我直接vi不就好了嘛,但...

zgxlinux
23分钟前
0
0
iOS App “去评分” 功能的几种实现总结

通常 App 都会在它的设置页面或者关于页面添加一个“去评分”选项,或者在用户使用 App 过程中适当时机弹窗,引导用户跳转到 App Store 对当前 App 进行评分或者撰写评论。 绝大部分 App 实现...

秦无炎
28分钟前
0
0
Chrome 图片解码与 Image Decoding Hint

我在之前的一篇文章Chrome 图片解码与 Image.decode API,说明了为什么图片解码可能会导致非合成器动画的阻塞和如何使用 Image.decode API 来避免动画的阻塞。不过虽然 Image.decode API 给页...

全部原谅
28分钟前
0
0
java获取ip和地区

String s = HttpUtil.sendPost("http://pv.sohu.com/cityjson");JSONObject jsonObject = JSONObject.parseObject(s.substring(s.indexOf("{"), s.indexOf("}") + 1));jsonObject.get("c......

吴伟祥
30分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部