本站原创
摘 要：人工智能是目前最前沿也是最尖端的计算机科学分支之一，它主要研究计算机与人类大脑的本质联系与差别，并通过对人类思维方式的研究使得计算机的工作效率实现革命性的提升。本文简要介绍了人工智能里面最核心的部分之一--搜索。读者需要对数据结构有所了解。
关键词：人工智能；启发式搜索；A*算法；agent；Artificial Intelligence
1007-9599 （2013） 04-0000-02
1 引言
人工智能是目前信息技术领域最前沿也是和其它学科如生物学紧密相关的一个分支。人工智能的一个核心的目标即是探索计算机从根本上到底有没有可能具备人类的思维方式。计算机的计算能力是人类望尘莫及的，但是即便是硬件性能高速发展的现在，人类依然有着远远超出计算机能力的方面，比如创造性思维以及图形识别能力。计算机没有办法独立于人类发现新的算法或者证明一个定理，它们只能用数据去验证却无法用数学逻辑去证明。1997年5月，IBM公司研制的深蓝计算机战胜了国际象棋大师卡斯帕洛夫，这一事件让了所有人开始意识到人工智能的威力以及未来计算机会对人类造成的影响。
即便是处于发展不完全阶段的人工智能领域也依然能在现实生活中为人类提供便捷，比如GPS和翻译软件，这些都是非常有用的应用。今天我们所要探讨的是人工智能中的一个最核心的问题—搜索。
2.1 一些基础概念。首先要介绍一个概念：智能体（Agent）。顾名思义，智能体就是搭载了人工智能“能力”的一台机器，它可以是计算机，机器人等等。搜索实际上是人类将现实中的各种需要考虑的情况抽象成一幅“地图”（比如树（Tree）和图（Graph））。智能体大体分为两类：反射智能体（Reflex agent）和规划智能体（Planning agent）。反射智能体永远只对当前它所知道的情况作出判断，而规划智能体根据“全局”作出抉择。例如，小明要从武汉到上海有两种方案，方案A坐飞机到上海花费1000元，方案B先坐火车到湖南花费600元再坐飞机到上海花费800元。小明要选择开销最小的方案。反射智能体采用了贪心（Greedy）的策略，它的“思考”过程是先比较方案A的第一步以及方案B的第一步，方案B花费较少于是它选择方案B。但其实最优方案是方案A。这就是不考虑全局的后果，它很难能作出正确的抉择。但是如果一个问题能保证子结构的最优即是全局最优，那么反射智能体当然是不二的选择！（因为它会省去考虑全局的时间）
然而现实生活中很少有局部最优即是全局最优的情况，所以基本上我们都要和规划智能体打交道。规划智能体的搜索方式分为两种：非智能搜索和只能搜索。非智能搜索包括深度优先搜索（DFS），广度优先搜索（BFS）以及全局成本搜索（UCS）。
2.2 非智能搜索（Uninformed Search）。深度优先搜索总是沿着搜索树一条路径走到底，如果直到树的地步都没有找到目标节点才返回选择其它的支路。DFS首先选取搜索树最左边的节点，然后扩展该节点所有的子节点，然后对子节点进行同样的操作。如果该节点没有子节点，即返回到它的根节点对其它子节点进行扩展。以国际象棋为例，这个情境中的搜索树即是自己棋盘上所有棋子可以移动到的地方。在这一情境中，DFS选取一个棋子（例如士兵），将它下一步，下下一步等等所能走到的位置找到直到该棋子没有地方可走为止。
广度优先搜索则是一层一层地搜索，对每一层搜到的节点进行判断，如果没有找到目标节点即搜索下一层。BFS首先选取整棵树的根节点，然后扩展它所有的叶节点，判断有没有期待的解。如果没有，则扩展下一层的所有节点，然后再进行同样的操作。在国际象棋的问题中，BFS每次扩展所有棋子下一步可以走的地方。每一步即为搜索树中的每一层。
由此可见对于一棵搜索树来说，DFS搜到的永远是搜索树中最左边的解，BFS搜到的永远是搜索树中深度最小的解。
全局成本搜索则是考虑全局，它有着类似反射智能体的机制：优先搜索“看起来”最优的节点（注意只是“看起来”）。但是搜到之后它并不会停止，而是搜索其它节点看看有没有更优的。若是一条路径不需搜完便可判断不是最优路径，这条路径即被忽略。在最坏情况下，UCS仍然需要对每一个节点进行判断，所以当问题规模庞大的时候UCS算法所耗费的时间让这种算法极不使用。全局成本搜索永远可以找到最优解，但是在现实生活中问题的规模太过于庞大以至于采用全局成本搜索所花费的时间难以忍受。于是人们从自身的思考方式中找到线索，提出了智能搜索。
2.3 智能搜索（Informed Search）。智能搜索又叫A*算法。智能搜索的思想是在全局成本搜索的基础之上调用一个启发函数（Heuristics）来对智能体当前的状态进行评估（比如离最优解的距离或者方向的偏差）。因此启发函数为我们省去搜索与所期望的解差之千里的节点的浪费的时间。在人类的思维方式中其实也有类似的机制，比如一个经验老道的人用经验去行事，他的经验其实就相当于是一个启发函数，能够告诉他行事的方向。智能搜索中的函数一般只能告诉智能体搜索的大致方向，因为在现实生活中要构造一个完美的启发函数几乎不可能。智能搜索的效率和最优性取决于启发函数的好与坏。一个好的启发函数被称之为可接受的（Admissible）。想象一下有一个“颠倒是非”的启发函数，当智能体接近最优解的时候它反而告诉智能体离最优解很远，于是智能体被误导以至于在错误的方向上越走越远。更严重的是，只能搜索永远信赖启发函数，以至于一个荒谬的启发函数不光浪费了时间，更有可能让智能体永远搜索不到正确的解！当启发函数是可接受的时候，A*算法永远能找出最优解，而且因为有了启发函数这个“指路人”的存在使得时间复杂度降低了很多。事实上，全局成本搜索就是启发函数返回值永远为0的A*算法。
A*算法在实现的时候需要同时考虑问题本身提供的信息以及启发函数提供的信息。比如在城市旅游的问题中，要选择花钱少而且走的总路程短的路线。从一个节点到另外一个节点所花费的钱（c（x））和它们之间的距离是问题本身提供的问题，一个节点到目的地（注意是目的地！）之间的距离（d（x））则是启发函数告诉智能体的。一种A*算法的实现是直接将“有价值”扩展的节点的筛选标准定为f（x）=c
一个A*搜索算法的启发函数并不一定只能有一个，在评估每一个节点时应该得到所有启发函数之间共同给出的一个值h（x）=max（h1（x），…hn（x））或者h（x）=min（h1（x），…hn（x））.取最大值还是最小值取决于实际问题本身。
在许许多多的实际应用问题中，人们并不需要最优的解，往往一个较优的解也可以解决问题。找到一个最优解的时间通常是难以接受的，而采用启发式搜索找到一个较优解的时间却要低很多，于是在很多领域人们都开始采用智能搜索的思想。
3 总结
人工智能领域中的A*算法极大地提高了搜索算法的效率以及对现实问题的针对性。事实上，很多时候解决一个问题的难点并不是搜索算法的实现，而是在于对一个庞大的现实问题的抽象以及构建“明智”的启发函数。在解决很多复杂问题的时候，一些适当简化的启发函数能让计算机在极短的时间内找到较优的解。因此，相比于非智能搜索，A*搜索算法让计算机变得更加“智能”了。
参考文献：
Stuart Russell， Peter Norvig -- Artificial Intelligence： A Modern Approach （3rd Edition）-- Prentice Hall
[作者简介]钟瑜（1996-），男，江西人，武汉市第二中学，研究方向：人工智能及算法。
关键词：人工智能；启发式搜索；A*算法；agent；Artificial Intelligence
1007-9599 （2013） 04-0000-02
1 引言
人工智能是目前信息技术领域最前沿也是和其它学科如生物学紧密相关的一个分支。人工智能的一个核心的目标即是探索计算机从根本上到底有没有可能具备人类的思维方式。计算机的计算能力是人类望尘莫及的，但是即便是硬件性能高速发展的现在，人类依然有着远远超出计算机能力的方面，比如创造性思维以及图形识别能力。计算机没有办法独立于人类发现新的算法或者证明一个定理，它们只能用数据去验证却无法用数学逻辑去证明。1997年5月，IBM公司研制的深蓝计算机战胜了国际象棋大师卡斯帕洛夫，这一事件让了所有人开始意识到人工智能的威力以及未来计算机会对人类造成的影响。
即便是处于发展不完全阶段的人工智能领域也依然能在现实生活中为人类提供便捷，比如GPS和翻译软件，这些都是非常有用的应用。今天我们所要探讨的是人工智能中的一个最核心的问题—搜索。
2 几种搜索算法的思想
大家都知道，目前计算机是无法独立思考的，它们只能依赖人类设定的算法机械的去执行。就拿国际象棋的例子来说明，一个伟大的象棋运动员可以依赖自己的直觉以及经验而计算机却不行。然而为什么计算机可以打败国际象棋好手呢？答案就是它所执行的搜索的算法。2.1 一些基础概念。首先要介绍一个概念：智能体（Agent）。顾名思义，智能体就是搭载了人工智能“能力”的一台机器，它可以是计算机，机器人等等。搜索实际上是人类将现实中的各种需要考虑的情况抽象成一幅“地图”（比如树（Tree）和图（Graph））。智能体大体分为两类：反射智能体（Reflex agent）和规划智能体（Planning agent）。反射智能体永远只对当前它所知道的情况作出判断，而规划智能体根据“全局”作出抉择。例如，小明要从武汉到上海有两种方案，方案A坐飞机到上海花费1000元，方案B先坐火车到湖南花费600元再坐飞机到上海花费800元。小明要选择开销最小的方案。反射智能体采用了贪心（Greedy）的策略，它的“思考”过程是先比较方案A的第一步以及方案B的第一步，方案B花费较少于是它选择方案B。但其实最优方案是方案A。这就是不考虑全局的后果，它很难能作出正确的抉择。但是如果一个问题能保证子结构的最优即是全局最优，那么反射智能体当然是不二的选择！（因为它会省去考虑全局的时间）
然而现实生活中很少有局部最优即是全局最优的情况，所以基本上我们都要和规划智能体打交道。规划智能体的搜索方式分为两种：非智能搜索和只能搜索。非智能搜索包括深度优先搜索（DFS），广度优先搜索（BFS）以及全局成本搜索（UCS）。
2.2 非智能搜索（Uninformed Search）。深度优先搜索总是沿着搜索树一条路径走到底，如果直到树的地步都没有找到目标节点才返回选择其它的支路。DFS首先选取搜索树最左边的节点，然后扩展该节点所有的子节点，然后对子节点进行同样的操作。如果该节点没有子节点，即返回到它的根节点对其它子节点进行扩展。以国际象棋为例，这个情境中的搜索树即是自己棋盘上所有棋子可以移动到的地方。在这一情境中，DFS选取一个棋子（例如士兵），将它下一步，下下一步等等所能走到的位置找到直到该棋子没有地方可走为止。
广度优先搜索则是一层一层地搜索，对每一层搜到的节点进行判断，如果没有找到目标节点即搜索下一层。BFS首先选取整棵树的根节点，然后扩展它所有的叶节点，判断有没有期待的解。如果没有，则扩展下一层的所有节点，然后再进行同样的操作。在国际象棋的问题中，BFS每次扩展所有棋子下一步可以走的地方。每一步即为搜索树中的每一层。
由此可见对于一棵搜索树来说，DFS搜到的永远是搜索树中最左边的解，BFS搜到的永远是搜索树中深度最小的解。
全局成本搜索则是考虑全局，它有着类似反射智能体的机制：优先搜索“看起来”最优的节点（注意只是“看起来”）。但是搜到之后它并不会停止，而是搜索其它节点看看有没有更优的。若是一条路径不需搜完便可判断不是最优路径，这条路径即被忽略。在最坏情况下，UCS仍然需要对每一个节点进行判断，所以当问题规模庞大的时候UCS算法所耗费的时间让这种算法极不使用。全局成本搜索永远可以找到最优解，但是在现实生活中问题的规模太过于庞大以至于采用全局成本搜索所花费的时间难以忍受。于是人们从自身的思考方式中找到线索，提出了智能搜索。
2.3 智能搜索（Informed Search）。智能搜索又叫A*算法。智能搜索的思想是在全局成本搜索的基础之上调用一个启发函数（Heuristics）来对智能体当前的状态进行评估（比如离最优解的距离或者方向的偏差）。因此启发函数为我们省去搜索与所期望的解差之千里的节点的浪费的时间。在人类的思维方式中其实也有类似的机制，比如一个经验老道的人用经验去行事，他的经验其实就相当于是一个启发函数，能够告诉他行事的方向。智能搜索中的函数一般只能告诉智能体搜索的大致方向，因为在现实生活中要构造一个完美的启发函数几乎不可能。智能搜索的效率和最优性取决于启发函数的好与坏。一个好的启发函数被称之为可接受的（Admissible）。想象一下有一个“颠倒是非”的启发函数，当智能体接近最优解的时候它反而告诉智能体离最优解很远，于是智能体被误导以至于在错误的方向上越走越远。更严重的是，只能搜索永远信赖启发函数，以至于一个荒谬的启发函数不光浪费了时间，更有可能让智能体永远搜索不到正确的解！当启发函数是可接受的时候，A*算法永远能找出最优解，而且因为有了启发函数这个“指路人”的存在使得时间复杂度降低了很多。事实上，全局成本搜索就是启发函数返回值永远为0的A*算法。
A*算法在实现的时候需要同时考虑问题本身提供的信息以及启发函数提供的信息。比如在城市旅游的问题中，要选择花钱少而且走的总路程短的路线。从一个节点到另外一个节点所花费的钱（c（x））和它们之间的距离是问题本身提供的问题，一个节点到目的地（注意是目的地！）之间的距离（d（x））则是启发函数告诉智能体的。一种A*算法的实现是直接将“有价值”扩展的节点的筛选标准定为f（x）=c
职称论文范文www.udooo.com
（x）+d（x）的值。但是在这里要注意一点，d（x）必须小于或者等于c（x）的值，否则这个启发函数将会是不可接受的。一个A*搜索算法的启发函数并不一定只能有一个，在评估每一个节点时应该得到所有启发函数之间共同给出的一个值h（x）=max（h1（x），…hn（x））或者h（x）=min（h1（x），…hn（x））.取最大值还是最小值取决于实际问题本身。
在许许多多的实际应用问题中，人们并不需要最优的解，往往一个较优的解也可以解决问题。找到一个最优解的时间通常是难以接受的，而采用启发式搜索找到一个较优解的时间却要低很多，于是在很多领域人们都开始采用智能搜索的思想。
2.4 搜索算法最优性的总结。反射智能体采用的贪心搜索：不一定最优
DFS：不一定最优（只找出最左边的解）；BFS：只有在所有节点间成本为相同值时最优；UCS：永远最优；A*：当启发函数可接受时最优3 总结
人工智能领域中的A*算法极大地提高了搜索算法的效率以及对现实问题的针对性。事实上，很多时候解决一个问题的难点并不是搜索算法的实现，而是在于对一个庞大的现实问题的抽象以及构建“明智”的启发函数。在解决很多复杂问题的时候，一些适当简化的启发函数能让计算机在极短的时间内找到较优的解。因此，相比于非智能搜索，A*搜索算法让计算机变得更加“智能”了。
参考文献：
Stuart Russell， Peter Norvig -- Artificial Intelligence： A Modern Approach （3rd Edition）-- Prentice Hall
[作者简介]钟瑜（1996-），男，江西人，武汉市第二中学，研究方向：人工智能及算法。