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