n数码程序设计说明2003.docVIP

N数码问题自动求解算法说明 问题描述： ?????? 有一个3×3的棋盘，其中有0~8九个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态步数最少的解。 ???????解决八数码问题的常用方法为图有哪些信誉好的足球投注网站法，可用广度优先、深度优先和A*算法实现，其中A*算法又因估价函数的不同而有着不同的有哪些信誉好的足球投注网站时间。 我通过自己玩八数码游戏，然后又参照了网上的相关算法，最后通过总结游戏的玩法，开发了自己的一套特有的解法，用编程的方式记录了游戏的解法思路，让计算机也可以自动求解了。 在最开始我打算写这个程序时，我就给自己立了一个目标，一定要做成可扩展的，也就是说不仅可以解出3X3的8数码，也可以解4X4的15数码，甚至N X N的N平方减1数码，通过努力，最后还是达成了目标，还可以通过对程序进行简单的扩展，去求解N X M的数码问题。 思路： 用到算法中的动态规划，总体上讲是把游戏的整个复原过程分成了三个阶段，复原过程不一定是最优的，但一定可以在较短时间内找到解法。 三个阶段分别是：拼和中心部分，拼和边界，拼合右下角 对于NxN的数码问题，中心部分指的是从左上角算起，1到n-2行乘以1到n-2列的方阵。 边界分为右边界和下边界两个部分，右边界指的是n-1列和n列乘以1到n-2行的方阵；左边界指的是n-1行和n行乘以1到n-2列的方阵。 右下角指的是(n-1,n-1),(n-1,n),(n,n-1)三个元素 以下是区域划分的例子： 1所在的位置表示中心部分，2所在的位置表示右边界，3所在的位置表示下边界，4所在的位置表示右下角 当n=6时的区域划分 1 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 2 2 3 3 3 3 4 4 3 3 3 3 4 当n=3时的区域划分 1 2 2 3 4 4 3 4 当n=4时的区域划分 1 1 2 2 1 1 2 2 3 3 4 4 3 3 4 当n=8，m=5时的区域划分 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 3 3 3 3 3 3 4 4 3 3 3 3 3 3 4 以6x6的35数码问题为例，详细说明各个阶段具体做什么 1．拼和中心部分 先从第一个元素说起（1行1列），假设在要把4行6列的一个滑块移动到1行1列，而空格的位置在6行6列，这时该怎么做呢？ 分为两步，首先确定从4行6列到1行1列的路径（要确定这个路径很简单不需要用寻路算法）然后再把空格移动到这条路径的第1个节点上（在空格移动到这个节点之前，待移动滑块暂时被block，让空格不能移动到待移动滑块的位置），然后4行6列的滑块沿着这条路径走一步（空格的行列位置会改变，block数组中的一个元素也会改变），然后再把空格移动到这条路径的第2个节点上，然后滑块再沿着路径前进1步，以此类推，直到滑块到达目标位置。 把第一个滑块归位后，就把相应位置的状态设置为block，意思是1行1列变成障碍物，以后在移动空格的过程中，空格始终不被允许移动到这个位置，然后以此类推可以完成整个中心部分的拼合，中心部分拼合完成后整个中心区域（1所在的位置）都被block掉了，这时再来拼合右边界 2．边界拼合 边界分为右边界和下边界 2。1 右边界拼合 边界的拼合之所以要和拼合中心部分区分开来是因为按照中心部分的拼合算法来弄，很可能出现问题无解的情况，比如对于6行6列的数码问题，中心区域已经拼合，如果继续用中心部分的拼合算法，先让1行5列的滑块归位，1行5列就被block掉，下个要归位的滑块在2行6列，而空格在其他位置（只要不在1行6列），这时空格是不可能到达1行6列，因为1行5列和2行6列都被block掉了。 要让1行5列和1行6列的滑块归位也有2个步骤：（构造局部区域，拼合局部区域），构造局部区域： 就是把这两个待归位的滑块和空格都移动到一个矩形区域，就这个例子而言，这个矩形区域指1行5列，2行5列，3行5列，1行6列，2行6列，3行6列这6个位置。 拼合局部区域： 就是让空格和两个待归位的滑块都只能在这个矩形区域内移动，因为问题规模很小，用广度优先有哪些信誉好的足球投注网站或者其他有哪些信誉好的足球投注网站方式，都能很快找出让1行5列，1行6列滑块归位的最少移动步法，一旦1行5列，1行6列归位，就把这两个位置block掉，拼合局部区域就算完成了。 然后矩形区域也下移一个单位，变成从2行到4行的5列6列。重新构造局部区域，然后拼合局部区域，2行5列，2行6列归位并被block掉；以此类推可以把右边界拼合（2所在的位置） 2．2 下边界拼合 和拼合右边界的方法是一样的，只是矩形区域有变化(第一矩形区域是5行到6行，1列到3列) 3．拼