资源描述：
《国家集训队2001论文集 chapter3》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、搬运工问题的启示重庆外语学校刘汝佳三用IDA*算法解搬运工问题实现与改进在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里，我们将用IDA*算法来做一个解决搬运工问题的程序–虽然是我们的最初版本(我们称做S4-Baby)，但是不要小看它哦！1IDA*算法框架由前所述，IDA*算法是基于重复式深度优先的A*算法，忽略所有f值大于深度限制的结点。那么，我们不难写出IDA*算法框架的伪代码伪代码1-IDA*算法框架procedureIDA_STAR(StartState)begin
2、PathLimit:=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(CurrentS
3、tate)doPush(OpenStack,Child(CurrentState));untilSuccessorempty(OpenStack);untilSuccessorResourceLimitsReached;end;这只是一个很粗略的框架，什么事情都不能做。不过我想大家可能比较急于试验一下IDA*的威力，因此我们不妨就做一个最最基本的程序。2.第一个程序要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。输入输出文件格式输入文件是一个文本文件，它由N行构成，每行是一些字符。各种字
4、符的含义是：SPACE空地.目标格子$箱子*目标格子中的箱子@搬运工+目标格子中的搬运工#墙表2输入文件格式这种格式和Xsokoban,SokoMind和RollingStone的格式是一致的，因此会比较方便一些。输出文件第一行是推箱子的次数M，以下M行，每行的格式是：xydirection,代表把第x行第y列的箱子往direction的方向推一步。Direction可以是left,right,up,down之中的一个,1<=x,y<=20数据结构由于是最初的版本，我们不必考虑这么多：只需要可行，编程
5、方便就可以了，暂时不管它的效率和其他东西。优化是以后的事。我们定义新的数据类型BitString,MazeType,MoveType,StateType和IDAType。请大家看附录中的程序，不难猜出它们的含义和用途。唯一需要说明的BitString类型。记录状态时，我们把地图看成一个大数，一个格子是一个bit。那么所有箱子构成一个BitString,检查某一个是否有箱子（或者目标，墙）时只需要检测对应位置上的bit是否为1。这样虽然会浪费一些空间，但是判断会比较快，操作也比较简单。我们把x,y坐标合
6、并成一个”position”变量。其中Position=(x-1)*width+(y-1)。我们用常量数组DeltaPos:array[0..3]表示上，下，左，右的Position增量。算法为了简单起见，我们连最佳匹配也不做了，用所有箱子离最近目标的距离和作为下界函数。不过，这里的“距离”是指推的次数，计算的时候（MinPush函数），只要忽略其它所有箱子，然后用一次BFS就可以了。效果嘿嘿，这个效果嘛，不说你也知道的，就是标准关一个也过不了啦。不过为了说明我的程序是正确的，你可以试验一下幼儿关卡(
7、共61关)嘛！什么！第一关都就没有动静了…55555，生成了18万个结点???不过很多关都很快就过了的。我们用1,000,000个结点为上限(在我的Celeron300A上要运行十多分钟),得到以下的测试结果：No.步数结点数No.步数结点数No.步数结点数1151864762181024111145262422711042101183514231019243122234624241043244863593125423451213865826118464614178763527318478296811
8、39289384881569412291014249560105143086415011144511151331719251N/A>1M124193231252N/A>1M134143311515384701462034113325416242701565735161111855N/A>1M1612394736102425614331817663379117157N/A>1M18115108381155658N/A>1M19104673910725911
