人工智能57657238

1、精品资料推荐真空吸尘器问题一实验目的在人工智能领域，有一个重要部分，是研究智能化智能体的。智能体可以被 视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。 本实验分 析真空吸尘器这个简单反射型智能体、环境以及它们之间的关系。验证该吸尘器 是否是理性智能体（行为表现尽可能好的智能体）。二实验内容1. 智能体的描述智能体可以被视为通过传感器感知所处环境并通过执行器对该环境产生作 用的东西。人类智能体具有眼睛、耳朵和其它器官作为传感器，也具有手、腿和 身体的其它部位作为执行器。机器人智能体则可能用摄像头、红歪测距仪作为传 感器，各种马达作为执行器。简单放射型智能体直接对感知信息做出反应。

2、智能体传感器感知r1S？环境执彳器行动图2 1智能体通过传感器和执行器与环境进行交互2. 真空吸尘器的描述真空吸尘器属于简单智能体的一种，真空吸尘器世界只有两个地点：A地点和B地点。一个吸尘器智能体可以感知它处于哪个方格中，以及该地点是否有灰尘。它可以选择向左移动，向右移动，吸取灰尘，或者什么也不做。机器人所处位置有两种选择，要么在 A,要么在Bo A、B两地点的状态分别有两种，干净 或脏。A、B两地具体状态及吸尘器的行动如下表：序号吸尘器所处位置A地点状态B地点状态吸尘器的行动情况1A干净干净没有地点需要清扫，吸尘 器不动2A干净脏清扫B地点，吸尘器不动3A脏干净清扫A地点，吸尘器不动4A脏

3、脏先清扫A地点，再到达B地点，并清扫B地点5B干净干净没有地点需要清扫6B脏干净清扫A地点，吸尘器不动7B干净脏清扫B地点，吸尘器不动8B脏脏先清扫B地点，再到达A地点，并清扫A地点表2 1 A、B两地具体状态及吸尘器的行动3. 开发环境所使用的软件：VC+6.0程序说明：在程序中吸尘器所处位置用1、2表示，分别表示 A B两地。A B两地的 状态用0、1表示，分别表示干净不需要清扫、脏需要清扫。通过吸尘器对环境 的判断得知A、B两地干净与否，再来回移动进行清扫。174.吸尘器程序流程图开始C清扫B地点结束图2 2程序流程图三实验结果分析图3 1状态一图3 1状态二图3 1状态三说明杭器人防处

4、傥豊琴数为1和2时，分别表击 机豁八现正卍此点和匚址点：辿点伏志莖戲为询 1河帶別表示谍惟点不H5奚潢扫和需黑満扫”12 匚 leaner fx誌也点已蓿扫三毕图3 1状态四析黯人所址悅置选择祸点狀态出也点状态开赠说明机霧人所处位置谢數为1和2时分別表示 机器人现在瞇点和B他点：地点伏态参数为0和 1时，分别表云读馳点不盍要舌押和需要洁押图3 1状态五T二 Cleaner开始机踣人所处位置参数为1和啊I分别表示 机品人现在眦点和F地点；地点茁态参数討D和 1时，分別示融点不需零淸扫和需誓港彳玉图3 1状态六图3 1状态七图 3 1 状态八四 收获与心得本实验通过对简单智能体真空吸尘器的研究，

5、使我加深了对智能体、 环 境、性能度量等概念的理解。 通过传感器的感知可以得到环境的感知信息， 智能 体通过感知到的信息进行判断， 再通过执行器行动， 然后引起状态的变化， 再反 馈给环境。在这个过程中，性能度量即智能体成功程度标准的具体化是重要的。 吸尘器是一个简单的反射型智能体，它通过传感器感知外面的环境是什么情况 的，然后我们点一下 “确定”按钮即执行器， 执行行动， 之后把状态反馈给环境。 由此可见， 环境的变化引起智能体行动的变化， 反过来，智能体的行动对环境也 会产生影响，它们是联系在一起的。这个程序的开发环境是 VC+6.0,这也使我对VC软件的编程环境、编程方 法等有了进一步的

6、了解。完成人工智能作业的同时，也学了一些 VC的知识，这 对我以后的学习会有很大帮助，也增强学 VC的信心。收获的同时，我也发现了自己学习中的不足， 在以后的学习生活中一定改正。 另外，在实验的过程中， 我得到了老师耐心细致的指导和同学热心的帮助， 在这 里对她们表示感谢！八数码问题一 “八数码问题”的描述八数码问题一般描述：在3 X 3的方格棋盘上，分别放置标有数字1、2、3、 4、5、6、7、8 的八张牌，第九张牌不标数字，记为空格，空格用 0 表示，空格 周围的棋子可以移动到空格中。给定一种初始状态和目标状态，通过移动空格， 使得棋盘从初始状态向目标状态转换 （其中操作空格可用的操作有：

7、 左移、上移、 右移、下移，但不能移出棋盘之外） ，通过搜索策略寻找从初始状态到目标状态 的解路径。二 “八数码问题”是否有解的判断1“八数码问题”是否有解的判断的目的：有的八数码排列顺序是无解的， 如果再进行搜索就会浪费很多时间， 最终还 得不到结果。为了避免无解的情况下盲目搜索，判断是否有解是必要的。2. 八数码问题有解无解的结论：一个状态表示成一维的形式， 求出除 0 之外所有数字的逆序数之和， 也就是 每个数字前面比它大的数字的个数的和， 称为这个状态的逆序。 若两个状态的逆 序奇偶性相同，则可相互到达，否则不可相互到达。可以证明，八码问题有解的 充分必要条件是两个状态的逆序列奇偶性相

8、同。 为此，无解判定问题转化为计 算两个状态的逆序列奇偶性问题，由于原始状态的逆序为0（偶数），则逆序为偶数的状态有解。 也就是说， 逆序的奇偶将所有的状态分为了两个等价类， 同一 个等价类中的状态都可相互到达。3. 简要说明：当左右移动空格时， 逆序不变。 当上下移动空格时， 相当于将一个数字向前 （或向后）移动两格，跳过的这两个数字要么都比它大（小） ，逆序可能 2；要 么一个较大一个较小，逆序不变。所以可得结论：只要是相互可达的两个状态， 它们的逆序奇偶性相同。三 “八数码问题”的搜索方法原理搜索是人工智能中的一个基本问题， 也是模拟仿真中研究的一般性问题， 是 推理不可分割的一部分。

9、现实世界中的大多数问题都是结构不良或非结构化的 问题，一般不存在现成的求解方法，而只能利用已有的知识一步步地摸索着前进。解决八数码问题的常用方法为图搜索法， 可用无信息搜索算法（包括广度优 先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入搜索、双向搜 索）和有信息搜索算法（包括贪婪最佳优先搜索、A*算法、递归最佳优先搜索）实现，其中A*算法又因评价函数的不同而有着不同的搜索时间。1.无信息搜索（盲目搜索 Unin formed search），即问题中提供的定义之外没 有任何关于状态的附加信息。可以做的事情只能是生成后继，并区分目标状态与 非目标状态。广度优先搜索（Broadth F

10、irst Search BFS）:首先扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依 此类推。通常，在下一层的任何节点扩展之前搜索树上层深度的所有节点都已经 扩展过了。图2 1 广度优先搜索搜索顺序该算法可以使用FIFO队列实现，初始时将开始结点放入队列中，每次取队 头结点，判断是否为终结点，不是则将其所有子结点放入队列尾， 直到队列为空 或者找到目标结点为止。如果目标结点在深度d，那么该算法扩展完深度小于d 的结点后就将找到目标结点。而且，显然这是最优的。 容易观察到，在根节点的第一子层有 b 个结点，第二子层有 b2 ，然后 b3， 以此类推。在最坏情况下，我们将扩展为目标

11、结点前的所有结点，在 d + 1 层 扩展bd+1-b 个，那么将总共扩展：b + b2 + b3 + + bd + (bd+-b) = 0(bd+1) 由此可见，该算法的空间要求是相当高的。广度优先搜索算法伪代码描述如下(队列实现) ：Status BFS()Push_back(begin);doCurrentState=Top();Pop();if(Solution(CurrentState)return Success;for each successor of CurrentState doif(!Exist(successor)Push_back(successor);while(!

12、Empty();Return NoAnswer;(2) 深度优先搜索( Depth First Searc h， DFS)： 总是扩展搜索树当前边缘中最深的节点。搜索直接推进到搜索树的最深层， 那里的节点没有后继节点。 当那些节点扩展完之后， 它们被从边缘中去掉， 然后 搜索算法“向上回到”下一个还有未扩展后继节点的稍浅的节点。深度优先算法伪代码描述如下(堆栈实现)：Status DFS()Push(begi n);doCurre ntState = Pop();if(Solutio n(Curre ntState)retur n Success;for each successor of C

13、urren tState doif( !Exist(successor)Push(successor);while(!Empty();return NoA nswer;(3)深度有限搜索：(Depth Limited Search, DLS):无边界的搜索树问题可以通过对深度优先搜索提供一个预先设定的深度限制L来解决。就是说，深度为L的节点被当作没有后继的节点对待。2.有信息搜索， 是一种在问题本身定义之外还利用问题的特定知识的搜索策 略如何能够比无信息的搜索策略更有效地找到解。A*搜索算法：最佳优先搜索最广为人知的形式称为 A*搜索，它把到达节点的耗散 g( n)和 从该节点到目标节点的消耗

14、h(n)结合起来，对节点进行评价：f(n)= g(n) +h(n)。因 此，此搜索策略是基于每个扩展点的评价函数进行选择， 即评选出最佳的节点扩 展搜索。 A* 算法属于一种启发式搜索 ,它扩展结点的次序类似于广度优先搜索 ,但 不同的是每生成一个子结点需要计算估价函数f,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价 ;每当扩展结点时 ,意是在所有待扩展结点中选 择具有最小 f 值的结点做为扩展对象 ,以便使搜索尽量沿最有希望的方向进行。A* 算法只要求产生问题的全部状态空间的部分结点及关系,就可以求解问题了 ,搜索效率较高。A* 搜索算法伪代码描述如下 (优先队列实现 -prio

15、rity_queue)：Status Greedy-Search ()priority_queue Q;begin.f = h(begin);Q.Push_back(begin);doCurrentState = Q.Top();Q.Pop(); if(Solution(CurrentState) ) return Success;for each successor of CurrentState do if( !Exist(successor) ) successor.f = successor.g + h(successor);Q.Push_back(successor);while(!

16、Q.Empty() ); return NoAnswer;四 所用程序相关说 明1.使用软件： VC+6.02.具体内容：在这个程序中，分别用广度优先、深度优先和A* 算法实现了八数码问题， 初始状态值和目标状态值自己任意设定，空格周围的棋子可以移动到空格中，一步一步往下进行，直至达到目标状态，搜索过程中的每一步都有 显示，这样更便于理解每一步的运行情况。另外，此程序除了实现了八数码问题求解外，还推广应用于16数码问题，即在4X 4的方格棋盘上，分别放置标有数字1、2、3、4、5、6、7、8、9、A、B、C、D、E、F的十五张牌，第十六张牌不标数字，记为空格，空格用 0 表示，空格周围的棋子可

17、以移动到空格中。五实验结果分析1.实验结果图如下：搜索算法:初始状;态r r rF F 2 厂|o厂不能由棋盘初始布局劉达目标布局T-2 -O -61000开始搜索图5-1广度优先搜索算法（无解情况）Chess -|f F |Trrr|F瞞状态FFTFFFF F F探度估寸；ioT S 4图5-2广度优先搜索算法（八数码）精品资料推荐21|FJ需辑堵肉hTv搜索算注一尸度优先:初始状崙|F 5T甘檢状捋F亍匠100QA0pEc:a$8J14FAGcB9E7(5J3114图5-3 广度优先搜索算法（十六数码）图5-5深度优先搜索算法（八数码）*- Chess -无标营攫索算:去際度比先-3+3r

18、曲4册伏态F FFF F目标横态|FFF T4睥度14计2 loooF精品资料推荐MTU茯度估th iooos丽嘛算iS：ism -:夥（* &+4枕始鮭F F F F 莎 亍F F F F F 6 |T o FF图5-6 深度优先搜索算法（十六数码）23精品资料推荐搜索算法:肛算法初始状态-|F |T F|F一目檢状态-| |2 f3 T FT图5-7 A*搜索算法（无解情况）25釋度估计：1000珈捜索精品资料推荐2. 三种算法的优缺点简评 ： 三种算法在一定条件下均可得到八数码问题的解。前两种是经典的无信息（盲目）搜索算法，后一种是经典的有信息（启发式）搜索算法。 从本文的实验可以看出，广度优先搜索是一种完备策略，即只要问题有解， 它就一定可以找到解。 并且， 广度优先搜索找到的解， 还一定是路径最短的解。 这些都是广度优先搜索的优点。 当然， 广度优先搜索也存在很多缺点， 主要缺点 是盲目性较大，尤其是当目标行点距初始