奥林匹克竞赛论文-搬运工问题的启示三 用IDA算法解搬运工问题 实现与改进定稿.doc

PAGE PAGE 4 搬运工问题的启示 重庆外语学校 刘汝佳 三 用IDA*算法解搬运工问题 实现与改进 在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里，我们将用IDA*算法来做一个解决搬运工问题的程序 – 虽然是我们的最初版本(我们称做S4-Baby)，但是不要小看它哦！ 1 IDA*算法框架 由前所述，IDA*算法是基于重复式深度优先的A*算法，忽略所有f值大于深度限制的结点。那么，我们不难写出IDA*算法框架的伪代码 伪代码1 - IDA*算法框架 procedure IDA_STAR(StartState) begin PathLimit := H( StartState ) – 1; Success := False; repeat inc(PathLimit); StartState.g:= 0; Push(OpenStack,StartState); repeat 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 ResourceLimitsReached; end; 这只是一个很粗略的框架，什么事情都不能做。不过我想大家可能比较急于试验一下IDA*的威力，因此我们不妨就做一个最最基本的程序。 2. 第一个程序 要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。 输入输出文件格式 输入文件是一个文本文件，它由N行构成，每行是一些字符。 各种字符的含义是： SPACE 空地 . 目标格子 $ 箱子 * 目标格子中的箱子 @ 搬运工 + 目标格子中的搬运工 # 墙 表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上要运行十多分钟),得到以下的测试结果： No. 步数 结点数 No. 步数 结点数 No. 步数 结点数 1 15 186476 21 8 102 41 11 145 2 6 24 22 7 110 42 10 118 3 5 14 23 10 192 43 12 223 4 6 24 24 10 432 44 8 63 5 9 31 25 4 23 45 12 138 6 5 8 26 11 846 46 14 178 7 6 35 27 3 18 47 8 296 8 11 39 28 9 38 48