人工智能实验报告八数码难题

1 昆明理工大学信息工程与自动化学院学生实验报告昆明理工大学信息工程与自动化学院学生实验报告 201 201 学年学年 第第 一一 学期学期 课程名称 课程名称 开课实验室 开课实验室 年年 月月 日日 年级 专业 年级 专业 班班 学号学号 姓名姓名 成绩成绩 实验项目名称实验项目名称八数码难题八数码难题指导教师指导教师 教教 师师 评评 语语 该同学是否了解实验原理 A 了解 B 基本了解 C 不了解 该同学的实验能力 A 强 B 中等 C 差 该同学的实验是否达到要求 A 达到 B 基本达到 C 未达到 实验报告是否规范 A 规范 B 基本规范 C 不规范 实验过程是否详细记录 A 详细 B 一般 C 没有 教师签名 教师签名 年年 月月 日日 一 实验内容一 实验内容 八数码难题 问题描述 在 3 3 方格棋盘上 分别放置了标有数字 1 2 3 4 5 6 7 8 的 八张牌 初始状态 S0 目标状态 S1 如图所示 可以使用的操作有 空格上移 空格左移 空格右移 空格下移 只允许位于空格左 上 右 下方的牌移入空格 用广度优先搜索 策略寻找从初始状态到目标状态的解路径 二 实验原理二 实验原理 算法思想 算法思想 这是一种盲目搜索算法 算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展 结点 并逐一检查这些后继结点是否为目标结点 若不等于目标结点则把该后继结点插入到 数组末尾 然后取数组中未扩展的第一个结点重复以上操作 直到得到目标结点为止或在限 定步数以内未得到解 2 广度优先搜索策略数据结构 广度优先搜索策略数据结构 void Bfs queue Queue Queue push org HashTable org myindex 1 while NOT Queue empty Map node Queue front Queue pop for int k 0 k 4 k Map tmp node tmp position node position derection k if tmp position 8 k 1 tmp myindex HashValue node k if 0 HashTable tmp myindex continue tmp detail node position tmp detail tmp position tmp detail tmp position 0 HashTable tmp myindex node myindex 状态记录到 hashtable 中 if node myindex EndIndex return Queue push tmp return 三 所用仪器 材料三 所用仪器 材料 1 台 PC 及 VISUAL C 6 0 软件 四 实验方法 步骤四 实验方法 步骤 源代码见同一文件夹中源代码见同一文件夹中 bashuma cpp 部分程序代码 部分程序代码 typedef struct Node int num 9 int deepth int diffnum int value struct Node pre struct Node next 3 struct Node parent numNode int main int argc char argv open create numNode close create numNode open pre open next close pre close next NULL init 由用户输入初始和目标状态 numNode p1 p1 create numNode p1 parent NULL p1 deepth 0 int i 0 for i 0 inum i origin i open insert open p1 numNode num 1 p1 open getfirst open while p1 NULL close append close p1 if expand p1 return EXIT SUCCESS p1 open getfirst open printf No solution n return EXIT SUCCESS void init while 1 printf 输入初始状态 S0 请从左到右依次输入每行数字 0 代表空格 n char temp 10 scanf s int i 0 for i 0 i 0 i origin i temp i 0 4 printf 请输入目标状态 S1 n scanf s int j 0 for j 0 j 0 j target j temp j 0 system cls if i 9 int operate int m int op int blank blank 0 while m blank 0 break case 2 down if blank 6 swap m blank m blank 3 break case 3 left if blank 0 break case 4 right if blank 2 break default return 1 return 0 五 实验过程原始记录五 实验过程原始记录 5 六 实验总结 六 实验总结 人工智能这门课程综合了许多学科的知识 这些知识面十分广 以及它 的应用也是十分广泛的 才刚开始学习的时候就会感觉有点复杂 因为它毕竟 综合了一些我们还没有学过的知识 通过这次实验 我对八数码难题有了更进 一步的认识 对广度优先搜索策略更加熟悉 广度优先搜索策略在有解的情形 总能保证搜索到最短路经 也就是移