人工智能57657238

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

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

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

4、I和2时,分别表示机器人现在触也.点、和E地点；地.点.状忐梦非为口和 1时.芬刻表宗该地点不需要清扫和需要清扫.图31状态六图3-1状态七图3-1状态八四收获与心得本实验通过对简单智能体一一真空吸尘器的研究，使我加深了对智能体、环 境、性能度量等概念的理解。通过传感器的感知可以得到环境的感知信息，智能 体通过感知到的信息进行判断，再通过执行器行动，然后引起状态的变化，再反 馈给环境。在这个过程中，性能度量即智能体成功程度标准的具体化是重要的。吸尘器是一个简单的反射型智能体，它通过传感器感知外面的环境是什么情况 的，然后我们点一下“确定”按钮即执行器，执行行动，之后把状态反馈给环境。 由此可见

5、，环境的变化引起智能体行动的变化， 反过来，智能体的行动对环境也 会产生影响，它们是联系在一起的。这个程序的开发环境是 VC+6.0,这也使我对VC软件的编程环境、编程方 法等有了进一步的了解。完成人工智能作业的同时，也学了一些 VC的知识，这 对我以后的学习会有很大帮助，也增强学 VC的信心。收获的同时，我也发现了自己学习中的不足，在以后的学习生活中一定改正。 另外，在实验的过程中，我得到了老师耐心细致的指导和同学热心的帮助，在这 里对她们表示感谢！八数码问题一 “八数码问题”的描述八数码问题一般描述：在3X3的方格棋盘上，分别放置标有数字1、2、3、 4、5、6、7、8的八张牌，第九张牌不

6、标数字，记为空格，空格用 0表示，空格 周围的棋子可以移动到空格中。给定一种初始状态和目标状态，通过移动空格， 使得棋盘从初始状态向目标状态转换（其中操作空格可用的操作有：左移、上移、 右移、下移，但不能移出棋盘之外），通过搜索策略寻找从初始状态到目标状态 的解路径。二“八数码问题”是否有解的判断1 .“八数码问题”是否有解的判断的目的：有的八数码排列顺序是无解的，如果再进行搜索就会浪费很多时间， 最终还 得不到结果。为了避免无解的情况下盲目搜索，判断是否有解是必要的。2 .八数码问题有解无解的结论：一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，也就是 每个数字前面比它大的数字的

7、个数的和， 称为这个状态的逆序。若两个状态的逆 序奇偶性相同，则可相互到达，否则不可相互到达。可以证明，八码问题有解的 充分必要条件是两个状态的逆序列奇偶性相同。为此，无解判定问题转化为计算两个状态的逆序列奇偶性问题，由于原始状态的逆序为0 （偶数），则逆序为偶数的状态有解。也就是说，逆序的奇偶将所有的状态分为了两个等价类，同一个等价类中的状态都可相互到达。3 .简要说明：当左右移动空格时，逆序不变。当上下移动空格时，相当于将一个数字向前 （或向后）移动两格，跳过的这两个数字要么都比它大（小），逆序可能土 2;要 么一个较大一个较小，逆序不变。所以可得结论：只要是相互可达的两个状态， 它们的逆

8、序奇偶性相同。“八数码问题”的搜索方法原理也是模拟仿真中研究的一般性问题，是搜索是人工智能中的一个基本问题,推理不可分割的一部分。 现实世界中的大多数问题都是结构不良或非结构化的 问题，一般不存在现成的求解方法，而只能利用已有的知识一步步地摸索着前进。解决八数码问题的常用方法为图搜索法， 可用无信息搜索算法（包括广度优 先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入搜索、双向搜 索）和有信息搜索算法（包括贪婪最佳优先搜索、A*算法、递归最佳优先搜索）实现，其中A*算法又因评价函数的不同而有着不同的搜索时间。1 .无信息搜索（盲目搜索 Uninformed search）,即问题中提

9、供的定义之外没 有任何关于状态的附加信息。可以做的事情只能是生成后继，并区分目标状态与 非目标状态。（1）广度优先搜索（Broadth First Search BFS）:首先扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依 此类推。通常，在下一层的任何节点扩展之前搜索树上层深度的所有节点都已经 扩展过了。图21 广度优先搜索搜索顺序该算法可以使用FIFO队列实现，初始时将开始结点放入队列中，每次取队 头结点，判断是否为终结点，不是则将其所有子结点放入队列尾， 直到队列为空 或者找到目标结点为止。如果目标结点在深度d ,那么该算法扩展完深度小于d 的结点后就将找到目标结点。而且，

10、显然这是最优的容易观察到，在根节点的第一子层有b个结点，第二子层有b2,然后b3,以此类推。在最坏情况下，我们将扩展为目标结点前的所有结点，在 d + 1层 扩展bd+1-b 个，那么将总共扩展：b + b2 + b3 + + bd + (bd+-b) = O(bd+1) 由此可见，该算法的空间要求是相当高的。广度优先搜索算法伪代码描述如下(队列实现)：Status BFS()Push_back(begin);doCurrentState=Top();Pop();if(Solution(CurrentState)return Success;for each successor of Curr

11、entState doif(!Exist(successor)Push_back(successor);while(!Empty();Return NoAnswer;(2)深度优先搜索(Depth First Searc h, DFS):总是扩展搜索树当前边缘中最深的节点。搜索直接推进到搜索树的最深层， 那里的节点没有后继节点。当那些节点扩展完之后，它们被从边缘中去掉，然后 搜索算法“向上回到”下一个还有未扩展后继节点的稍浅的节点。0图22深度优先搜索搜索顺序深度优先算法伪代码描述如下(堆栈实现)：Status DFS()Push(begin);doCurrentstate = Pop();i

12、f(Solution(CurrentState)return Success;for each successor of CurrentState doif( !Exist(successor)Push(successor);while(!Empty();return NoAnswer;深度有限搜索：(Depth Limited Search, DLS):无边界的搜索树问题可以通过对深度优先搜索提供一个预先设定的深度限 制L来解决。就是说，深度为L的节点被当作没有后继的节点对待。2 .有信息搜索，是一种在问题本身定义之外还利用问题的特定知识的搜索策 略一如何能够比无信息的搜索策略更有效地找到解

13、。A*搜索算法：最佳优先搜索最广为人知的形式称为A*搜索，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来，对节点进行评价：f(n)= g(n) +h(n)。因 此，此搜索策略是基于每个扩展点的评价函数进行选择，即评选出最佳的节点扩展搜索。A*算法属于一种启发式搜索，它扩展结点的次序类似于广度优先搜索，但 不同的是每生成一个子结点需要计算估价函数f,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价；每当扩展结点时，意是在所有待扩展结点中选 择具有最小f值的结点做为扩展对象，以便使搜索尽量沿最有希望的方向进行。A*算法只要求产生问题的全部状态空间的部分结点及关系，就可

14、以求解问题了，搜索效率较高。A*搜索算法伪代码描述如下(优先队列实现-priority_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 doif( !Exist(successor) )successor.f = successor.g + h(succ

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

16、十五张牌，第十六张牌不标数字，记为空格，空格用 0 表示，空格周围的棋子可以移动到空格中。 五实验结果分析1.实验结果图如下:搜索算法；|广度优先二:鬻1.4*4-初始状态pF 丁 F F |2" F F b-目标状态F F F 济W广 pF 肉T深度估讨士 1000开始搜索图5-1广度优先搜索算法（无解情况）Chess -无标置搜索算法:深度估注1项初始犍r r r b目懒态炉灰F F图5-2广度优先搜索算法（八数码）搜索算法:初始状态DC目标状态HH|F T |b-6 5 0|T|F深度估计：000k* Chess -无标盏文件 编辑旧查看 帮助也）f 口3JMil开始搜索9&#

17、187;>ai£IUa文件更）编辑I查看也 帮助第齐耀嘉!i_.iis_.iis_.iis_-.iir|r* Chess -无标题支伴g编辑（1）查看 帮助如r r f 瓦目标状态|F TF图5-5深度优先搜索算法（八数码）-无标题深度估计：1 wormraaiiiBB Him iihii ii画搜索算法：1深度优先二；警' 4*4一初始状态一Ir r r r|T|FF F FF目标状态一f |e |5 卜F F FFH H搜索算法:A*算法* 3*34*4-初始状态-|T T F目标状态H ,H 7 1F深度估计：000开始搜索图5-7 A*搜索算法（无解情况）les

18、s - 5ESS深度估讯1000ffiSi初始蟋|F目标精FFF FFF蜴算法:初始状态一 F |T |T B 目标脑一 F底/H|T |? |6 |5 |0 |T fT |T |T深度估计：loooFH12 14图5-9 A*搜索算法（十六数码）2.三种算法的优缺点简评：三种算法在一定条件下均可得到八数码问题的解。前两种是经典的无信息（盲目）搜索算法，后一种是经典的有信息（启发式）搜索算法。从本文的实验可以看出，广度优先搜索是一种完备策略，即只要问题有解， 它就一定可以找到解。 并且，广度优先搜索找到的解，还一定是路径最短的解。 这些都是广度优先搜索的优点。当然，广度优先搜索也存在很多缺点，主