Question

什么是人工智能的搜索方式？

Answer 1

什么是搜索？搜索是人工智能领域的一个重要问题。它类似于传统计算机程序中的查找，但远比查找复杂得多。传统程序一般解决的问题都是结构化的，结构良好的问题算法简单而容易实现。但人工智能所要解决的问题大部分是非结构化或结构不良的问题，对这样的问题很难找到成熟的求解算法，而只能是一步步地摸索前进。就像是甲、乙两个不同的网络，甲网络中的某一台计算机A要想找到乙网络中的数据。乙网络位于广域网中，A的目标就是要找到乙网络（实际上就是找到甲主路由器的IP），但是A不知道目标的具体位置，只能试探着去找。像这样摸索着前进，不断搜索前进方向的过程称为搜索。从理论上讲，只要乙不犯规 (不会关闭设备)，A终究是会找到乙的（当然这必须是在甲、乙本来是可以互通的基础上）。当然，A找到乙所需的时间是无法预测的。如果A以前就访问过乙网络上的某台主机，在找的过程中，可以得到路由器中更新的路由表的支持，很快会找对了方向，可能花费的时间就会少些。相反，也有可能A找遍了所有的地方，最后才找到乙(极端情况)。 搜索，通常可分为盲目搜索和启发式搜索。盲目搜索是按预定的控制策略进行，在搜索过程中获得的中间信息不用来改进控制策略 。这在复杂网络中的路由选择会经常用到。广域网中的动态路由协议，为了学习相邻路由器的路由，为了确定最短路径，总是主动地去搜索相邻的路由设备。由于路由选择总是按预先规定的方式进行，未能考虑到环形结构或不可到达情况，因此效率不高，具有盲目性，往往会因此占去不少的网络带宽。启发式搜索是在搜索过程中根据问题的特点，加入一些具有启发性的信息，如从上一级路由器中找到相应的路由表来确定下一步搜索的路线，加速问题的求解过程。显然，启发式搜索的效率比盲目搜索要高，但由于启发式搜索需要与网络本身特性有关的信息，而这对非常复杂的网络是比较困难的，因此盲目搜索在目前的应用中仍然占据着统治地位。而盲目搜索中最行之有效、应用最广泛的搜索策略就是：宽度优先搜索和深度优先搜索。这两种搜索方法在很多人工智能的资料中都有介绍，关于算法也给出了简单的设计思路。这里只对简单应用及体会做简单介绍。 宽度优先搜索，又称为广度优先搜索，是一种逐层次搜索的方法。在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。设V1为起始节点，则搜索的顺序为：V1V2V3V4V5V6V7 Flash5中Action Script功能非常强大，其实它涉及到的最主要的问题就是动作怎么通过指定路径或一个大概的方式去完成动作的结果。利用此算法可以很好地解决这个问题。打红警，玩帝国时，指挥坦克或炮车去指定位置，计算机控制坦克通过此算法找到最短路径行进只需要将屏幕分成多个区间并编成号码，实际上从源地址到目标地址就是找到到达目标地址的一串区间号码。这样问题就可以程序化了。至于具体的设计流程和源程序这里就不多讲了。 Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 实际上网络上许多协议和应用程序都会用到类似的思想。例如，生成树协议中，为了确定生成树的树根。它要确定每一台交换机的树值并不断地更新结果。象使用网络下载某个软件时，它的每个线程都会去找目标地址，来确定到达的路径。 因为宽度优先搜索是针对非结构化或结构不良的问题，所以只要碰到类似的情况只是将具体条件转化一下，就可以应用此算法了。