人工智能论文

淮北师范大学淮北师范大学 计算机科学与技术学院计算机科学与技术学院 0909 级网络工程级网络工程 题目 人工智能中用 A 算法解决八数码问题 学 号 21 姓 名 1 专 业 网络工程 课 程 1 2012 年 6 月 12 日 问题说明 问题说明 八数码问题是人工智能中一个很典型的智力问题 本文以状态 空间搜索的观点讨论了八数码问题 给出了八数码问题的 Java 算法 与实现的思想 分析了 A 算法的可采纳性等及系统的特点 关键词 九宫重排 状态空间 启发式搜索 A 算法 1 引言九宫重排问题是 人工智能当中有名的难题之一 问题是在 3 3 方格盘上 放有八个 数码 剩下一个位置为空 每一空格其上下左右的数码可移至空格 问题给定初始位置和目标位置 要求通过一系列的数码移动 将初 始状态转化为目标状态 状态转换的规则 空格四周的数移向空格 我们可以看作是空格移动 它最多可以有 个方向的移动 即上 下 左 右 九宫重排问题的求解方法 就是从给定的初始状态出 发 不断地空格上下左右的数码移至空格 将一个状态转化成其它 状态 直到产生目标状态 一 一 问题描述问题描述 1 11 1 待解决问题的解释待解决问题的解释 八数码游戏 八数码问题 描述为 在 3 3 组成的九宫格棋盘上 摆有八 个将牌 每一个将牌都刻有 1 8 八个数码中的某一个数码 棋盘中留有一个空 格 允许其周围的某一个将牌向空格移动 这样通过移动将牌就可以不断改变 将牌的布局 这种游戏求解的问题是 给定一种初始的将牌布局或结构 称初 始状态 和一个目标的布局 称目标状态 问如何移动将牌 实现从初始状态 到目标状态的转变 1 21 2 问题的搜索形式描述 问题的搜索形式描述 4 4 要素 要素 初始状态 8 个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间 其 中 状态空间中的任一种状态都可以作为初始状态 后继函数 通过移动空格 上 下 左 右 和周围的任一棋子一次 到达新的合法 状态 目标测试 比较当前状态和目标状态的格局是否一致 路径消耗 每一步的耗散值为 1 因此整个路径的耗散值是从起始状态到目标状态的棋 子移动的总步数 1 31 3 解决原理解决原理 对于八数码问题的解决 首先要考虑是否有答案 每一个状态可认为是一 个 1 9 的矩阵 问题即通过矩阵的变换 是否可以变换为目标状态对应的矩阵 由数学知识可知 可计算这两个有序数列的逆序值 如果两者都是偶数或奇数 则可通过变换到达 否则 这两个状态不可达 这样 就可以在具体解决问题 之前判断出问题是否可解 从而可以避免不必要的搜索 如果初始状态可以到达目标状态 那么采取什么样的方法呢 常用的状态空间搜索有深度优先和广度优先 广度优先是从初始状态一层一 层向下找 直到找到目标为止 深度优先是按照一定的顺序前查找完一个分支 再查找另一个分支 以至找到目标为止 广度和深度优先搜索有一个很大的缺 陷就是他们都是在一个给定的状态空间中穷举 这在状态空间不大的情况下是 很合适的算法 可是当状态空间十分大 且不预测的情况下就不可取了 他的 效率实在太低 甚至不可完成 由于八数码问题状态空间共有 9 个状态 对于 八数码问题如果选定了初始状态和目标状态 有 9 2 个状态要搜索 考虑到时 间和空间的限制 在这里采用 A 算法作为搜索策略 在这里就要用到启发式搜 索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估 得到 最好的位置 再从这个位置进行搜索直到目标 这样可以省略大量无畏的搜索 路径 提到了效率 在启发式搜索中 对位置的估价是十分重要的 采用了不 同的估价可以有不同的效果 启发中的估价是用估价函数表示的 如 f n g n h n 其中 f n 是节点 n 的估价函数 g n 是在状态空间中从初始节点到 n 节 点的实际代价 h n 是从 n 到目标节点最佳路径的估计代价 在此八数码问题 中 显然 g n 就是从初始状态变换到当前状态所移动的步数 估计函数 f n 我 们就可采用当前状态各个数字牌不在目标状态未知的个数 即错位数 二 二 算法介绍算法介绍 2 12 1 搜索算法一般介绍搜索算法一般介绍 不管哪种搜索 都统一用这样的形式表示 搜索的对象是一个图 它面向 一个问题 不一定有明确的存储形式 但它里面的一个结点都有可能是一个解 可行解 搜索的目的有两个方面 或者求可行解 或者从可行解集中求最优 解 搜索算法可分为两大类 无信息的搜索算法和有信息的搜索算法 无信息 的搜索又称盲目搜索 其特点是只要问题状态可以形式化表示 原则上就可用 使用无信息的搜索 无信息搜索有如下常见的几种搜索策略 广度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深入优先搜索 双向搜索 我们说 DFS 和 BFS 都是蛮力搜索 因为它们在搜索到一个结点时 在展开它的 后续结点时 是对它们没有任何 认识 的 它认为它的孩子们都是一样的 优秀 但事实并非如此 后续结点是有好有坏的 好 就是说它离目标结点 近 如果优先处理它 就会更快的找到目标结点 从而整体上提高搜索性能 为了改善上面的算法 我们需要对展开后续结点时对子结点有所了解 这 里需要一个估值函数 估值函数就是评价函数 它用来评价子结点的好坏 因 为准确评价是不可能的 所以称为估值 这就是我们所谓的有信息搜索 如果 估值函数只考虑结点的某种性能上的价值 而不考虑深度 比较有名的就是有 序搜索 Ordered Search 它着重看好能否找出解 而不看解离起始结点的距 离 深度 如果估值函数考虑了深度 或者是带权距离 从起始结点到目标结 点的距离加权和 那就是 A 如果不考虑深度 就是说不要求最少步数 移动 一步就相当于向后多展开一层结点 深度多算一层 如果要求最少步数 那就 需要用 A 简单的来说 A 就是将估值函数分成两个部分 一个部分是路径价值 另一个部分是一般性启发价值 合在一起算估整个结点的价值 考虑到八数码问题的特点 在本实验中使用 A 算法求解 A 搜索是一种效 的搜索算法 它把到达节点的耗散 g n 和从该节点到目标节点的消耗 h n 结合 起来对节点进行评价 f n g n h n 当 h n 是可采纳时 使用 Tree Search 的 A 算法将是最优的 2 22 2 算法伪代码算法伪代码 算法的功能 产生 8 数码问题的解 由初始状态到达目标状态的过程 输入 初始状态 目标状态 输出 从初始状态到目标状态的一系列过程 算法描述 Begin 读入初始状态和目标状态 并计算初始状态评价函数值 f 根据初始状态和目标状态 判断问题是否可解 If 问题可解 把初始状态假如 open 表中 While 未找到解 全局静态变量 表示目标状 态 class eight num private int num 9 定义八数码的初始状态 int not in position num 定义不在正确位置八数码的个数 int deapth 定义了搜索的深度 int eva function 评价函数的值 每次选取最小的进行扩展 public eight num parent 指向节点的父节点 eight num leaf next 指向 open 表的下一个节点 eight num leaf pre 指向 open 表的前一个节点 初始状态的构造函数 eight num int init num 9 eight num int num1 int num2 int num3 int num4 int num5 int num6 int num7 int num8 int num9 eight num void 计算启发函数 g n 的值 void eight num cul para void 显示当前节点的状态 void eight num show 复制当前节点状态到一个另数组中 void eight num get numbers to int other num 9 设置当前节点状态 欲设置的状态记录的 other 数组中 void eight num set num int other num 9 eight num class definition class eight num private int num 9 int not in position num int deapth int eva function public eight num parent eight num leaf next eight num leaf pre eight num int init num 9 eight num int num1 int num2 int num3 int num4 int num5 int num6 int num7 int num8 int num9 num 0 num1 num 1 num2 num 2 num3 num 3 num4 num 4 num5 num 5 num6 num 6 num7 num 7 num8 num 8 num9 eight num void for int i 0 i 9 i num i i void cul para void void get numbers to int other num 9 int get nipn void return not in position num int get deapth void return deapth int get evafun void return eva function void set num int other num 9 void show void eight num eight num int operator eight num int operator int other num 9 计算启发函数 g n 的值 void eight num cul para void int i int temp nipn 0 for i 0 iparent NULL deapth 0 else deapth this parent deapth 1 eva function not in position num deapth 构造函数 1 eight num eight num int init num 9 for int i 0 i 9 i num i init num i 显示当前节点的状态 void eight num show cout num 0 cout cout num 1 cout cout num 2 cout n cout num 3 cout cout num 4 cout cout num 5 cout n cout num 6 cout cout num 7 cout cout num 8 cout n 复制当前节点状态到一个另数组中 void eight num get numbers to int other num 9 for int i 0 i 9 i other num i num i 设置当前节点状态 欲设置的状态记录的 other 数组中 void eight num set num int other num 9 for int i 0 i 9 i num i other num i eight numi 9 i num i another 8num num i not in position num another 8num not in position num deapth another 8num deapth 1 eva function not in position num deapth return this eight numi 9 i num i other num i return this int eight num operator eight num for int i 0 i 9 i if num i another 8num num i match 0 break if match 0 return 0 else return 1 int eight num operator int other num 9 int match 1 for int i 0 i 9 i if num i other num i match 0 break if match 0 return 0 else return 1 class definition over 空格向上移 int move up int num 9 for int i 0 i 9 i if num i 0 break if i 3 return 0 else num i num i 3 num i 3 0 return 1 空格向下移 int move down int num 9 for int i 0 i5 return 0 else num i num i 3 num i 3 0 return 1 空格向左移 int move left int num 9 for int i 0 i 9 i if num i 0 break if i 0 i 3 i 6 return 0 else num i num i 1 num i 1 0 return 1 空格向右移 int move right int num 9 for int i 0 i 9 i if num i 0 break if i 2 i 5 i 8 return 0 else num i num i 1 num i 1 0 return 1 判断可否解出 int icansolve int num 9 int target 9 int i j int count num count target for i 0 i 9 i for j 0 j i j if num j num i if target j parent if p num return 1 return 0 寻找估价函数最小的叶子节点 eight num find OK leaf eight num start eight num p OK p OK start int min start get evafun for p start p NULL p p leaf next if min p get evafun OK p min p get evafun return OK 主函数开始 int main void double time clock t Start Finish int memery used 0 step 0 int num 9 int flag 0 是否输入错误标志 1 表示输入错误 int bingo 0 是否查找成功标志 1 表示成功 int i j cout Please input the number 0 for the blank n for i 0 i num i for j 0 j i j if num i num j flag 1 if num i 8 flag 1 i cout Illegle number tReinput n eight num S num Target target S parent S leaf next S leaf pre NULL S cul para memery used cout Now the initial numbers are n S show cout And the Target is n Target show if icansolve num target cout i return 1 Start clock eight num OK leaf while OK leaf NULL if OK leaf Target bingo 1 break p OK leaf leaf pre OK leaf get numbers to num if move up num new 8num set num num new 8num parent OK leaf new 8num cul para new 8num leaf pre p if p NULL leaf start new 8num else p leaf next new 8num p new 8num memery used OK leaf get numbers to num if move down num new 8num set num num new 8num parent OK leaf new 8num cul para new 8num leaf pre p if p NULL leaf start new 8num else p leaf next new 8num p new 8num memery used OK leaf get numbers to num if move left num new 8num set num num new 8num parent OK leaf new 8num cul para new 8num leaf pre p if p NULL leaf start new 8num else p leaf next new 8num p new 8num memery used OK leaf get numbers to num if move right num new 8num set num num new 8num parent OK leaf new 8num cul para new 8num leaf pre p if p NULL leaf start new 8num else p leaf next new 8num p new 8num memery used p leaf next OK leaf leaf next if OK leaf leaf next NULL OK leaf leaf next leaf pre p OK leaf leaf next OK leaf leaf pre NULL Finish clock if bingo 1 time double Finish Start 1000 CLOCKS PER SEC eight num p for p OK leaf parent p NULL p p parent cout show step cout Time cost cout time cout ms n cout Totaly covered steps cout step cout n else cout Fail to find return 0 对对 人工智能人工智能 中相关问题的理解与认识 中相关问题的理解与认识 人工智能 即用计算机来模拟人的思维活动 包含学习能力 理解能力 推理 能力 其主要是模拟脑功能的结构模拟和功能模拟 人工智能的发展 强烈依赖于计算机和生物技术 计算机技术提供了方便易用 的虚拟实验平台 可进行复杂算法的设计 虚拟生物环境的模拟 而生物技术 在生命智能的生理结构的应用 促进了对智能的物质基础的认识 人工智能涉及到多个领域 常包含了多学科的交叉 以下选取其中三个方向叙 述自己对人工智能特点的一些理解 人工神经网络 是高度复杂的模拟神经元的的兴奋与抑制活动的结构 是为通 过人脑结构生物结构 工作方式模拟 而设计出具有大脑局部功能的神经结构 基于生理结构上的实现 神经网络的结构决定了其并行工作的方式 实际通常 只基于模拟神经元 联结成较小的网络实现复杂的功能 如 Hopfield 网络 BP 网络 并不完全模拟整个人脑 这类网络基于一定的数学模拟 能够实现复杂 的控制算法 但不同于物理世界中的电路等基于特定规的网络 其能够根据外 界刺激进行自我修改 自组织 自学习的能力 神经网络可以和多种学科交叉融合 神经管理学是近年来在管理科学领域出现 的新的研究方向 在 Nature Science 管理科学相关顶级杂志上均有出现 以 神经科学 信号数据挖掘 行为分析 动态建模等方法为基础 融合了系统决 策 工业工程 营销工程与科学 金融工程等学科理论与方法 是将传统管理 行为在神经层面的科学化 神经网络的研究两个大的趋势 一是在理论上向更复杂的神经网络系统方 向发展 表现在神经网络与模糊 进化算法的结合 神经网络与认知科学的结 合 神经网络与生物医学的结合 以及各种混合神经网络的出现 二是神经网 络的应用范围不断扩展 神经网络应用技术研究不断深入 它与多种学科相交 叉 解决了很多传统科学解决不了的难题 目前对神经网络的模拟还处理宏观世界的水平 而对于量子世界的研究还相对 欠缺 基于冯 若依曼体系统的结构在客观上限制了神经网络的发展 因此 已有少数人开始将量子理论应用于神经网络 在网络的结构中和算法中应用量 子理论 如中科院半导体研究所开发的半导体神经计算机 可以预见 一旦在 量子理论的研究有所突破 引发计算机技术的革命 对人脑结构的模拟必定会 有飞跃性进步 专家系统是基于专家的知识和解决方法解决问题的智能计算机程序 基于知识 符号的分析 基于符号的推理 直接从脑的宏观功能出发 采用启发式程序或 推理方法模拟大脑功能 用户多采用提问的方式与迅家系统交互 专家系统通 常不会自己做出判断 逻辑推理 对用于用户的问题的解答是通过查询知识库 寻找相应的经验和知识 相对而言 这类专家系统的智力水平有限 并且强烈 依赖于知识库 因而知识在知识库中存储与表示 组织 及系统如何确定知识 极大的影响系统智能水平 为弥补不足 神经经网络协助建立专家系统 提供 自组织 自适应 自学习并可进行模糊推理 目前的一些专家系统通常只针对某一领域 知识面窄 推理能力弱 知识获取 困难 因而出