[科普中国]-多主机搜索-

简介

特别是近年来，移动设备不断增多，移动设备如笔记本电脑、电子书籍、智能手机都要进行联网。随着用户的增多，网络服务不可能完全满足不同的各种个性化的需求，proxy也会变为通信的瓶颈，一种解决方法是以移动代码的形式实现这些个性化的工具，这些移动代码可以按用户要求移动到相应的服务器或proxy上，甚至可以移动到客户主机上，移动代码方法可以在通信双方链接断开的情况下继续工作。

多主机搜索是指用户在网络上搜索信息时不可能在一台服务器上得到全部信息，往往要搜索多台主机。为避免大的延迟，就要避免“星性循环”，即移动代码首先进入第一个网址进行搜索并将结果返回客户，然后同样的或不同的移动代码又从客户端出发进入第二个指定的网址……如此进行，直到用户找到所需的信息。1

搜索概述人工智能的基本技术之一，指计算机找出从初始状态转化到目标状态的途径，根据给定条件求解一个问题正确答案的过程。一个有趣的例子是：3个驯兽员带着3只熊和1条船在左岸(初始状态)，要把人、熊、船都渡到右岸去(目标状态)，给定条件是人或熊都会划船、但船每次最多只能装载或两人或两熊或一人一熊、而且无论左岸或右岸都不允许出现熊多于人的情况(否则熊会伤人)，为顺利到达右岸而寻找正确解决这个问题的可靠方法的过程就叫搜索。

搜索要讲究策略方法，一个最佳搜索的标准是：

(1)在问题有解的场合下能保证成功；

(2)必须花的搜索工作量最少；

(3) 找到的途径是最短的 (捷径)；

(4)沿着找到的途径进行实际操作的费用最小。实际上这4点很难同时满足，只能根据具体情况选择一种满意的搜索方法。

研究得较多的搜索方法有：状态图搜索 (包括宽度优先搜索和深度优先搜索)、与或图搜索 (又称问题分解搜索)、启发式搜索等。2

搜索策略宽度优先搜索

宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标，则算法中止。属于盲目搜索。

深度优先搜索

深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点，然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的，也不是最优的。有时候，某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的，当每次运用向上、向下、向左、向右移动空格的算符时，可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时，由于应用的算符基本一致，还会产生重复，所以为了节约时间和存储空间，往往在深度优先算法中设立一个机制，用来删除这些重复的节点，以提高效率。

迭代加深搜索（ID搜索）

对深度优先搜索进行了一定改进，对搜索树的深度进行控制，即有界深度优先搜索。

在程序找到目标之前，通过迭代不断增大d以保证完备性和最优性。虽然会有不少重复搜索，但是鉴于每增加一次d，则搜索的时间复杂度会以指数级别增加，所以重复搜索的时间可以忽略，亦可以与A*算法结合（即IDA*搜索算法）来剪枝。

迭代加深搜索通常用于那种搜索树又深又宽、但是解并不是很深的情况，这时广度优先搜索会超空间，而深度优先搜索会超时。这时迭代加深搜索很有用，可是说是在用递归方法在实现广度优先搜索。

启发式OR图搜索算法

爬山算法

模拟退火算法

最好优先

通用图

AND-OR图启发式搜索

一个特殊问题：博弈论

约束满足搜索

搜索策略还可以指在使用搜索引擎中所使用的策略，它通常是搜索之母，一个好的搜索过程必定有一个好的搜索策略来支持。

搜索引擎多主机搜索应用最多的领域是搜索引擎。

搜索引擎（Search Engine）是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。

一个搜索引擎由搜索器、索引器、检索器和用户接口四个部分组成。搜索器的功能是在互联网中漫游，发现和搜集信息。索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。3

搜索引擎的工作原理大致可以分为：

搜集信息：搜索引擎的信息搜集基本都是自动的。搜索引擎利用称为网络蜘蛛的自动搜索机器人程序来连上每一个网页上的超链接。机器人程序根据网页链到其中的超链接，就像日常生活中所说的“一传十，十传百……”一样，从少数几个网页开始，连到数据库上所有到其他网页的链接。理论上，若网页上有适当的超链接，机器人便可以遍历绝大部分网页。

整理信息：搜索引擎整理信息的过程称为“创建索引”。搜索引擎不仅要保存搜集起来的信息，还要将它们按照一定的规则进行编排。这样，搜索引擎根本不用重新翻查它所有保存的信息而迅速找到所要的资料。想象一下，如果信息是不按任何规则地随意堆放在搜索引擎的数据库中，那么它每次找资料都得把整个资料库完全翻查一遍，如此一来再快的计算机系统也没有用。

接受查询：用户向搜索引擎发出查询，搜索引擎接受查询并向用户返回资料。搜索引擎每时每刻都要接到来自大量用户的几乎是同时发出的查询，它按照每个用户的要求检查自己的索引，在极短时间内找到用户需要的资料，并返回给用户。目前，搜索引擎返回主要是以网页链接的形式提供的，这样通过这些链接，用户便能到达含有自己所需资料的网页。通常搜索引擎会在这些链接下提供一小段来自这些网页的摘要信息以帮助用户判断此网页是否含有自己需要的内容。

整理信息及接受查询的过程，大量应用了文本信息检索技术，并根据网络超文本的特点，引入了更多的信息。