文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:08
字数 401
阅读 112
收藏 0
点赞 0
评论 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

游戏与常用的五大算法---下篇

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

loving_forever_ ⋅ 2017/01/08 ⋅ 0

五大常用算法:分治、动态规划、贪心、回溯、分支限界

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

毛朱 ⋅ 2015/09/11 ⋅ 0

回溯算法之购物车(0-1 背包问题)

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

u011068702 ⋅ 05/10 ⋅ 0

算法设计策略----回溯法和分枝限界法

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

Superheros ⋅ 03/10 ⋅ 0

动态规划和分治法,贪心算法以及递归的再一次深刻理解和体会

每次体会算法都有新的感觉,刷题越多,对算法的理解感觉也就越深刻。 下面我们来重新体会下分治法,动态规划,贪心法,递归的理解。 1.分治法: 将问题分成单独的阶段,每个阶段互相不干扰很...

qingliangdexiar ⋅ 2017/08/25 ⋅ 0

面试算法:线性表

链表 队列 堆栈 实践应用 难题首选[动归],受阻[贪心][暴力];考虑[分治]思想,配合[排序][哈希]; 动态规划:动态数组降低空间复杂度 贪心法:Dijkstra最短路径、最小生成树Prim、Kruskal算...

datacube ⋅ 2016/07/20 ⋅ 0

代码之谜 - 『序』其实,你不懂代码

2012年9月28日 13时32分 新增 最近看本文评论,争议很多,我先说说这篇文章的前世今生吧。 我原文标题是『代码之谜 - 开篇/前言/序』,副标题是『其实,你不懂代码』,本来打算用“其实,代码...

justjavac ⋅ 2012/11/02 ⋅ 4

代码之谜(零) - 其实,你不懂代码

2012年9月28日 13时32分 新增 最近看本文评论,争议很多,我先说说这篇文章的前世今生吧。 我原文标题是『代码之谜 - 开篇/前言/序』,副标题是『其实,你不懂代码』,本来打算用“其实,代码...

justjavac ⋅ 2012/09/26 ⋅ 5

DDD战术篇:领域模型的应用

领域驱动设计DDD在战术建模(后文简称建模,除非特别说明)上提供了一个元模型体系(如下图),通过这个元模型我们会对战略建模过程中识别出来的问题子域进行抽象,而通过抽象来指导最后的落...

ThoughtWorks中国 ⋅ 2017/11/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

005. 深入JVM学习—Java堆内存参数调整

1. JVM整体内存调整图解(调优关键) 实际上每一块子内存区域都会存在一部分可变伸缩区域,其基本流程:如果内存空间不足,则在可变的范围之内扩大内存空间,当一段时间之后,内存空间不紧张...

影狼 ⋅ 9分钟前 ⋅ 0

内存障碍: 软件黑客的硬件视图

此文为笔者近日有幸看到的一则关于计算机底层内存障碍的学术论文,并翻译(机译)而来[自认为翻译的还行],若读者想要英文原版的论文话,给我留言,我发给你。 内存障碍: 软件黑客的硬件视图...

Romane ⋅ 42分钟前 ⋅ 0

SpringCloud 微服务 (七) 服务通信 Feign

壹 继续第(六)篇RestTemplate篇 做到现在,本机上已经有注册中心: eureka, 服务:client、order、product 继续在order中实现通信向product服务,使用Feign方式 下面记录学习和遇到的问题 贰 or...

___大侠 ⋅ 59分钟前 ⋅ 0

gitee、github上issue标签方案

目录 [TOC] issue生命周期 st=>start: 开始e=>end: 结束op0=>operation: 新建issueop1=>operation: 评审issueop2=>operation: 任务负责人执行任务cond1=>condition: 是否通过?op3=>o......

lovewinner ⋅ 今天 ⋅ 0

浅谈mysql的索引设计原则以及常见索引的区别

索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索...

屌丝男神 ⋅ 今天 ⋅ 0

String,StringBuilder,StringBuffer三者的区别

这三个类之间的区别主要是在两个方面,即运行速度和线程安全这两方面。 首先说运行速度,或者说是, 1.执行速度 在这方面运行速度快慢为:StringBuilder(线程不安全,可变) > StringBuffer...

时刻在奔跑 ⋅ 今天 ⋅ 0

java以太坊开发 - web3j使用钱包进行转账

首先载入钱包,然后利用账户凭证操作受控交易Transfer进行转账: Web3j web3 = Web3j.build(new HttpService()); // defaults to http://localhost:8545/Credentials credentials = Wallet......

以太坊教程 ⋅ 今天 ⋅ 0

Oracle全文检索配置与实践

Oracle全文检索配置与实践

微小宝 ⋅ 今天 ⋅ 0

mysql的分区和分表

1,什么是mysql分表,分区 什么是分表,从表面意思上看呢,就是把一张表分成N多个小表,具体请看mysql分表的3种方法 什么是分区,分区呢就是把一张表的数据分成N多个区块,这些区块可以在同一...

梦梦阁 ⋅ 今天 ⋅ 0

exception.ZuulException: Forwarding error

错误日志 com.netflix.zuul.exception.ZuulException: Forwarding error Caused by: com.netflix.hystrix.exception.HystrixRuntimeException: xxx timed-out and no fallback available. Ca......

jack_peng ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部