八数码问题解的存在性证明_8数码问题无解情况资源-CSDN文库

3星 · 超过75%的资源需积分: 42 62 浏览量 2009-12-15 13:32:40 上传评论收藏 41KB DOC 举报

资源推荐

资源详情

资源评论

关于此问题解的存在性讨论如下：

为了进行更一般性的讨论，这里把 3*3 的八数据码问题一般化的 M*N（其中 N 为奇数）的 M*N-1 数码问

题，也就是对 M*N 矩阵（如图 1 所示）中数码的位置的讨论。

首先说明序列和逆序对数。把 M*N 的数码矩阵看成这样一个先行后列的

数码序列(以下不区分数码矩阵与数码序列 )，其中的代格不排入序列（每个数

码均不相同，如图 2 序列 1）：

并且规定按两个数码的大小关系确定其偏序关系，这样可得到上述序列的

逆序对数。

假设现在的空格在 Aij（i>=1 && i<=m , j=1 && j<=n）的位置，如图 2 中的序列 2 所示。对 Aij 四周的数码

的移动不仿看成是空格的移动，其移动（具有一般性意义的移动，没有 i，j 越界的情况）分为以下两种情况：

1、空格向左、右移动。这种情况下，移动前后序列的逆序对数不改变，这是显然的，因为空格没有排在

序列中，移动前后还是同一个序列。

2、空格向上、下移动。先讨论向上移动的情况，移动前如图 2 中的序列 2 所示状态，移动后如图 2 中的

序列 3 所示状态，这相当于数码 A(i-1)j 连续与右相邻的数码交换位置（N-j）+（j-1）次即 N-1 次后

的状态。

引理：交换序列的任意两元素，序列的逆序数的奇偶性必定发生改变。

由引理可得出一个推论：对序列进行偶数次的交换，序列的逆序数的奇偶性保持不变。

因此若 N 为奇数，则 N-1 为偶数，移动后序列的逆序对数的奇偶性不发生改变；对于 N 为偶数的情况

这里不作讨论。

空格向下移动的情况与向上移动道理相同，不再重复说明。

由以上对两种情况的讨论可知：空格的移动不会改变序列逆序对数的奇偶性（这里讨论的时 N 为奇数的情况）。

综上可知：如果初始数码序列的逆序对数的奇偶性与目标序列的逆序对数的奇偶性不相同时，状态转移的

路径肯定是找不到的。也就是说原问题是无解的。

那么对于初始数码序列的逆序对数的奇偶性与目标序列的逆序对数的奇偶性相同时，是否一定有解呢？答

案是肯定的。下面给出一个证明。

设目标状态为数码矩阵 A[M*N]，初始状态为数码矩阵 B[M*N]。

显然：空格的移动都是可逆的。

首先移动 B 的空格，使之达到图表 3 所示的状态，即把空格移动到左

上角，记为 B’显然如果 A 能转化到 B’，则进而可以转化到 B（以 0 代表空格，

以下不在特别说明）。

下面给出一个由 A 状态向图表 3 所示状态的移动策略（假设

M>N）：

1、设 B’的最后一行为 B’[1….N]，首先移动 A 中的数码，使得 A 中

的最后一行与 B’的最后一行相同，移动方法为第 2 步：

2、在 A 中，首先移动 B’[i]{i>=1 && i<=n-1}到其相应位置的正上方，

再把空格移动到其对应的位置，然后此数码即可移动到位；下面

第 3 步移动此行的最后一个数码到位。

3、移动 B’[N]到 B’[N-1]位置的上方，再把空格移到 B’[1]的上方，然后顺时针移动 B’[1….N-1]一个格子，

然后数码 B[N]落下，再把 B[1….N]逆时针移动一个格子。此时 A 的最后一行与 B’的最后一行相同。

4、重复 2、3 的相似步骤直到第 N 行。此时 A 与 B’只有前 N 行的 N 列不相同，下面移动 A 的第 N 行与

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

诺伊

2013-02-13

对问题进行了详细的证明，学习了很多。。。

zhangjunhui1012

粉丝: 0
资源: 3

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip