Back
History
作业1: 推盒子游戏
([course_ai15|Back to course page]) ==问题描述== 在一个九宫格中，格子编号为a到i（如下图(a)）。有8个记号为1到8的盒子，游戏的目的是将这8个盒子按照下图(b)的位置放置。然而在游戏开始时，8个盒子的位置被打乱，例如下图(c)中所示。盒子<font color="blue">不可以</font>随意移动，而只能借助空出的格子来移动。 移动规则：每一次只能在 U (Up)、D (Down)、L (Left)、R (Right) 四个动作中选择一个动作执行，执行的结果是分别将空出格子的 上、下、左、右 的盒子移动到空格子中。例如，在下图(c)的情况下，格子g为空，执行动作R，则将格子g右侧的盒子1移动到格子g。 [image||{UP}course_ai15_hw1/hw1.png] ==作业内容== 请使用以下四种方法（都需实现），对于任意给出的初始摆放，给出变换为目标放置位置的<font color="blue">最短动作序列</font>，或告知无解： * 宽度优先搜索 * 深度优先搜索 * A*搜索 * 遗传算法搜索 对于A*搜索，尝试使用启发式函数 {{{{h = 当前盒子位置与目标位置相同的个数}}}}并尝试改进这个启发式函数。 对于遗传算法，尝试定长或变长编码，尝试使用适应值函数 {{{{f = 当前盒子位置与目标位置相同的个数}}}}并尝试改进这个适应值函数。 ==程序约定== 编程语言不限 输入：按格子a到i的顺序，输入0到8这9个数字的排列，其中0表示没有盒子。例如235874016，表示格子a放盒子2，格子b放盒子3，...，格子g没有盒子，...，即上图(c)的位置。 输出：1.动作序列，2.动作序列长度，3.搜索的九宫格状态数量。 ==作业报告== 使用 [{UP}course_ai15_hw1/template-2.doc|这个文档模版(点击下载)] 撰写实验报告。 报告交代实现细节、使用的测试输入、得到的输出、不同方法搜索状态数量、以及做出的改进等。 ==作业提交== 将 <font color="blue">作业报告 和 源代码</font> 压缩为.ZIP文件，用学号命名，例如131221001.zip 上传到 {{ftp://lamda.nju.edu.cn/AI/assignment1/}} (用户名: ai15, 密码: ai15)<br/> (注意：该ftp不能替换文件，上传一次后，如果需要修改，请在文件名后加上版本号再上传，例如131221001-1.zip) 注意：<font color="red">作业严禁抄袭！</font>
The end