程序设计实习：14.2广搜与八数码问题

广度优先搜索 八数码问题：

八数码问题是人工智能中的经典问题 有一个3*3的棋盘，其中有0-8共9个数字，0表示空格， 其他的数字可以和0交换位置。求由初始状态 到达目标状态 1 2 3 4 5 6 7 8 0 的步数最少的解。

状态空间：

广度优先搜索（bfs） 优先扩展浅层节点(状态），逐渐深入

广度优先搜索，用队列保存待扩展的节点 从队首队取出节点，扩展出的新节点放入队尾， 直到队首出现目标节点（问题的解）。

广度优先搜索的代码框架：

关键问题：判重，新扩展出的节点如果和以前扩展出的节点相同， 则则个新节点就不必再考虑 ，如何判重？

关键问题：判重 状态(节点）数目巨大，如何存储？ 怎样才能较快判断一个状态是否重复？

用合理的编码表示“状态”，减小存储代价 方案一：

用合理的编码表示“状态”，减小存储代价 方案二：

用合理的编码表示“状态”，减小存储代价 方案三：

用合理的编码表示“状态”，减小存储代价 方案四：

给定排列求序号：

整数 1,2…k的一个排列： a1 a2 a3 …ak 求其序号 基本思想：算出有多少个排列比给定排列小。 先算1到a1-1放在第1位，会有多少个排列: (a1-1)* ((k-1)!) 再算a1不变，1到a2-1 放在第2位(左边出现过的不能再用），会有多少个排 列: (a2-1)* ((k-2)!) 再算a1，a2不变，1到a3-1 放在第3位，会有多少个排列 ….全加起来。 时间复杂度：O(n2 ) 3241 1,2放在第一位，有 2*3! = 12 种 3在第一位，1放在第2位，有 2! = 2种 32？ 1放在第3位，有 1种 =>前面共 12+2+1 = 15种。所以 3241是第16个排列

1234的排列的第9号 第一位假定是1，共有3!种，没有到达9,所以第一位至少是2 第一位是2,一共能数到 3!+3!号，>= 9,所以第一位是2 第二位是1，21??,一共能数到 3!+2! = 8 不到9，所以第二位至少 是 3 第二位是3，23??,一共能数到 3!+2!+2! >= 9,因此第二位是3 第三位是1，一共能数到3!+2!+1 = 9,所以第三位是1，第四位是 4 答案：2314 时间复杂度：O(n2 ) 给定序号n求排列： 20 时间与空间的权衡 对于状态数较小的问题，可以用最直接的方式编 码以空间换时间 对于状态数太大的问题，需要利用好的编码方法 以时间换空间 具体问题具体分析

用广搜解决八数码问题(POJ1077)：

八数码问题有解性的判定：

八数码问题的一个状态实际上是0~8的一个排列，对于任意给定的初始状态和 目标，不一定有解，即从初始状态不一定能到达目标状态。 因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。 如果一个数字0~8的随机排列，用F(X) (X!=0)表示数字X前面比它小的数的个 数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称该排列是奇排列， 如果Y为偶数则称该排列是偶排列。 871526340排列的 Y=0+0+0+1+1+3+2+3=10，10是偶数，所以是偶排列。 871625340排列的Y=0+0+0+1+1+2+2+3=9 9是奇数，所以是奇排列。 因此，可以在运行程序前检查初始状态和目标状态的奇偶性是否相同，相 同则问题可解，应当能搜索到路径。否则无解。

证明：移动0的位置，不改变排列的奇偶性 a1 a2 a3 a4 0 a5 a6 a7 a8 a9 0向上移动： a1 0 a3 a4 a2 a5 a6 a7 a8 a9