页数：7页文件大小：363.0 KB来源： 数据结构-C#语言描述ppt课件
本课件以八数码问题作为课程综合实训：先说明 3×3 九宫格上移动棋子从初始状态到目标状态的规则，再引入逆序的概念，用两个具体棋局演示逆序数的计算方法，并给出“逆序奇偶性相同则可相互到达”的判定结论，最后讨论用什么方法与数据结构求解最优解、以及如何用数组表示棋盘状态。
本页为第十章八数码问题封面。本章作为课程综合实训，讲解八数码问题的规则、有解性判定以及求解最优解的方法与数据结构。
八数码问题就是在一个 3×3 的九宫格棋盘上，分别将标有数字 1~8 的八个棋子摆放其中，摆放时要求棋子不能重叠。于是，在 3×3 的棋盘上将出现一个空格，允许这个空格周围的某一个棋子向空格移动。
这样通过移动棋子就可以不断改变棋子的布局。假设给定一个初始的棋子布局（初始状态）和一个目标布局（目标状态），要求移动棋子，实现从初始状态到目标状态的转变，给出一个合法的走步序列。
逆序状态：将棋局中的数字从上到下、从左到右进行排序，每个数字前面比它大的数字的个数和称为这个状态的逆序。
函数 F(n) 表示数字 n 前面比它大的数字的个数。对棋局 8、1、5、6、7、3、4、2 逐一计算，结果如下：
| 数字 n | F(n)：前面比它大的数字个数 |
|---|---|
| 8 | 0 |
| 1 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 3 | 4 |
| 4 | 4 |
| 2 | 6 |
各 F(n) 之和为 18，是偶数，因此该棋局的逆序状态为偶数。
逆序状态：将棋局中的数字从上到下、从左到右进行排序，每个数字前面比它大的数字的个数和称为这个状态的逆序。函数 F(n) 表示数字 n 前面比它大的数字的个数。
对棋局 7、6、8、4、2、5、3、1 逐一计算，结果如下：
| 数字 n | F(n)：前面比它大的数字个数 |
|---|---|
| 7 | 0 |
| 6 | 1 |
| 8 | 0 |
| 4 | 3 |
| 2 | 4 |
| 5 | 3 |
| 3 | 5 |
| 1 | 7 |
各 F(n) 之和为 23，是奇数，因此该棋局的逆序状态为奇数。
对比两个棋局的逆序状态：
判定规则：若两个状态的逆序奇偶性相同，则可相互到达，否则不可相互到达。因此这两个棋局之间无法相互到达。
本页讨论使用什么方法求解八数码问题的最优解：把每一种棋子布局看作状态空间中的一个结点，从初始状态出发按空格的移动规则逐层扩展，直到搜索到目标状态为止。
图中给出了初始状态、目标状态以及若干中间状态构成的搜索树，沿起始状态到目标状态的路径即可得到合法的走步序列。
本页讨论使用什么数据结构表示棋盘状态。下图棋盘状态为 7、6、8、4、2、5、3、1，可用一个长度为 9 的一维数组按从左到右、从上到下的顺序存放各格中的棋子：
| 数组下标 | 存放内容 |
|---|---|
| 1 | 7 |
| 2 | 6 |
| 3 | 8 |
| 4 | 4 |
| 5 | 空格 |
| 6 | 2 |
| 7 | 5 |
| 8 | 3 |
| 9 | 1 |
用一维数组表示后，每次移动棋子只需交换空格所在位置与目标棋子所在位置的两个元素，便于程序判重与搜索。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}