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