N-Puzzle

• N-Puzzle
  • 一、实验简介
    • 1.1 重排拼图游戏（N-数码问题）
    • 1.2 实验目的
  • 二、搜索策略介绍
    • 2.1 盲目搜索策略
      • 2.1.1 BFS基本思想
      • 2.1.2 BFS算法步骤
    • 2.2 启发式搜索
      • 2.1.1 基本思想
      • 2.1.2 估价函数
      • 2.1.3 算法步骤
  • 三、实验软装置介绍
    • 3.1 拼图的数据结构
    • 3.2 代码说明
  • 四、实验任务
    • 4.1 演示程序
    • 4.2 实验任务一
    • 4.3 实验任务二
  • 五、Application Programming Interface（API）
    • 5.1 JigsawNode类
    • 5.2 Jigsaw类
    • 5.3 Solution类
    • 5.4 演示脚本Runners
    • 5.5 测试脚本main

一、实验简介

1.1 重排拼图游戏（N-数码问题）

以3*3拼图（8-数码问题）为例，在3*3的方格棋盘上，放置8个标有1、2、3、4、5、6、7、8数字的方块和1个空白格，空白格可以上下左右移动。要求通过反复移动空白格，寻找一条从某初始状态到目标状态的移动路径，如图1所示。

重排拼图游戏也叫N-数码问题(N-puzzle,N=M*M-1)，高维数码问题（如15数码、24数码）常常被用来作为一些搜索算法的测试实例。本实验需要用到软装置Jiasaw。

图1 八数码问题（红色块表示空白格）

1.2 实验目的

通过完成重排拼图游戏，加深对搜索策略的理解和应用：

1. 学会利用广度优先搜索算法求得指定8-数码问题（3*3拼图）的最优解；
2. 学会利用启发式搜索算法求解随机生成的24-数码问题（5*5拼图）。

二、搜索策略介绍

2.1 盲目搜索策略

用于搜索的方法可分为两大类：盲目搜索和启发式搜索。深度优先搜索(Depth-First-Search)和广度优先搜索(Breadth-First-Search)是常见的盲目搜索方法，它们在搜索节点时都采用固定的排序，没有考虑问题领域可应用的知识，也称为无信息引导的搜索策略。

在走迷宫题目中，我们介绍了深度优先搜索算法，这里我们介绍另一种盲目搜索算法——广度优先搜索。

2.1.1 BFS基本思想

从图中某节点V出发，在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使”先被访问的节点的邻接点”先于”后被访问的节点的邻接点”被访问，直至图中所有已被访问的节点的邻接点都被访问到。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程。图2是一个广度优先搜索算法的示意图。

BFS总是尽可能”广”地搜索每一个节点的邻接点，能够找到从源结点到目标结点的最短路径，因而本实验采用它来求8-数码问题的最优解。

图2 广度优先搜索(BFS)算法示意图（拼图状态旁边的序号代表访问顺序）

2.1.2 BFS算法步骤

1. 将起始节点放入一个open列表中。

2. 如果open列表为空，则搜索失败，问题无解；否则重复以下步骤：

   a. 访问open列表中的第一个节点v，若v为目标节点，则搜索成功，退出。

   b. 从open列表中删除节点v，放入close列表中。

   c. 将所有与v邻接且未曾被访问的节点放入open列表中。

2.2 启发式搜索

2.1.1 基本思想

与盲目搜索不同，启发式搜索（如A*算法）利用问题拥有的启发信息来引导搜索，动态地确定搜索节点的排序，以达到减少搜索范围，降低问题复杂度的目的。

在N-数码问题中，每搜索到每一个节点时，通过”估价函数”对该节点进行”评估”，然后优先访问”最优良”节点的邻接节点，能够大大减少求解的时间。

2.1.2 估价函数

估价函数f(n)用来估计节点n的重要性，表示为：从起始节点，经过节点n，到达目标节点的代价。f(n)越小，表示节点n越优良，应该优先访问它的邻接节点。可参考的估价方法有：

1. 所有 放错位的数码 个数
2. 所有 放错位的数码与其正确位置的距离 之和
3. 后续节点不正确的数码个数
4. ……

可以同时使用多个估价方法，f(n) = a*f1(n) + b*f2(n) + ... 通过适当调整权重(a,b,...)，能够加快搜索速度。

2.1.3 算法步骤

1. 将起始节点放入一个列表中。

2. 如果列表为空，则搜索失败，问题无解；否则重复以下步骤：

   a. 访问列表中的第一个节点v，若v为目标节点，则搜索成功，退出。

   b. 从列表中删除节点v。

   c. 利用估价函数，对所有与v邻接且未曾被发现的节点进行估价，按照估价大小（小的在前）插入列表中。

三、实验软装置介绍

在本实验中，拼图被抽象为一个数据结构——JigsawNode类，求解拼图的过程则在Jigsaw类和Solution类中完成。要求在Solution类中实现搜索算法，运行Runner*演示脚本熟悉拼图任务（N-数码问题），最终在main测试脚本中评判求解结果。

3.1 拼图的数据结构

JigsawNode类描述了拼图的数据结构，包括两个重要元素：”节点状态”和”节点操作”。5.1节有JigsawNode类的详细文档。

1. 节点状态（以3*3拼图为例）

   每一拼图状态称为一个节点状态，由一个10元数组nodesState表示。例如，图4的状态表示为｛5，1，2，3，7，0，8，6，5，4｝。其中，第1位代表空白格所处位置，其余9位分别代表每一格中所放方块的数值（按照先行后列排序）。

   

   图3 某一节点状态（红色块表示空白格）

2. 节点操作

   重排拼图游戏的操作过程，在实验中表示为对节点状态的操作，由以下四个类方法实现。如果空白格处于边缘位置，则可能无法向某些方向移动，返回false。

   方法	作用	返回值
   public boolean moveEmptyUp()	空白格向上移	成功返回true 失败返回flase
   public boolean moveEmptyDown()	空白格向下移	成功返回true 失败返回flase
   public boolean moveEmptyLeft()	空白格向左移	成功返回true 失败返回flase
   public boolean moveEmptyRight()	空白格向右移	成功返回true 失败返回flase

3.2 代码说明

本实验的软装置与GridWorld没有关联，这里包含三个类：JigsawNode类、Jigsaw类、Solution类(继承Jigsaw)，以及三个演示脚本和一个评分脚本。第五部分(API)有代码的详细说明文档。

JigsawNode类是拼图的数据结构，包含节点状态和节点操作这两个重要的元素，在3.1节已作介绍，5.1节有详细说明。

Jigsaw类则是完成搜索的地方，其中存储了拼图的初始状态、目标状态以及当前状态，以及与拼图游戏相关的其他数据和方法。演示脚本RunnerDemo.java使用了ASearch(JigsawNode bNode, JigsawNode eNode)求解随机8-数码问题（3*3拼图）；实验任务一要求在Solution类的BFSearch(JigsawNode bNode, JigsawNode eNode)中修改广度优先搜索算法；实验任务二要求修改estimateValue(JigsawNode jNode)方法，完成用启发式搜索求解24-数码问题（5*5拼图）。

Runners目录中包含了1个基本的演示脚本和2个实验任务演示脚本。

main脚本评判求解效率。

四、实验任务

4.1 演示程序

（Demo）运行演示脚本RunnerDemo.java，求解随机8数码问题（3*3拼图）。参照2.2节，阅读Jigsaw类中的ASearch(JigsawNode bNode, JigsawNode eNode)和estimateValue(JigsawNode jNode)方法。熟悉JigsawNode类和Jigsaw类。

4.2 实验任务一

利用广度优先搜索求出指定N-数码问题的最优解。

如图4所示，指定初始状态为

{5,1,5,2,7,0,4,6,3,8} 目标状态为

{9,1,2,3,4,5,6,7,8,0}

图4 指定的8-数码问题

RunnerPart1.java演示脚本对应以上8-数码例子。但在评判脚本main.java中测试的是24-数码。

要求参照2.1节，在Solution类中修改广度优先搜索算法BFSearch(JigsawNode bNode, JigsawNode eNode)求得最优解，即是从初始状态到达目标状态的步数最少的移动路径。

具体要求：

1. 只能修改Solution类中的BFSearch(JigsawNode bNode, JigsawNode eNode)函数，可在Solution类添加其他函数，属性。其余代码不能更改，否则可能导致评测时编译或运行失败
2. 要求求解成功后：
   • 能通过getPath()方法得到解路径

注意：所有可能的节点状态为25!/2种，因而采用广度优先搜索求解随机初始状态的5*5拼图可能需要花费较长时间，所以保证在最终测例的最短路径长度不超过11。

4.3 实验任务二

（5分）利用启发式搜索求解随机生成的24-数码问题（5*5拼图）

参照2.3节，修改Solution类中的代价估计函数estimateValue(JigsawNode jNode)，对随机生成的5*5拼图初始状态进行求解。

具体要求：

1. 只能修改Solution类中的estimateValue(JigsawNode jNode)函数，可在Solution类中添加其他函数，属性。其余代码不能更改，否则可能导致评测时编译或运行失败
2. 要求访问节点总数不超过29000个

五、Application Programming Interface（API）

5.1 JigsawNode类

5.2 Jigsaw类

5.3 Solution类

5.4 演示脚本Runners

5.5 测试脚本main

简单读取测例进行结果评判。可无视。