资源描述：
《算法设计与分析开放性实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《推箱子问题的设计与实现》实验报告一、问题描述码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。二、问题求解分析设箱子位置为Box，目标位置是End,人的位置为Man.可从所述问题上得到
2、以下条件：1.箱子是事物，不能和人处于同一位置上2.人只能推着箱子向前方移动3.移动方向只有四种：上、下、左、右4.找出从Box到Tar的最短路径，如果不存在任何路径，那么将相应的信息返回5.可移动空间周围有堵墙，即移动空间是封闭的6.走过的位置可重走如图所示，设箱子要移动到位置A，并且要求路径最短，那么我们可以从需求出发设计算法。既然要到达A位置，那么箱子必然要先到达B,C,D,E中的一点，假设B,C,D,E均可行，则我们可以让箱子先到达B，将找出的箱子到A的路径信息，保存起来，然后恢复各种信息到初始状况，依次比较箱子到达C,D,E的各种路径，并找出其中最短的一条件作为函数的返回值，最终将
3、最优的这条路径返回即可。同时在寻找路径时，我们可以对搜索空间进行剪枝，经过分析，我们可以在以下情况下进行剪枝：1.搜索到当前结点时，判断路径走不通2.要添加到路径中的结点是堵物时3.搜索出的可行路径比之前保留起来的可行路径较长在这些特殊的情况下，我们可以实现剪枝，最大限度的节省内存空间和搜索空间。对于特殊的情况，例如下图(2)所示，人站在C处，要求箱子从A移动到B。很明显，人是无法推动箱子的，因为根据题意，不存在人能够到达推动箱子的地方的路径，那么此时该怎样做呢？经过分析，我们可以有如下解决方法：1.求出箱子此次移动人必须站在的地方，此时为D。2.采用局部向整体扩散的方法，找出所有可以的到达
4、D的坐标并将其标记某一特定的符号BACDEBCAED（1）(2)三、源程序关键代码#include#includeusingnamespacestd;structPosition{shortrow;shortcol;};structGirdS{shortrow;shortcol;intstep;inttotle;Positionman_s;};structCompare{public:booloperator()(constGirdS&x,constGirdS&y)const{returnx.totle>y.totle;}};ifstreamin_f("inp
5、ut.txt");ofstreamout_f("output.txt");intn,m;//定义搜索四个方向Positionoffset[4];//start：箱子的初始位置；end：箱子的目标位置；man_s：人的位置；人是在man_t把箱子往nbox_e位置推Positionstart,end,man_s,man_t;//标志方格状态-1为障碍，0为空闲short**menFlag;//临时存放menFlag的数组short**temp;//标志方格的四个方向是否空闲bool***girdFlag;//box_s：箱子所在位置，nbox_e：推之后箱子的位置GirdSbox_s,nbox
6、_e;//可扩展结点队列，经过大小排列的队列?priority_queue,Compare>Q;//人能否到达到man_t的位置,人是在man_t把箱子往nbox_e位置推boolCanArrive(Position&man_s,Position&man_t,GirdS&box_s,short**menFlagtemp){queuepos1,pos2;Positionstart=man_s,end=man_t,from,to,temp1,temp2;if(start.row==end.row&&start.col==end.col)
7、returntrue;from=start;to=end;menFlagtemp[box_s.row][box_s.col]=-1;//箱子不动，人不能走箱子所在的位子menFlagtemp[from.row][from.col]=1;//人出发点（走过）menFlagtemp[to.row][to.col]=2;//目标点for(;;){for(inti=0;i<4;i++)//start（man_s）和e
