搜索
搬运工问题的启示重庆外语学校刘汝佳三用IDA*算法解搬运工问题实现与改进在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里，我们将用IDA*算法来做一个解决搬运工问题的程序–虽然是我们的最初版本(我们称做S4-Baby)，但是不要小看它哦！1IDA*算法框架由前所述，IDA*算法是基于重复式深度优先的A*算法忽略所有f值大于深度限制的结点。那么，我们不难写出IDA*算法框架的伪代码伪代码1-IDA*算法框架procedureIDA_STAR(StartState)beginPathLimit:=H(StartState)–1;Success:=False;repeatinc(PathLimit);StartState.g:=0;Push(OpenStack,StartState);repeatCurrentState:=Pop(OpenStack);IfSolution(CurrentState)thenSuccess=TrueElseifPathLimit=CurrentState.g+H(CurrentState)thenForeachChild(CurrentState)doPush(OpenStack,Child(CurrentState));untilSuccessorempty(OpenStack);untilSuccessorResourceLimitsReached;end;这只是一个很粗略的框架，什么事情都不能做。不过我想大家可能比较急于试验一下IDA*的威力，因此我们不妨就做一个最最基本的程序。2.第一个程序要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。输入输出文件格式输入文件是一个文本文件，它由N行构成，每行是一些字符。各种字符的含义是：SPACE空地.目标格子$箱子*目标格子中的箱子@搬运工+目标格子中的搬运工#墙表2输入文件格式这种格式和Xsokoban,SokoMind和RollingStone的格式是一致的，因此会比较方便一些。输出文件第一行是推箱子的次数M，以下M行，每行的格式是：xydirection,代表把第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个结点为上限(在我的Celeron300A上要运行十多分钟),得到以下的测试结果：No.步数结点数No.步数结点数No.步数结点数115186476218102411114526242271104210118351423101924312223462424104324486359312542345121386582611846461417876352731847829681139289384881569412291014249560105143086415011144511151331719251N/A1M124193231252N/A1M134143311515384701462034113325416242701565735161111855N/A1M1612394736102425614331817663379117157N/A1M18115108381155658N/A1M191046739107259113282010168140920360N/A1M61N/A1M没有解决的几关是：51,52,55,57,,58,60,61比较困难的几关是1,16,18,20,26,30,35,37,38,50,53,54,56下面，我们来看看“困难关卡”的下界估计的情况，看看“偷懒”付出的代价。关卡最优步数初始深度结点总数顶层结点数1151118647674161612739478441811105108492010616814226115846394308664120035163111183464379411714933811555625050116144515153854704854169242702562561443318460由此可见，下界估计对于搜索树的大小是很有关系的。看看第18,20,35,50,54,56关吧。顶层结点多么少！如果一开始就从这一层搜索不就…看来我们真的需要用最佳匹配算法了。3.试验最佳匹配算法的威力好，下面我们来使用最佳匹配算法。最佳匹配算法可以用网络流来实现，但是这里我们采用修改顶标算法，我是抄的书上的程序（偷个懒嘛，呵呵）。现在，程序改叫Baby2了^_^下面是刚才的“难题”的测试情况。关卡实际步数初始深度Baby-1结点总数Baby-2结点总数1151518647660161210394730418111151084620108168176261158465523088641153351641111865043795117143838115556546501171445198538847037541612242702735614433182225哇！有的比刚才的顶层结点还要少！当然了，下界估计好了，当前层的深度剪枝也更准确了嘛。另外，现在我们来看看文曲星的前12关，第1,2,4,6,8,9,11关已经可以在50000个结点之内出解。关卡实际步数初始深度结点总数顶层结点数131317575211111421424261833923159616164747827212392139126480627781114147373那么下一步干什么呢？打印出每个状态来分析，我们不难发现大量重复结点。所以下一个问题自然就是：怎么避免重复呢？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结点数Kid115156052Kid161210304189Kid1811114641Kid201087667Kid26115552192Kid3088153145Kid351646504704Kid3795438136Kid38115546152Kid501179896Kid53883724Kid541612273258Kid5614422251518Wqx131317575Wqx21111142107Wqx426183392333916Wqx616164746Wqx82721239226Wqx91264806968Wqx1114147367新完成的关卡有：关卡实际步数初始深度结点总数顶层结点数Kid511313629629Kid5218183984139841Kid5514448861919Kid601596916916需要注意的是，在保护模式下运行kid57的时候出现的heapoverflow，说明完全保存结点没有必要(费空间，费时间)，也不大可能。那么，我们应该怎样做呢？我们知道，评价一个HASH表的优劣，一般是从两个方面：查表成功的频率和查表成功以后节省的工作。因此，我们可以设置两个Hash表，一个保存最近的结点（查到的可能性比较大）和深度大的结点（一旦找到，节省很多工作）。这样做不会增加多少结点数，但是是程序效率有所提高，求解能力（空间承受能力）也有较大改善。但是为了方便，我们的程序暂时只使用第一个表。5.结点扩展顺序的优化在这一节中，我们的最后一个改进是优化结点扩展的顺序，不是想修剪搜索树，而是希望早一点得到解。具体的改进方法是这样的：1.优先推刚刚推过的箱子2.然后试所有的能够减少下界的方案，减少得越多越先试。如果减少得一样多，就先推离目标最近的。3.最后试其他的，也象2一样按顺序考虑。可以预料，这样处理以后，“比较容易”先找到解，但是因为下界估计不准所花费的代价是无法减小的（也就是说只能减少顶层结点数）。不过作为IDA*的标准改进方法之一，我们有必要把它加入我们的程序中试试。(需要注意的是，我们使用的是栈，应该把比较差的方案先压栈)实际测试结果，1的效果比较好，2和3的效果不佳，甚至产生了更多的结点。可能主要是我们的下界估计不准确，而2和3用到了下界函数的缘故。这一个版本Baby-4中，我们屏蔽了第2，3项措施。好了，写了四个Baby版程序，想不想比较一下呢？不过我只对几个困难一点的数据感兴趣。关卡实际步数Baby-1Baby-2Baby-3Baby-4Kid111186476605238Kid1673947304189149Kid18105108464131Kid3516111186504704462Kid5011144519896152Kid5113ToomanyToomany62954Kid5218ToomanyToomany3984197Kid541624270273258140Kid5514ToomanyToomany48863390Kid56143318222515181069Kid6015ToomanyToomany69165022Wqx42697855339233391624251Wqx9121169274806968350从上表可以看出，我们的优化总的来说是有效的，而且直观的看，那些改进不明显的很多是因为下界估计比较差，这一点我们以后会继续讨论。不管怎样，这61关“幼儿关”过了58关倒是挺不错的，至少可以说明我们程序的Baby版已经具有普通儿童的“智力”了^_^。不过这只是个开头，好戏还在后头！6.Baby-4源程序程序S4BABY4.PAS在附件中，这里只是加了少量的注释。大家可以试试它的效果，但是没有必要看得太仔细，因为在以后的章节中，我会改动很多东西，甚至连IDA*主程序