金博体育搬运工问题及其特点,搬运工,大自然的搬运工,搬运工找工作,搬运工图片,u盘搬运工,搬运工招聘,上海搬运工招聘信息,搬运工电影,搬运工培训,优盘搬运工

　　搬运工问题及其特点搬运工问题的启示 搬运工问题及其特点在对状态空间搜索算法有一定了解之后我们来看看我们的搬运工问题究竟用什么 方法比较好呢让我们先来看看该问题的特点搬运工问题我们在前面已经介绍过 搬运工问题这里我只是想提一些和解题有关的注意事项首先我们考虑的搬运工 问题的地图规模最大是 2020 这已经可以满足大部分关卡了为了以后讨论方便我 们把地图加以编号从左往右各列称为ABC 而从上往下各行叫abc 而由于不推箱子 时的走路并不重要我们在记录解的时候忽略了人的位置和移动只记录箱子的移 动人的动作很容易根据箱子的动作推出来下面是包含解答的标准关卡第一关呵 呵怎么样第一关都要那么多步啊以后的各关可是越来越难搬运工问题的特点我 在前言里吹了这么半天我想你即使以前没有玩现在也已经玩过了吧有什么感觉 呢是不是变化太多了不好把握不仅人不好把握连编程序也变得困难了很多我们 不妨拿它与经典的8 数码问题作一个比较1 死锁初学者很快就会学到什么是死锁 一旦他她把一个箱子推到角上显然这样的布局再继续玩下去是没戏了不管以后怎么推都不可能把这个箱子推离那个角不少玩家都总结了不少死锁的经验但 是要比较系统的解决这个问题并不是一件容易的事我们将用整整一章其实也不 长啦的篇幅来分析这个问题典型的死锁想一想为什么我们再看一下 数码问题它没有死锁因为每一步都是可逆的在这一点上搬运工问题要令人头疼得多了容 易看出这样的状态空间不是无向图而是有向图2 状态空间8 数码问题每次最多有 中移动方法最多的步数也只有几十步而搬运工问题呢困难一点的关卡可以是一步有100 多种选择整个解答包括600 多次推箱子动作分支因子和解答树深度都 这么大状态空间自然就非同小可了 数码问题有很多不错的下界函数如离家距离和但是搬运工问题又怎么样呢我们不能直接计算离家距离因为谁的家是哪儿都不 清楚很自然我们可以做一个二分图的最佳匹配但是这个下界怎么样呢 准确性对于 及其变种来说下界与实际代价越接近一般来说算法效率就越高我们这个最佳匹配只是理想情况但是事实上在很多情况下箱子相互制约不得已离开目标 路线来为其他箱子腾位置的事情是非常普遍的例如我们的标准关卡第 50 关有的 箱子需要从目标格子穿过并离开它来为其它箱子让路我们的下界函数返回值是 100 但是目前的最好结果是370 多么大的差别b 效率由于下界函数是一个调用非 常频繁的函数其效率不容忽视最佳匹配的时间渐进复杂度大约是ON3 数码的下界函数不知大了多少我们将会在后面给出一些改进方法但是其本质不会改变 如何解决搬运工问题已经有人证明了搬运工问题是 NP-Hard 看来我们还是考虑 搜索吧回想一下上一节提到过的状态空间搜索用哪一种比较好呢既然是智力游 戏可用的启发式信息是非常丰富了我们不仅是要用而且要用得尽量充分所以应 该用启发式搜索而前面已经提到了搬运工问题的状态空间是非常大的 是没有办法了因此我们选择了 IDA 算法实现简单空间需求也少既然搬运工问题这么难 为什么有那么多人都解决了相当数量的关卡呢标准的 90N 年以前就被人们模透 了因为人聪明嘛他们会预测会安排会学习有直觉的帮助还有一定的冒险精神他 们也包括我啦呵呵常用的是一些高层次的解题策略既有效又灵活 Srbga 想学吗 Readers 当然想可惜这些策略不是那么简单易学也不是很有规律的在后面的章 节中我将尽力模仿人的思维方式给我们的程序加入尽量多的智能