高中信息技术粤教版选修5 人工智能初步4.1 重排九宫问题及其树的表示完美版ppt课件

这是一份高中信息技术粤教版选修5 人工智能初步4.1 重排九宫问题及其树的表示完美版ppt课件，共12页。PPT课件主要包含了重排九宫问题，棋子的四种移动方法，重排九宫问题状态树，树的一些术语等内容，欢迎下载使用。
在3×3的方格棋盘上，放置标有数码的8个棋子（1，2，3，4，5，6，7，8），并留有一个空格，如图所示。通过移动棋子，可以生成不同的棋盘状态。棋子移动规则如下： （1）与空格垂直、水平方向的数码棋子均可以移至空格处，每步只能移动一个棋子，棋子共有四种移法，如图所示的a、b、c、d。
（2）为了减少移动的次数，在移动过程中，约定同一种棋盘状态，不能重复出现。例如下图中，棋盘状态③和⑤相同，则从状态④不能选择d移动方法，但从状态③可以选择b移动方法，生成与已有状态不重复的新状态。
一种不合规定的棋子移动过程
重排九宫问题的状态树表示
在后图中，画出了只移动4步的情况下，所生成的重排九宫问题的五层状态树。 （1）图中S0表示棋盘的初始状态，我们称为树的根节点。 （2）每移动一个棋子，称为一次操作，通过前面的实践，我们知道，对于任意棋盘状态来说，最多只有四种操作a、b、c、d。在树种用节点间的连线表示操作，如SO与B1之间的连线表示操作a（空格左方的棋子右移）。
（3）每进行一种操作，就会生成一个新的棋盘状态。若把生成的新状态按先后次序连接起来，如上图中：S0—B1、B1—C1、B1—C2、S0—B2、SO—B3、SO—B4，依次类推，可以构成重排九宫问题的状态树。
我们以下图为例，说明一些树的术语。
（1）层：树的最高层为第0层，向下依次为树的第1层、树的第2层，依次类推为第3层、第4层……（2）根节点：第0层的节点为树的根，对于一棵树来说根是唯一的（上图中节点SO是树的根)。（3）分支：图中节点间连线为树的分支，表示从一个节点生成另一个节点的操作。（4）分支节点：中间状态为树的分支节点，如B1，C2等。