作业1: 推盒子游戏

Modified: 2015/03/22 12:08 by admin - Uncategorized
(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。

Image

Edit

作业内容

请使用以下四种方法(都需实现),对于任意给出的初始摆放,给出变换为目标放置位置的最短动作序列,或告知无解:
  • 宽度优先搜索
  • 深度优先搜索
  • A*搜索
  • 遗传算法搜索

对于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)

注意:作业严禁抄袭!

The end