浅谈人工智能领域中的搜索问题

《浅谈人工智能领域中的搜索问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈人工智能领域中的搜索问题摘要：人工智能是目前最前沿也是最尖端的计算机科学分支之一，它主要研究计算机与人类大脑的本质联系与差别，并通过对人类思维方式的研究使得计算机的工作效率实现革命性的提升。本文简要介绍了人工智能里面最核心的部分之一--搜索。读者需要对数据结构有所了解。　　关键词：人工智能；启发式搜索；A*算法；agent；ArtificialIntelligence　　：TP18：A：1007-9599（2013）04-0000-02　　1引言　　人工智能是目前信息技术领域最前沿也是和其它学科如生物学紧密相关的一个分支。人工智能的一个核心的目标即是探索计算机从根本上到底有没有可能具备人类

2、的思维方式。计算机的计算能力是人类望尘莫及的，但是即便是硬件性能高速发展的现在，人类依然有着远远超出计算机能力的方面，比如创造性思维以及图形识别能力。计算机没有办法独立于人类发现新的算法或者证明一个定理，它们只能用数据去验证却无法用数学逻辑去证明。1997年5月，IBM公司研制的深蓝计算机战胜了国际象棋大师卡斯帕洛夫，这一事件让了所有人开始意识到人工智能的威力以及未来计算机会对人类造成的影响。　　即便是处于发展不完全阶段的人工智能领域也依然能在现实生活中为人类提供便捷，比如GPS和翻译软件，这些都是非常有用的应用。今天我们所要探讨的是人工智能中的一个最核心的问题—搜索。　　2几种搜索算法的思想

3、　　大家都知道，目前计算机是无法独立思考的，它们只能依赖人类设定的算法机械的去执行。就拿国际象棋的例子来说明，一个伟大的象棋运动员可以依赖自己的直觉以及经验而计算机却不行。然而为什么计算机可以打败国际象棋好手呢？答案就是它所执行的搜索的算法。　　2.1一些基础概念。首先要介绍一个概念：智能体（Agent）。顾名思义，智能体就是搭载了人工智能“能力”的一台机器，它可以是计算机，机器人等等。搜索实际上是人类将现实中的各种需要考虑的情况抽象成一幅“地图”（比如树（Tree）和图（Graph））。智能体大体分为两类：反射智能体（Reflexagent）和规划智能体（Planningagent）。反射智

4、能体永远只对当前它所知道的情况作出判断，而规划智能体根据“全局”作出抉择。例如，小明要从武汉到上海有两种方案，方案A坐飞机到上海花费1000元，方案B先坐火车到湖南花费600元再坐飞机到上海花费800元。小明要选择开销最小的方案。反射智能体采用了贪心（Greedy）的策略，它的“思考”过程是先比较方案A的第一步以及方案B的第一步，方案B花费较少于是它选择方案B。但其实最优方案是方案A。这就是不考虑全局的后果，它很难能作出正确的抉择。但是如果一个问题能保证子结构的最优即是全局最优，那么反射智能体当然是不二的选择！（因为它会省去考虑全局的时间）　　然而现实生活中很少有局部最优即是全局最优的情况，所

5、以基本上我们都要和规划智能体打交道。规划智能体的搜索方式分为两种：非智能搜索和只能搜索。非智能搜索包括深度优先搜索（DFS），广度优先搜索（BFS）以及全局成本搜索（UCS）。　　2.2非智能搜索（UninformedSearch）。深度优先搜索总是沿着搜索树一条路径走到底，如果直到树的地步都没有找到目标节点才返回选择其它的支路。DFS首先选取搜索树最左边的节点，然后扩展该节点所有的子节点，然后对子节点进行同样的操作。如果该节点没有子节点，即返回到它的根节点对其它子节点进行扩展。以国际象棋为例，这个情境中的搜索树即是自己棋盘上所有棋子可以移动到的地方。在这一情境中，DFS选取一个棋子（例如士兵

6、），将它下一步，下下一步等等所能走到的位置找到直到该棋子没有地方可走为止。　　广度优先搜索则是一层一层地搜索，对每一层搜到的节点进行判断，如果没有找到目标节点即搜索下一层。BFS首先选取整棵树的根节点，然后扩展它所有的叶节点，判断有没有期待的解。如果没有，则扩展下一层的所有节点，然后再进行同样的操作。在国际象棋的问题中，BFS每次扩展所有棋子下一步可以走的地方。每一步即为搜索树中的每一层。　　由此可见对于一棵搜索树来说，DFS搜到的永远是搜索树中最左边的解，BFS搜到的永远是搜索树中深度最小的解。　　全局成本搜索则是考虑全局，它有着类似反射智能体的机制：优先搜索“看起来”最优的节点（注意只是“

7、看摘要：人工智能是目前最前沿也是最尖端的计算机科学分支之一，它主要研究计算机与人类大脑的本质联系与差别，并通过对人类思维方式的研究使得计算机的工作效率实现革命性的提升。本文简要介绍了人工智能里面最核心的部分之一--搜索。读者需要对数据结构有所了解。　　关键词：人工智能；启发式搜索；A*算法；agent；ArtificialIntelligence　　：TP18：A：1007-9599（2013）0