C++ 做小游戏 推箱子中的问题 求大神。_c++吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：149,006贴子：
C++ 做小游戏 推箱子中的问题 求大神。收藏
这磨人的老汉推箱！！
//点class CPoint{int x,y;public:CPoint(){}CPoint(int x, int y){this-&x =this-&y =}public:void setX(int x){this-&x =}void setY(int y){this-&y =}int getX(){}int getY(){}};//精灵类class CSprite : public CPoint{public:CSprite(){}string strSvirtual void drawSHAPE(){cout && strS}};//人物类class CPlayer : public CSprite{public:CPlayer(){strShape = &♀&;}virtual void drawSHAPE(){cout && strS}};//箱子类class CBox : public CSprite{public:CBox(){strShape = &■&;}virtual void drawSHAPE(){cout && strS}};//墙类class CWall : public CSprite{public:CWall(){strShape = &¤&;}virtual void drawSHAPE(){cout && strS}};//空地类class CSpace : public CSprite{public:CSpace(){strShape = &□&;}virtual void drawSHAPE(){cout && strS}};//目的地类class CDest : public CSprite{public:CDest(){strShape = &●&;}virtual void drawSHAPE(){cout && strS}};//地图类class CMap{CSprite *m_map[10][10];//地图大小public:void initMAP(){int i = 0;int j = 0;for (i = 0; i & 10; i++){for (j = 0; j & 10; j++){if (i == 7 && j == 8){m_map[i][j] = new CPm_map[i][j]-&setX(i);m_map[i][j]-&setY(j);m_map[i][j]-&strShape = &♀&;}else if (i == 5 && j == 6 || i == 6 && j == 4 || i == 3 && j ==9){m_map[i][j] = new CBm_map[i][j]-&setX(i);m_map[i][j]-&setY(j);m_map[i][j]-&strShape = &■&;}else if (i == 8 && j == 9 || i ==0 && j == 3 || i == 9 && j == 9){m_map[i][j] = new CDm_map[i][j]-&setX(i);m_map[i][j]-&setY(j);m_map[i][j]-&strShape = &●&;}else if (i == 6 && j == 3){m_map[i][j] = new CWm_map[i][j]-&setX(i);m_map[i][j]-&setY(j);m_map[i][j]-&strShape = &¤&;}else{m_map[i][j] = new CSm_map[i][j]-&setX(i);m_map[i][j]-&setY(j);m_map[i][j]-&strShape = &□&;}}}}bool isWall(int x, int y)//是否为墙{bool bWall =if (m_map[x][y]-&strShape == &¤&){bWall =}return bW}CSprite *getplayer(){int i = 0;int j = 0;for (i = 0; i & 10; i++){for (j = 0; j & 10; j++){if (m_map[i][j]-&strShape == &♀&){return m_map[i][j];}}}}~CMap(){int i = 0;int j = 0;for (i = 0; i & 10; i++){for (j = 0; j & 10; j++){if (m_map[i][j]){delete []m_map[i][j];}}}}bool isBox(int x, int y)//是否为箱子{bool bBox =if (m_map[x][y]-&strShape == &■&){bBox =}return bB}bool isDest(int x, int y){bool bDest =if (m_map[x][y]-&strShape == &●&){bDest =}return bD}void drawMap(){int i = 0;int j = 0;for (i = 0; i & 10; i++){for (j = 0; j & 10; j++){if (isBox(i, j) && isDest(i, j)){cout && &◎&;}else{cout && m_map[i][j]-&strS}if (j == 9){cout &&}}}}void PlayerLogic(){char ch = (char)_getch();switch (ch){case *w*://y-1{if (getplayer()-&getY() != 0){int x = getplayer()-&getX();int y = getplayer()-&getY();int b = y - 1;CSprite *p = m_map[x][b];//人物坐标存储m_map[x][b] = m_map[x][y];//人物等于空格（）m_map[x][y] =//空格（）等于人物m_map[x][y]-&setY(y);//人物、空格（） 坐标交换}}case *s*://y+1if (getplayer()-&getY() != 9){//int x = getplayer()-&getX();//int y = getplayer()-&getY();//getplayer()-&setY(y+1);//m_map[y][x]-&strShape = m_map[y+1][x]-&strS//m_map[y+1][x]-&strShape = &♀&;}case *a*://x-1case *d*://x+1}}};
问题在w中 人物向上移动int x = getplayer()-&getX();int y = getplayer()-&getY();int b = y - 1;CSprite *p = m_map[x][b];//人物坐标存储m_map[x][b] = m_map[x][y];//人物等于空格（）m_map[x][y] =//空格（）等于人物m_map[x][y]-&setY(y);//人物、空格（） 坐标交换调试中按w只会向左！然后又向右(掀桌）！调试挺久的找不到问题在哪。。
我有现成的，要么
--云在青天，水在瓶底;
鱼得水游，鸟乘风飞; 盛衰无常，强弱安在…
“多年没用了 手好像有的生”（结印、咆哮）大·挽尊术！
登录百度帐号我的游戏推荐游戏
后查看最近玩过的游戏
为兴趣而生，贴吧更懂你。或5:21:47【 转载互联网】 作者： &&|&责编：李强
&&& &为了解决用户可能碰到关于"推箱子如何解？"相关的问题，突袭网经过收集整理为用户提供相关的解决办法，请注意，解决办法仅供参考，不代表本网同意其意见,如有任何问题请与本网联系。"推箱子如何解？"相关的详细问题如下:RT,我想知道:推箱子如何解？===========突袭网收集的解决方案如下===========
解决方案1：无解！中间那个区域只有9个箱子但有10个目标点，其他箱子无法推到那个区域！解决方案2：是啊！软件错了。解决方案3：太给力了，你的回答完美地解决了我的问题，非常感谢！解决方案4：上上下下左右左右ABAB
================可能对您有帮助================
答：请从左到右分别是123号箱子,1号箱子(绿点旁的那个)从下向上推一下,绕到它的右边向左推,在从上往下推至绿点. 3号箱子(最右),往左推2格,然后推2号箱子往左一格,绕一下把3号往右推一格,从下向上推至最上方的红点,2号向上一格,右一格,上一格~锵锵~~...===========================================答：上上下下左右左右ABAB===========================================答：右下右下下下下左左上上左上下右下下右右上上左右上上左下左下左左上右右右上右右下左下左左上右下右上左左左左下右右上右右下下下左左上上右上上上左左下下左下右右左上上上右右下下右右上左下左左下下下右右上上下下左左上上右左左左上右上上...===========================================问：11个箱子的，是我这个手机游戏的第101关，总共108关。答：这~~有哪个网址能玩玩，这，，，，谁知道行不行===========================================问：附图，求大神帮忙。本人太穷，分不多 拜谢了答：左左左上上右右右左左左下下右右右上下左左左上上右右下左右右右右上上左下右下左左下左左上上左左下下右右左左上右上右右右下右右上上左下右下左===========================================问：附图，求大神帮忙。本人太穷，分不多 拜谢了答：按照箱子位置命名：左边为1号，中上面为2号，中下面为3号，右边为4号。 首先，推4号到底，4号进入。 第二，往左走，来到2、3号之间，推2号到底，2号进入。 第三，退回来，推3号到底，3号进入。 第四，来到1号左边，往右推一格，绕路来到1号下方...===========================================问：附图，求大神帮忙。本人太穷，分不多 拜谢了答：===========================================问：附图，求大神帮忙。本人太穷，分不多 拜谢了答：右右上右右下下左上左左左上右下右右右上上左下上上左左下下左下右上右上右右下左右下下左上下下左左上上右上下左左上右下右下右右上左右上上左下下右下左 是这关吧，不是这关贴图上来追问。===========================================问：已附图。答：推箱子13关图解/article/e8cdb32bbad3b.html===========================================
12345678910求蜗牛推箱子第10关解法_推箱子吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：677贴子：
求蜗牛推箱子第10关解法收藏
求蜗牛推箱子第10关解法
1楼 21:49&|来自
相关的贴子4917286303相关的图贴
2楼 11:14&|
这关说实话真没什么难度，我第一次就过去了，还有更简单的方法
3楼 09:20&|
登录百度帐号推荐应用
内&&容:使用签名档&&
为兴趣而生，贴吧更懂你。&或怎样使用计算机实现自动推箱子功能?怎样得到最优解?
[问题点数：100分，结帖人laofeng]
怎样使用计算机实现自动推箱子功能?怎样得到最优解?
[问题点数：100分，结帖人laofeng]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
相关帖子推荐：
2002年7月 PHP大版内专家分月排行榜第一2002年5月 PHP大版内专家分月排行榜第一2002年7月 C/C++大版内专家分月排行榜第一
2003年1月 PHP大版内专家分月排行榜第三2002年7月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。怎样使用计算机实现自动推箱子功能?怎样得到最优解?
主　　题：
怎样使用计算机实现自动推箱子功能?怎样得到最优解?
很想知道!有源码更好!up有分!
ninny(zstudio)
) 信誉：92
<font color="#02-06-24 14:13:35Z
得分:<font color="#
程序员三月份还是四月份有着这道题目，而且富有详细的代码，论坛上以前也有相关的帖子，你可以去找那本杂志或者艘原来的帖子
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-24 15:12:09Z
得分:<font color="#
"搬运工"是一个十分流行的单人智力游戏，玩家的任务是在一个仓库中操纵一个搬运工人
将N个相同的箱子推到N个相同的目的地。不清楚规则不要紧，玩一玩附件里的SokoMind就
知道了。我在里面加上了标准的测试关卡90关，幼儿关卡61关和文曲星170关，在以后的介
绍中，我们就用这些关来测试我们的程序，因此我建议你自己先试一试，看看你能过多少
因为本文内容不算少，在这里我先给大家提供一个小小的阅读建议。初学的朋友或者不知
道IDA*算法的朋友一定要从第一章开始阅读并弄懂，因为它是全文的基础。第二章很好懂
，大家只需要做一个了解，知道搬运工问题的难点在哪里，为什么我们选择了IDA*算法。
急于看程序的朋友可以先看看第三章，我们的第一个版本S4-Baby诞生了，接着是一系列的
改进措施，喜欢人工智能的朋友不妨认真看看，也许会找到灵感哦！最后是总结，和第一
章一样的重要，不要错过了。
我假定本文的读者已经对相关知识有一定了解，所以一般不给出很严格的定义或者论证，
只是粗略的提一下，语言尽量做到通俗易懂。但由于我的水平实在有限，错误之处一定不
少，恳请大家批评指正：）
一 状态空间搜索基本知识
1.状态空间(state space)
对于一个实际的问题，我们可以把它进行一定的抽象。通俗的说，状态(state)是对问题在
某一时刻的进展情况的数学描述，状态转移(state-transition)就是问题从一种状态转移
到另一种（或几种）状态的操作。如果只有一个智能体(Agent)可以实施这种状态转移，则
我们的目的是单一的，也就是从确定的起始状态(start state)经过一系列状态转移而到达
一个（或多个）目标状态(goal state)。
如果不止一个智能体可以操纵状态转移(例如下棋)，那么它们可能会朝不同的，甚至是对
立的目标进行状态转移。这样的题目不在本文讨论范围之内。
我们知道，搜索的过程实际是在遍历一个隐式图，它的结点是所有的状态，有向边对应于
状态转移。一个可行解就是一条从起始结点出发到目标状态集中任意一个结点的路径。这
个图称为状态空间(state space)，这样的搜索就是状态空间搜索(Single-Agent Search)
2.盲目搜索(Uninformed Search)
盲目搜索主要包括以下几种：
纯随机搜索(Random Generation and Random Walk)
听起来比较"傻"，但是当深度很大，可行解比较多，解的深度又不重要的时候还是有用的
，而且改进后的随机搜索可以对付解分布比较有规律（相对密集或平均，或按黄金分割比
例分布等）的题目。一个典型的例子是：你在慌乱中找东西的时候，往往都是进行随机搜
广度优先搜索(BFS)和深度优先搜索(DFS)
大家都很熟悉它们的时间效率，空间效率和特点了吧。广度优先搜索的例子是你的眼镜掉
在地上以后，你趴在地板上找：）- 你总是先摸最接近你的地方，如果没有，在摸远一点
的地方…深度优先搜索的典型例子是走迷宫。它们还有逆向和双向的搜索方式，但是不再
本文讨论范围之内。
重复式搜索
这些搜索通过对搜索树扩展式做一些限制，用逐步放宽条件的方式进行重复搜索。这些方
重复式深度优先(Iterative Deepening)
限制搜索树的最大深度Dmax,然后进行搜索。如果没有解就加大Dmax再搜索。虽然这样进行
了很多重复工作，但是因为搜索的工作量与深度成指数关系，因此上一次（重复的）工作
量比起当前的搜索量来是比较小的。这种方法适合搜索树总的来说又宽又深，但是可行解
却不是很深的题目（一般的深度优先可能陷入很深的又没有解的地方，广度优先的话空间
重复式广度优先(Iterative Broadening)
它限制的是从一个结点扩展出来的子节点的最大值Bmax,但是因为优点不是很明显，应用并
不多，研究得也比较少。
柱型搜索(Beam Search)
它限制的是每层搜索树节点总数的最大值Wmax。显然这样搜索树大小与深度成正比，但是
可能错过很接近起点的解，而增加Wmax的时候保留哪些节点，Wmax增加多少是当前正在研
究的问题。
3.启发式搜索(Informed Search)
我们觉得一些问题很有"想头"，主要是因为启发信息比较多，思考起来容易入手，但是却
不容易找到解。我们不愿意手工一个一个盲目的试验，同样也不愿意我们的程序机械的搜
索。也就是说，我们希望尽可能的挖掘题目自身的特点，让搜索智能化。下面介绍的启发
式搜索就是这样的一种智能化搜索方法。
在刚才的那些算法中，我们没有利用状态本身的信息，只是利用了状态转移来进行搜索。
事实上，我们自己在解决问题的时候常常会估计状态离目标到底有多接近，进而对多种方
案进行选择。把这种方法用到搜索中来，我们可以用一个状态的估价函数来估计它到目标
状态的距离。这个估价函数是和问题息息相关的，体现了一定的智能。为了以后叙述方便
，我们先介绍一些记号：
S 问题的任何一种状态
H*(s) s到目标的实际（最短）距离 - 可惜事先不知道：）
H(s) s的启发函数 - s到目标距离的下界，也就是h(s)&=h*(s),如果h函数对任意状态s1和
s2,还满足h(s1)&=h(s2)+c(s1,s2)（其中c(s1,s2)代表状态s1转移到s2的代价）,也就是状
态转移时，下界h的减少值最多等于状态转移的实际代价，我们说h函数是相容(consisten
t)的。(其实就是要求h不能减少得太快)
G(s) 到达s状态之前的代价，一般就采用s在搜索树中的深度。
F(s) s的估价函数，也就是到达目标的总代价的估计。直观上，应该
有f(s)=g(s)+h(s)，即已经付出的和将要付出的代价之和。如果g
是相容的，对于s1和它的后辈节点，有h(s1)&=h(s2)+c(s1,s2)
两边同时加上g(s1),有h(s1)+g(s1)&=h(s2)+g(s1)+c(s1,s2),也就是
f(s1)&=f(s2)。因此f函数单调递增。
启发式搜索用到的符号
贪心搜索(Best-First Search)
象广度优先搜索一样用一个队列储存待扩展，但是按照h函数值从小到大排序(其实就是优
先队列)。显然由于h估计的不精确性，贪心搜索不能保证得到的第一个解最优，而且可能
很久都找不到一个解。
和贪心搜索很类似，不过是按照f函数值进行排序。但是这样会多出一个问题：新生成的状
态可能已经遇到过了的。为什么会这样呢？由于贪心搜索是按照h函数值排序，而h只与状
态有关，因此不会出现重复，而f值不仅状态有关，还与状态转移到s的方式有关，因此可
能出现同一个状态有不同的f值。解决方式也很简单，如果新状态s1与已经遇到的状态s2相
同，保留f值比较小的一个就可以了。(如果s2是待扩展结点，是有可能出现f(s2)&f(s1)的
情况的，只有已扩展结点才保证f值递增)。A*算法保证得到最优解，但是所用的空间是很
大的，难以适应我们的搬运工问题。
既然A*算法存在空间问题，那么我们能不能借用深度优先搜索的空间优势，用重复式搜
索的方式来缓解危机呢？经过研究，Korf于1985年提出了一个Iternative Deepening A*(
IDA*)算法，比较好的解决了这一问题。一开始，我们把深度最大值Dmax设为起始结点的h
值，开始进行深度优先搜索，忽略所有f值大于Dmax的结点，减少了很多搜索量。如果没有
解，再加大Dmax的值，直到找到一个解。容易证明这个解一定是最优的。由于改成了深度
优先的方式，与A*比较起来，IDA*更加实用：
1. 不需要判重，不需要排序，只用栈就可以了。操作简单。
2. 空间需求大大减少，与搜索树大小成对数关系。
其他的启发式搜索
这些方法包括深度优先+最优剪枝式的A*，双向A*,但是由于很不成熟或者用处并不大，这
里就不介绍了。A*算法有一个加权的形式，由于在搬运工问题中效果不明显，这里从略。
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-24 15:22:48Z
得分:<font color="#
二 搬运工问题及其特点
在对状态空间搜索算法有一定了解之后，我们来看看我们的搬运工问题。究竟用什么方法
比较好呢？让我们先来看看该问题的特点。
1. 搬运工问题
我们在前面已经介绍过搬运工问题，这里我只是想提一些和解题有关的注意事项。首先，
我们考虑的搬运工问题的地图规模最大是20*20，这已经可以满足大部分关卡了。为了以后
讨论方便，我们把地图加以编号。从左往右各列称为A，B，C…，而从上往下各行叫a,b,c
…。而由于不推箱子时的走路并不重要，我们
在记录解的时候忽略了人的位置和移动，只记录箱子的移动。人的动作很容易根据箱子的
动作推出来。下面是包含解答的标准关卡第一关。
呵呵，怎么样，第一关都要那么多步啊…以后的各关，可是越来越难。
2. 搬运工问题的特点
我在前言里吹了这么半天，我想你即使以前没有玩，现在也已经玩过了吧：）。
有什么感觉呢？是不是变化太多了，不好把握？不仅人不好把握，连编程序也变得困难了
很多。我们不妨拿它与经典的8数码问题作一个比较。
初学者很快就会学到什么是死锁 - 一旦他（她）把一个箱子推到角上。显然，这样的布局
再继续玩下去是没戏了，不管以后怎么推都不可能把这个箱子推离那个角。不少玩家都总
结了不少死锁的经验，但是要比较系统的解决这个问题并不是一件容易的事。我们将用整
整一章（其实也不长啦）的篇幅来分析这个问题。
典型的死锁。想一想，为什么：）我们再看一下8数码问题。它没有死锁，因为每一步都是
可逆的。在这一点上，搬运工问题要令人头疼得多了。
容易看出，这样的状态空间不是无向图，而是有向图。
2.状态空间。
8数码问题每次最多有4中移动方法，最多的步数也只有几十步。而搬运工问题呢？困难一
点的关卡可以是一步有100多种选择，整个解答包括600多次推箱子动作。分支因子和解答
树深度都这么大，状态空间自然就非同小可了。
3.下界估计
在启发式搜索中，我们需要计算h值，也就是需要对下界进行估计。8数码问题有很多不错
的下界函数（如"离家"距离和），但是搬运工问题又怎么样呢？我们不能直接计算"离家"
距离，因为谁的家是哪儿都不清楚。很自然，我们可以做一个二分图的最佳匹配，但是这
个下界怎么样呢？
对于A*及其变种来说，下界与实际代价越接近，一般来说算法效率就越高。我们这个最佳
匹配只是"理想情况"，但是事实上，在很多情况下箱子相互制约，不得已离开目标路线来
为其他箱子腾位置的事情是非常普遍的。例如我们的标准关卡第50关，有的箱子需要从目
标格子穿过并离开它来为其它箱子让路。我们的下界函数返回值是100，但是目前的最好结
果是370。多么大的差别！
由于下界函数是一个调用非常频繁的函数，其效率不容忽视。最佳匹配的时间渐进复杂度
大约是O(N^3),比8数码的下界函数不知大了多少…我们将会在后面给出一些改进方法，但
是其本质不会改变。
3. 如何解决搬运工问题
已经有人证明了搬运工问题是NP-Hard，看来我们还是考虑搜索吧。回想一下上一节提到过
的状态空间搜索，用哪一种比较好呢？
既然是智力游戏，可用的启发式信息是非常丰富了，我们不仅是要用，而且要用得尽量充
分,所以应该用启发式搜索。而前面已经提到了，搬运工问题的状态空间是非常大的，A*是
没有办法了，因此我们选择了IDA*算法：实现简单，空间需求也少。
既然搬运工问题这么难，为什么有那么多人都解决了相当数量的关卡呢（标准的90N年以前
就被人们模透了）。因为人聪明嘛。他们会预测，会安排，会学习，有直觉的帮助，还有
一定的冒险精神。他们（也包括我啦，呵呵）常用的是一些"高层次"的解题策略，既有效
，又灵活。(Srbga:想学吗? Readers:当然想!!)可惜这些策略不是那么简单易学，也不是
很有规律的。在后面的章节中，我将尽力模仿人的思维方式给我们的程序加入尽量多的智
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-24 15:25:39Z
得分:<font color="#
三 用IDA*算法解搬运工问题
实现与改进
在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里，我们
将用IDA*算法来做一个解决搬运工问题的程序 - 虽然是我们的最初版本(我们称做S4-Bab
y)，但是不要小看它哦！
1 IDA*算法框架
由前所述，IDA*算法是基于重复式深度优先的A*算法，忽略所有f值大于深度限制的结点。
那么，我们不难写出IDA*算法框架的伪代码
伪代码1 - IDA*算法框架
procedure IDA_STAR(StartState)
PathLimit := H( StartState ) - 1;
Success := F
inc(PathLimit);
StartState.g:= 0;
Push(OpenStack,StartState);
CurrentState:=Pop(OpenStack);
If Solution(CurrentState) then
Success = True
Else if PathLimit &= CurrentState.g + H(CurrentState) then
Foreach Child(CurrentState) do
Push(OpenStack, Child(CurrentState));
until Success or empty(OpenStack);
until Success or ResourceLimitsR
这只是一个很粗略的框架，什么事情都不能做。不过我想大家可能比较急于试验一下IDA*
的威力，因此我们不妨就做一个最最基本的程序。
2. 第一个程序
要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。
输入输出文件格式
输入文件是一个文本文件，它由N行构成，每行是一些字符。
各种字符的含义是：
目标格子中的箱子
目标格子中的搬运工
表2 输入文件格式
这种格式和Xsokoban, SokoMind和Rolling Stone的格式是一致的，因此会比较方便一些。
输出文件第一行是推箱子的次数M，以下M行，每行的格式是：x y direction,代表把第x行
第y列的箱子往direction的方向推一步。Direction可以是left,right,up,down之中的一个
,1&=x,y&=20
由于是最初的版本，我们不必考虑这么多：只需要可行，编程方便就可以了，暂时不管它
的效率和其他东西。优化是以后的事。
我们定义新的数据类型BitString,MazeType,MoveType,StateType和IDAType。请大家看附
录中的程序，不难猜出它们的含义和用途。唯一需要说明的BitString类型。记录状态时，
我们把地图看成一个大数，一个格子是一个bit。那么所有箱子构成一个BitString,检查某
一个是否有箱子（或者目标，墙）时只需要检测对应位置上的bit是否为1。这样虽然会浪
费一些空间，但是判断会比较快，操作也比较简单。
我们把x,y坐标合并成一个"position"变量。其中Position=(x-1)*width+(y-1)。
我们用常量数组DeltaPos:array[0..3]表示上，下，左，右的Position增量。
为了简单起见，我们连最佳匹配也不做了，用所有箱子离最近目标的距离和作为下界函数
。不过，这里的"距离"是指推的次数，计算的时候（MinPush函数），只要忽略其它所有箱
子，然后用一次BFS就可以了。
嘿嘿，这个效果嘛，不说你也知道的，就是标准关一个也过不了啦。不过为了说明我的程
序是正确的，你可以试验一下幼儿关卡(共61关)嘛！
什么！第一关都就没有动静了…55555，生成了18万个结点???不过很多关都很快就过了的
。我们用1,000,000个结点为上限(在我的Celeron 300A上要运行十多分钟),得到以下的测
没有解决的几关是：51,52,55,57,,58,60,61
比较困难的几关是1,16,18,20,26,30,35,37,38,50,53,54,56
下面，我们来看看"困难关卡"的下界估计的情况，看看"偷懒"付出的代价。
顶层结点数
由此可见，下界估计对于搜索树的大小是很有关系的。看看第18,20,35,50,54,56关吧。顶
层结点多么少！如果一开始就从这一层搜索不就…看来我们真的需要用最佳匹配算法了。
3.试验最佳匹配算法的威力
好，下面我们来使用最佳匹配算法。最佳匹配算法可以用网络流来实现，但是这里我们采
用修改顶标算法，我是抄的书上的程序（偷个懒嘛，呵呵）。现在，程序改叫Baby2了^_^
下面是刚才的"难题"的测试情况。
Baby-1结点总数
Baby-2结点总数
哇！有的比刚才的顶层结点还要少！当然了，下界估计好了，当前层的深度剪枝也更准确
另外，现在我们来看看文曲星的前12关，第1,2,4,6,8,9,11关已经可以在50000个结点之内
顶层结点数
那么下一步干什么呢？打印出每个状态来分析，我们不难发现大量重复结点。所以下一个
问题自然就是：怎么避免重复呢？
4.试验HASH表的威力
判重嘛，当然就需要HASH表了。不过一个很棘手的问题是：如何表示状态？在结点扩展中
，我们用比特流的方式定义了箱子的状态，但是在这里我们需要的是合适的数组的下标。
这种表示法不爽吧。所以在构造HASH表的时候我们就用箱子的坐标来表示状态，也就是N元
组(p[1],p[2],p[3]..p[n])。至于散列函数嘛，我们根据HASH表的项数来考虑。这里，如
果箱子最多100个，我们就用10000项试试看。一种方案是把所有的坐标加起来，但是这样
做冲突很多！因为一个箱子A右移一格，另一个箱子B左移一格，散列函数值不变。考虑到
必须使冲突变少，函数又不宜太复杂，我们采用坐标的加权和来作为散列函数值，也就是
Sum{k*Position[k]},当然，最后要对10000取余数，其实这个函数也不好，不过我比较懒
了，以后再改进吧。至于冲突处理吗，为了简单起见，我们用开链法 设立链表来保存所有
元素。值得注意的是，箱子坐标相同而人的坐标不能互通的状态是不同的，应该一起保存
。下面是刚才那些关的测试结果：
Baby2结点数
Baby3结点数
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-26 07:02:56Z
得分:<font color="#
5.结点扩展顺序的优化
在这一节中，我们的最后一个改进是优化结点扩展的顺序，不是想修剪搜索树，而是希望
早一点得到解。具体的改进方法是这样的：
1.优先推刚刚推过的箱子
2.然后试所有的能够减少下界的方案，减少得越多越先试。如果减少得一样多，就先推离
目标最近的。
3.最后试其他的，也象2一样按顺序考虑。
可以预料，这样处理以后，"比较容易"先找到解，但是因为下界估计不准所花费的代价是
无法减小的（也就是说只能减少顶层结点数）。不过作为IDA*的标准改进方法之一，我们
有必要把它加入我们的程序中试试。
(需要注意的是，我们使用的是栈，应该把比较差的方案先压栈)
实际测试结果，1的效果比较好，2和3的效果不佳，甚至产生了更多的结点。可能主要是我
们的下界估计不准确，而2和3用到了下界函数的缘故。这一个版本Baby-4中，我们屏蔽了
第2，3项措施。
好了，写了四个Baby版程序，想不想比较一下呢？不过我只对几个困难一点的数据感兴趣
关卡 实际步数 Baby-1 Baby-2 Baby-3 Baby-4
Kid 51 13 Too many Too many 629 54
Kid 52 18 Too many Too many 39841 97
Kid 54 16 8 140
Kid 55 14 Too many Too many
Kid 56 14 18 1069
Kid 60 15 Too many Too many
Wqx 9 12 6 968 350
从上表可以看出，我们的优化总的来说是有效的，而且直观的看，那些改进不明显的很多
是因为下界估计比较差，这一点我们以后会继续讨论。不管怎样，这61关"幼儿关"过了58
关倒是挺不错的，至少可以说明我们程序的Baby版已经具有普通儿童的"智力"了^_^。不过
这只是个开头，好戏还在后头！
6.Baby-4源程序
程序S4BABY4.PAS在附件中，这里只是加了少量的注释。大家可以试试它的效果，但是没有
必要看得太仔细，因为在以后的章节中，我会改动很多东西，甚至连IDA*主程序框架都会
变得不一样。
常量定义：
VerStr='S4 - SRbGa Super Sokoban Solver (Baby Version 4)';
Author='Written by Liu Rujia(SrbGa), 2001.2, Chongqing, China';
InFile='soko.in';
OutFile='soko.out';
{Charactors}
Char_Soko='@';
Char_SokoInTarget='+';
Char_Box='$';
Char_BoxInTarget='*';
Char_Target='.';
Char_Wall='#';
Char_Empty=' ';
{Dimentions}
MaxBox=50;
{Directions}
DirectionWords:array[0..3] of string=('UP','DOWN','LEFT','RIGHT');
{Movement}
MaxPosition:integer=Maxx*M
Opposite:array[0..3] of integer=(1,0,3,2);
DeltaPos:array[0..3] of integer=(-Maxy,Maxy,-1,1);
我们把x,y坐标合成一个值position，其中position=(x-1)*maxy+(y-1)。这里用类型常量
是因为以后会根据地图的尺寸改变MaxPosition的值。Opposite就是相反方向例如Opposit
e[UP]:=DOWN;DeltaPos也是会重新设定的。我们在进行移动的时候只需要用：NewPos:=Ol
dPos+DeltaPos[Direction]就可以了，很方便。
{IDA Related}
MaxNode=1000000;
MaxDepth=100;
MaxStack=150;
DispNode=1000;
每生成多少个结点报告一次。
{HashTable}
MaxHashEntry=10000;
HashMask=10000;
MaxSubEntry=100;
{BitString}
BitMask:array[0..7] of byte=(1,2,4,8,16,32,64,128);
Infinite=M
类型定义：
PositionType=
BitString=array[0..Maxx*Maxy div 8-1]
整个地图就是一个BitString。第position位为1当且仅当position位置有东西（如箱子，
目标，墙）。
MapType=array[1..Maxx] of string[Maxy];
BiGraph=array[1..MaxBox,1..MaxBox]
GoalPosition:array[1..MaxBox]
Goals:BitS
Walls:BitS
尺寸，原始数据（用来显示状态的），目标的BitString，箱子总数，目标位置（BitStri
ng和位置数组都用是为了加快速度）和Walls的BitString。
Direction:0..3;
Direction是箱子被推向的方向。
StateType=
Boxes:BitS
ManPosition:PositionT
MoveCount:
Move:array[1..MaxDepth] of MoveT
TopLevelNodeCount:
NodeCount:
StartState:StateT
PathLimit:
Stack:array[1..MaxStack] of StateT
Top是栈顶指针。
PHashTableEntry=^HashTableE
HashTableEntry=
Next:PHashTableE
State:StateT
PHashTableType=^HashTableT
HashTableType=
FirstEntry:array[0..MaxHashEntry] of PHashTableE
Count:array[0..MaxHashEntry]
这些是Hash表相关类型。我们采用的是拉链法，这样可以利用指针申请到堆空间，结合保
护模式使用，效果更好。
HashTable:PHashTableT
SokoMaze:MazeT
procedure SetBit(var BS:BitS p:integer);
BS[p div 8]:=BS[p div 8] or BitMask[p mod 8];
procedure ClearBit(var BS:BitS p:integer);
BS[p div 8]:=BS[p div 8] xor BitMask[p mod 8];
function GetBit(var BS:BitS p:integer):
if BS[p div 8] and BitMask[p mod 8]&0 then GetBit:=1 else GetBit:=0;
这些是位操作，设置，清除和得到一个BitString的某一项。
procedure I
Lines:MapT
procedure ReadInputF
SokoMaze.X:=0;
SokoMaze.Y:=0;
SokoMaze.BoxCount:=0;
assign(f,infile);
while not eof(f) do
readln(f,s);
if length(s)&SokoMaze.Y then
SokoMaze.Y:=length(s);
inc(SokoMaze.X);
Lines[SokoMaze.X]:=s;
procedure AdjustD
for i:=1 to SokoMaze.X do
while length(Lines[i])&SokoMaze.Y do
Lines[i]:=Lines[i]+' ';
SokoMaze.Map:=L
for i:=1 to SokoMaze.X do
for j:=1 to SokoMaze.Y do
if SokoMaze.Map[i,j] in [Char_BoxInTarget,Char_SokoInTarget,Char_Targe
SokoMaze.Map[i,j]:=Char_Target
else if SokoMaze.Map[i,j]&&Char_Wall then
SokoMaze.Map[i,j]:=Char_E
调整Map数组，把箱子和搬运工去掉。
for i:=1 to SokoMaze.X do
for j:=1 to SokoMaze.Y do
if Lines[i,j] in [Char_Target,Char_BoxInTarget,Char_SokoInTarget] then
inc(SokoMaze.BoxCount);
SokoMaze.GoalPosition[SokoMaze.BoxCount]:=(i-1)*SokoMaze.Y+j-1;
统计Goal的个数和GoalPosition。
DeltaPos[Up]:=-SokoMaze.Y;
DeltaPos[Down]:=SokoMaze.Y;
MaxPosition:=SokoMaze.X*SokoMaze.Y;
根据地图尺寸调整DeltaPos和MaxPosition
procedure ConstructM
fillchar(SokoMaze.Goals,sizeof(SokoMaze.Goals),0);
fillchar(SokoMaze.Walls,sizeof(SokoMaze.Walls),0);
for i:=1 to SokoMaze.X do
for j:=1 to SokoMaze.Y do
case Lines[i,j] of
Char_SokoInTarget, Char_BoxInTarget, Char_Target:
SetBit(SokoMaze.Goals,(i-1)*SokoMaze.Y+j-1);
Char_Wall:
SetBit(SokoMaze.Walls,(i-1)*SokoMaze.Y+j-1);
procedure InitIDA;
StartState:StateT
IDA.NodeCount:=0;
IDA.TopLevelNodeCount:=0;
fillchar(StartState,sizeof(StartState),0);
for i:=1 to SokoMaze.X do
for j:=1 to SokoMaze.Y do
case Lines[i,j] of
Char_Soko, Char_SokoInTarget:
StartState.ManPosition:=(i-1)*SokoMaze.Y+j-1;
Char_Box, Char_BoxInTarget:
SetBit(StartState.Boxes,(i-1)*SokoMaze.Y+j-1);
StartState.g:=0;
IDA.StartState:=StartS
new(HashTable);
for i:=1 to MaxHashEntry do
HashTable^.FirstEntry[i]:=
HashTable^.Count[i]:=0;
ReadInputF
ConstructM
procedure PrintState(State:StateType);
Map:=SokoMaze.M
x:=State.ManPosition div SokoMaze.Y+1;
y:=State.ManPosition mod SokoMaze.Y+1;
if Map[x,y]=Char_Target then
Map[x,y]:=Char_SokoInTarget
Map[x,y]:=Char_S
for i:=1 to MaxPosition do
if GetBit(State.Boxes,i)&0 th
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-26 07:03:19Z
得分:<font color="#
function CanReach(State:StateT Position:integer):
用BFS判断在状态State中，搬运工是否可以到达Position
Direction:
Pos,NewPos:
Queue:array[0..Maxx*Maxy]
Reached:Array[0..Maxx*Maxy]
fillchar(Reached,sizeof(Reached),0);
Pos:=State.ManP
Get:=0; Put:=1;
Queue[0]:=P
Reached[Pos]:=
CanReach:=
while Get&&Put do
Pos:=Queue[Get];
if Pos=Position then
for Direction:=0 to 3 do
NewPos:=Pos+DeltaPos[Direction];
if Reached[NewPos]
if GetBit(State.Boxes,NewPos)&0
if GetBit(SokoMaze.Walls,NewPos)&0
Reached[NewPos]:=
Queue[Put]:=NewP
CanReach:=
function MinPush(BoxPosition,GoalPosition:integer):
在没有其他箱子的情况下，从BoxPosition推到GoalPosition至少要多少步。
Direction:
Pos,NewPos,ManPos:
Queue:array[0..Maxx*Maxy]
Distance:Array[0..Maxx*Maxy]
for i:=0 to Maxx*Maxy do
Distance[i]:=I
Get:=0; Put:=1;
Queue[0]:=P
Distance[Pos]:=0;
while Get&&Put do
Pos:=Queue[Get];
if Pos=GoalPosition then
MinPush:=Distance[Pos];
for Direction:=0 to 3 do
NewPos:=Pos+DeltaPos[Direction];
ManPos:=Pos+DeltaPos[Opposite[Direction]];
人应该站在后面
if Distance[NewPos]&In
if GetBit(SokoMaze.Walls,NewPos)&0
if GetBit(SokoMaze.Walls,ManPos)&0
人没有站的地方
Distance[NewPos]:=Distance[Pos]+1;
Queue[Put]:=NewP
MinPush:=I
procedure DoMove(State:StateT Position,Direction: var NewState:Sta
NewState:=S
NewPos:=Position+DeltaPos[Direction];
NewState.ManPosition:=P
SetBit(NewState.Boxes,NewPos);
ClearBit(NewState.Boxes,Position);
function MinMatch(BoxCount:Gr:BiGraph):
这个是标准算法，抄的书上的程序，不用看了。
TempGr:BiG
L:array[1..MaxBox*2]
SetX,SetY,MatchedX,MatchedY:Set of 1..MaxB
procedure MaxMatch(n,m:integer);
function Path(x:integer):
for i:=1 to m do
if not (i in SetY)and(Gr[x,i]&&0) then
SetY:=SetY+[i];
if not (i in MatchedY) then
Gr[x,i]:=-Gr[x,i];
MatchedY:=MatchedY+[i];
while (j&=m)and not (j in SetX) and (Gr[j,i]&=0) do inc(j);
if j&=m then
SetX:=SetX+[j];
if Path(j) then
Gr[x,i]:=-Gr[x,i];
Gr[j,i]:=-Gr[j,i];
Fillchar(L,sizeof(L),0);
TempGr:=Gr;
for i:=1 to n do
for j:=1 to m do
if L[i]&Gr[i,j] then
L[i]:=Gr[i,j];
u:=1; MatchedX:=[]; MatchedY:=[];
for i:=1 to n do
for j:=1 to m do
if L[i]+L[n+j]=TempGr[i,j] then
Gr[i,j]:=1
Gr[i,j]:=0;
while u&=n do
SetX:=[u]; SetY:=[];
if not (u in MatchedX) then
if not Path(u) then
for i:=1 to n do
for j:=1 to m do
if (i in SetX) and not (j in SetY) and (L[i]+L[n+j]-TempGr[i,j]&al
al:=L[i]+L[n+j]-TempGr[i,j];
for i:=1 to n do if i in SetX then L[i]:=L[i]-
for i:=1 to m do if i in SetY then l[n+i]:=l[n+i]+
for i:=1 to n do
for j:=1 to m do
if l[i]+l[n+j]=TempGr[i,j] then
Gr[i,j]:=1
Gr[i,j]:=0;
MatchedX:=[]; MatchedY:=[];
for i:=1 to n+m do
if l[i]&-1000 then
MatchedX:=MatchedX+[u];
VeryBig:=0;
for i:=1 to BoxCount do
for j:=1 to BoxCount do
if (Gr[i,j]&Infinite)and(Gr[i,j]&VeryBig) then
VeryBig:=Gr[i,j];
inc(VeryBig);
for i:=1 to BoxCount do
for j:=1 to BoxCount do
if Gr[i,j]&Infinite then
Gr[i,j]:=VeryBig-Gr[i,j]
Gr[i,j]:=0;
这些语句是进行补集转化。
MaxMatch(BoxCount,BoxCount);
for i:=1 to BoxCount do
for j:=1 to BoxCount do
if Gr[i,j]&0 then
Tot:=Tot+VeryBig-TempGr[i,j];
if Gr[i,j]&=0 then
MinMatch:=I
MinMatch:=T
function CalcHeuristicFunction(State:StateType):
计算启发函数值
i,j,p,Count,BoxCount,Cost:
BoxPos:array[1..MaxBox]
Distance:BiG
for i:=1 to MaxPosition do
if GetBit(State.Boxes,i)&0 then
BoxPos[p]:=i;
for i:=1 to p do
for j:=1 to p do
Distance[i,j]:=MinPush(BoxPos[i],SokoMaze.GoalPosition[j]);
BoxCount:=SokoMaze.BoxC
for i:=1 to BoxCount do
for j:=1 to BoxCount do
if Distance[i,j]&Infinite then
inc(Count);
if Count=0 then
有一个箱子推不到任何目的地
CalcHeuristicFunction:=I
H:=MinMatch(BoxCount, Distance);
CalcHeuristicFunction:=H;
function HashFunction(State:StateType):
for i:=1 to MaxPosition do
if GetBit(State.Boxes,i)&0 then
h:=(h+p*i) mod HashM
你可以自己换一个
HashFunction:=h;
function SameState(S1,S2:StateType):
SameState:=
for i:=1 to MaxPosition do
if GetBit(S1.Boxes,i)&&GetBit(S2.Boxes,i) then
if not CanReach(S1,S2.ManPosition) then
注意只要两个状态人的位置是相通的就应该算同一个状态
SameState:=
atlantis13579(更深的蓝)(^_^)
) 信誉：100
<font color="#02-06-26 07:04:24Z
得分:<font color="#
function Prior(State:StateTM1,M2:MoveType):
Inertia1,Inertia2:
S1,S2:StateT
if State.MoveCount&0 then
NewPos:=State.Move[State.MoveCount].Position+
DeltaPos[State.Move[State.MoveCount].Direction];
if NewPos=M1.Position then Inertia1:=true else Inertia1:=
连续推同一个箱子的动作优先
if NewPos=M2.Position then Inertia2:=true else Inertia2:=
if Inertia1 and not Inertia2 then begin Prior:=
if Inertia2 and not Inertia1 then begin Prior:=
procedure IDA_S
CurrentState:StateT
procedure IDA_Push(State:StateType);
if IDA.Top=MaxStack then
inc(IDA.Top);
IDA.Stack[IDA.Top]:=S
procedure IDA_Pop(var State:StateType);
State:=IDA.Stack[IDA.Top];
dec(IDA.Top);
function IDA_Empty:
IDA_Empty:=(IDA.Top=0);
上面的是栈操作
procedure IDA_AddToHashTable(State:StateType);
p:PHashTableE
h:=HashFunction(State);
if HashTable^.Count[h]&MaxSubEntry then
p^.State:=S
p^.Next:=HashTable^.FirstEntry[h];
HashTable^.FirstEntry[h]:=p;
inc(HashTable^.Count[h]);
else begin
p:=HashTable^.FirstEntry[h];
while p^.Next^.Next&&nil do
p^.Next^.State:=S
p^.Next^.Next:=HashTable^.FirstEntry[h];
HashTable^.FirstEntry[h]:=p^.N
function IDA_InHashTable(State:StateType):
p:PHashTableE
h:=HashFunction(State);
p:=HashTable^.FirstEntry[h];
IDA_InHashTable:=
while p&&nil do
if SameState(p^.State,State) then
if p^.State.g&State.g then
p^.State.g:=State.g;
IDA_InHashTable:=
如果找到的表项深度要大些，并不代表这一次深度小点的也无解。本来应该动态更新下界
的，这里作为没有找到处理，后面的章节会改进这个地方的。
IDA_InHashTable:=
这是Hash表的操作。
procedure IDA_AddNode(State:StateType);
IDA_Push(State);
inc(IDA.NodeCount);
if IDA.NodeCount mod DispNode=0 then
Writeln('NodeCount=',IDA.NodeCount);
inc(IDA.TopLevelNodeCount);
IDA_AddToHashTable(State);
procedure IDA_Expand(State:StateType);
MoveCount:
MoveList:array[1..Maxx*Maxy*4] of MoveT
i,j,Direction:
NewBoxPos, NewManPos:
NewState:StateT
MoveCount:=0;
for i:=1 to MaxPosition do
if GetBit(State.Boxes,i)&0 then
for Direction:=0 to 3 do
NewBoxPos:=i+DeltaPos[Direction];
NewManPos:=i+DeltaPos[Opposite[Direction]];
if GetBit(State.Boxes,NewBoxPos)&0
if GetBit(SokoMaze.Walls,NewBoxPos)&0
if GetBit(State.Boxes,NewManPos)&0
if GetBit(SokoMaze.Walls,NewManPos)&0
if CanReach(State,NewManPos) then
DoMove(State,i,Direction,NewState);
if CalcHeuristicFunction(NewState)=In
if CalcHeuristicFunction(NewState)+State.g&=IDA.PathLimit then con
IDA*算法的核心：深度限制
if IDA_InHashTable(NewState)
inc(MoveCount);
MoveList[MoveCount].Position:=i;
MoveList[MoveCount].Direction:=D
for i:=1 to MoveCount do
for j:=i+1 to MoveCount do
if Prior(State,MoveList[i],MoveList[j]) then
调整推法次序
t:=MoveList[j];
MoveList[j]:=MoveList[i];
MoveList[i]:=t;
for i:=1 to MoveCount do
依次考虑所有移动方案
DoMove(State,MoveList[i].Position,MoveList[i].Direction,NewState);
inc(NewState.MoveCount);
NewState.Move[NewState.MoveCount].Position:=MoveList[i].P
NewState.Move[NewState.MoveCount].Direction:=MoveList[i].D
NewState.g:=State.g+1;
IDA_AddNode(NewState);
procedure IDA_Answer(State:StateType);
Writeln(f,'Solution Found in ', State.MoveCount,' Pushes');
for i:=1 to State.Movecount do
x:=State.Move[i].Position div SokoMaze.Y+1;
y:=State.Move[i].Position mod SokoMaze.Y+1;
Writeln(f, x,' ',y,' ',DirectionWords[State.Move[i].Direction]);
Writeln(VerStr);
Writeln(Author);
IDA.PathLimit:=CalcHeuristicFunction(IDA.StartState)-1;
inc(IDA.PathLimit);
Writeln('Pathlimit=',IDA.PathLimit);
IDA.TopLevelNodeCount:=0;
IDA.Top:=0;
IDA.StartState.g:=0;
IDA_Push(IDA.StartState);
IDA_Pop(CurrentState);
H:=CalcHeuristicFunction(CurrentState);
if Solution(CurrentState) then
Sucess:=true
else if IDA.PathLimit&=CurrentState.g+H then
IDA_Expand(CurrentState);
until Sucess or IDA_Empty or (IDA.NodeCount&MaxNode);
Writeln('PathLimit ',IDA.PathLimit,' Finished. NodeCount=',IDA.NodeCount);
until Sucess or (IDA.PathLimit&=MaxDepth) or (IDA.NodeCount&MaxNode);
Assign(f,outfile);
ReWrite(f);
Writeln(f,VerStr);
Writeln(f,Author);
Writeln(f);
if not Sucess then
Writeln(f,'Cannot find a solution.')
IDA_Answer(CurrentState);
Writeln('Node Count:',IDA.NodeCount);
NowCan(((((( ★ ))))))
) 信誉：100
<font color="#02-06-26 17:57:16Z
得分:<font color="#
结束了吗？
LeeMaRS(小菜虎，仍需努力)
) 信誉：122
<font color="#02-06-26 17:58:19Z
得分:<font color="#
@_@ 狂抄SRbGa的论文.....
小蓝,你行D.....
scorpiotianyawei(scorpiotianyawei)
) 信誉：100
<font color="#02-06-26 18:00:56Z
得分:<font color="#
我有源代码,vb 的
，得分记录：
atlantis13579
scorpiotianyawei