搜索算法

搜索算法（精选11篇）

搜索算法 篇1

摘要：介绍了一种采用广度优先搜索算法实现游戏中路径搜索的方法, 并用VC编程实现。

关键词：广度优先搜索,VC语言

路径搜索是许多游戏特别是即时战略游戏的核心组成部分, 玩过即时战略游戏 (如红色警报) 的朋友们对此一定都不陌生。在这类游戏中, 玩家不需要控制游戏主角的每一步移动, 只需用鼠标点击一下目的地, 游戏主角就可以自己移动到那里。那么游戏是如何实现路径搜索的呢?实现路径搜索的算法又是什么呢?下文就以一个简单的路径搜索为例, 说明上述问题, 并给出VC++的程序实现。

1 路径搜索的实现方法

路径搜索是一个寻径问题, 所谓寻径问题, 就是在地图上的起始点A和目的点B之间寻找一条可通行的路径。显然, A和B之间可以有很多条路径, 目的就是用最短的时间找到一条最佳路径。寻找最佳路径, 其本质就是搜索, 是一个从初始节点出发, 沿着与之相连的边试探前进, 寻找目标节点的过程。

路径搜索的基本算法主要有盲目搜索和启发式搜索两种, 进行盲目搜索时, 扩展节点不估计路径代价, 是比较常用的方法, 下文采用一种盲目搜索算法——广度优先搜索算法来实现即时战略游戏中的路径搜索。

1.1 广度优先搜索算法简介

广度优先搜索算法把起点作为初始节点, 从初始节点开始, 应用算法生成第一层节点, 检查目标节点是否在这些后继节点中。若没有, 再用算法将所有第一层的节点逐一扩展, 得到第二层节点, 并逐一检查第二层节点中是否包含目标节点。如此依次扩展、检查下去, 直至发现目标节点为止。这里采用的原则是先生成的节点先扩展, 为满足这一要求, 采用“队列”这一数据结构来存储节点, 队列设置两个指针:open指针和closed指针, open指针指向扩展得到的节点, closed指向已检查过的节点。当open=closed时, 表示队列空, 当open大于队列长度时, 表示队列溢出, 如图1所示。

1.2 路径搜索的实现过程

为了具体说明广度优先搜索算法在即时战略游戏中的应用, 以一个简单的路径搜索为例, 构造一个二维地图, 如图2所示, 把地图均匀划分为若干个小方格, 在图2中共3*3个方格, 游戏主角位于一个方格中, 我们选中其他任一个方格作为目的地, 点击鼠标, 游戏主角自动选路移动到目的方格。为了更加逼近现实情况, 可以设置某些方格为障碍物, 即游戏主角必须绕过障碍才能前进。例如, 方格编号如图2所示分别为1、2、……、9, 游戏主角位于方格1中, 方格5为障碍物, 玩家要使主角移动到方格9中, 那么广度优先搜索算法把1加入队列, 此时队列包含{1}, 检查1是否目标节点, 不是目标节点则继续搜索, 从1开始搜索相邻节点, 这是第一层搜索, 得到方格2和4, 检查2和4, 不是目标节点, 则2、4进入队列, 队列包含{1, 2, 4};进行第二层搜索, 由2搜索相邻节点得到3, 也搜索到了5, 但是方格5是障碍物, 不能加入队列, 由4搜索到7, 检查3和7, 不是目标节点, 于是3、7进入队列, 队列包含{1, 2, 4, 3, 7};继续第三层搜索, 由3得到6, 由7得到8, 检查6和8, 不是目标节点, 于是6、8进入队列, 队列包含{1, 2, 4, 3, 7, 6, 8};继续第四层搜索, 由6得到9, 检查9是目标节点, 于是结束搜索。为了记住搜索的路径, 在搜索过程中, 设计数据结构记录每一个节点的前趋节点, 如2的前趋节点是1, 这样, 在找到9之后, 可以根据前趋节点回溯到节点1, 回溯过程是9、6、3、2、1。可以用“栈”这一数据结构保存回溯过程, 压栈顺序为9、6、3、2、1, 这时, 游戏主角可以按路径移动, 移动按出栈顺序进行, “栈”是后入先出的数据结构, 于是, 主角就按1-2-3-6-9的顺序完成移动。

2 程序实现

下面给出广度优先搜索的程序实现。选用VC++6.0作为程序开发平台, 建立基于对话框的工程。程序设计的关键是: (1) 编写广度优先搜索类, 用于随机生成二维地图, 并且实现路径搜索。 (2) 实现游戏主角在地图中移动。

2.1 实现广度优先搜索的类CBfs Map

下面依次介绍CBfs Map类的成员函数。

函数void Init Map () 用于初始化地图, 并随机设置障碍物。

函数void Search Path () 用于路径搜索:

2.2 实现主角在地图中移动

创建一个基于对话框的类CBfs Dlg, 在类中添加按下鼠标左键的消息响应函数On LButton Down () , 该函数根据鼠标左键点击的位置, 进行路径搜索, 代码如下:

程序运行情况如图3所示, 界面中红色栅格表示障碍, 白色部分表示通路, 当玩家点击任意空白处, 游戏主角能够自行移动到该位置。

3 结语

介绍了一种采用广度优先搜索算法实现路径搜索的方法, 并给出了原理及关键数据结构。虽然代码不多, 却实现了一个较为完整的路径搜索实例, 希望能对游戏编程爱好者们起到积极的参考作用。

参考文献

[1]吴文虎, 王建德.实用算法的分析与程序设计.电子工业出版社, 1998.

搜索算法 篇2

针对多边形切割中由于切割点坐标值的取舍导致的点位偏移,从而可能出现拓扑错误的情况,提出一种基于节点序列搜索的`多边形分割算法.该算法在生成多边形相交的切割线的基础上,对产生的切割点进行坐标值取舍,将进行坐标值取舍后的坐标点与被切割多边形的坐标点按照节点序列生成被切割多边形,同时切割点内插到相关多边形,从而保证多边形的拓扑关系不变.该算法能解决带岛多边形切割.该算法已经在大规模数据生产中得到应用.

作 者：曾广鸿 王晓明 徐宜勤 邬伦 ZENG Guang-hong WANG Xiao-ming XU Yi-qin WU Lun  作者单位：曾广鸿,ZENG Guang-hong(北京大学,地球与空间科学学院,北京,100871;广州市国土资源和房屋管理局,广东,广州,510031)

王晓明,徐宜勤,邬伦,WANG Xiao-ming,XU Yi-qin,WU Lun(北京大学,地球与空间科学学院,北京,100871)

刊 名：测绘通报  ISTIC PKU英文刊名：BULLETIN OF SURVEYING AND MAPPING 年，卷(期)： “”(8) 分类号：P208 关键词：多边形分割   节点序列   拓扑关系   算法  

基于P2P的资源搜索算法探讨 篇3

关键词:P2P 搜索 根服务器

一、引言

随着Internet的广泛普及和网络应用规模的不断扩大,客户机/服务器模式的存储技术面对快速增长的网络规模,由于自身模式的原因闲置浪费了大量的计算和存储资源。更大规模的网络对存储服务器提出了更高的要求。服务器的不堪重负和分布在网络中的闲置资源促使了一种新的网络范例——对等计算(Peer-to-Peer,简称P2P)的出现。本文就基于P2P的资源搜索算法设计进行探讨。

二、P2P概述

P2P中文称为对等网络,是指分布式系统中的各个节点是逻辑对等的,也就是说,对等网络中每个IP点的地位是对等的,既可充当服务器为其他节点服务,也可充当客户机消费其他IP点提供的服务。依据文件的检索模型和机制,现有的P2P实现方式大致可以分为三种类型。它们分别是基于目录服务器P2P,非结构化P2P和结构化P2P。

基于目录服务器的P2P摒弃了传统C/S模式由服务器负责一切的方式,用一个或多个中央目录服务器存储资源的实际存储位置,并响应各P2P对等机的查询请求;在非结构化的P2P中,网络模型无需特别的设计,节点在网络中完全对等,加入和退出网络不会引起大量的维护消息;结构化的P2P多数采用基于DHT技术构造,具有明确的搜索目的性,具有较高的搜索效率。

三、基于根服务器的P2P搜索算法设计

1.数据结构

(1)根服务器上保存所有搜索树根的列表:

structRootlst{

long KEY_Sector;

long ip;

}rootlst[LENGTH];

(2)物理节点(PN)所保存的本地逻辑节点列表:

struct LNlst{

longKEY_Sector;

long LNID;

}Inlst[LENGTH];

int LNnum;

(3)逻辑节点(LN)的路由表:

struct Lnroute{

longfather;

longchildren[4];

intchildren-count;

int Vln;

int Lin;

long Ext;};

struct LN{

long IP;

long KEY;

struct Lnroute Inroute;

}LNnew;

2.搜索树根发现机制

所有LN维护一个仅存储自己的父节点、所有子节点的位置信息的邻居表,所有根节点的子节点均设置父节点为根节点的标识符口当一个LN需要获得根节点的位置时,将发送一个根节点发现消息给自己的父节点,并逐级向上转发,直到父节点为根节点时,返回响应消息。

3.空余度路由更新算法

子LN节点的空余度Vin或者空余度距离Lin发生改变时,将二者的值发给父LN,通知父节点执行空余度路由更新。

父节点更新自己存储的该子节点的Vln和Lin,并根据新的子节点空余度路。

由状况重新设置自己的空余度路由出口。

Vin为空余度,Lin为空余度距离,Ext为空余度路由出口。LN6下接4个节点之后,LN6的空余度路由发生改变,同时通知其父节点LN2,LN2将选择Lin最小的子节点,而LN7.LN8.LN9的Lin均为0,因此LN6选择这三个子节点中Vin最大者,即LN9作为自己的空余度路由出口。而LNl及其他兄弟节点并为受此拓扑变化的影响。

伪码如下:

Route-update(child_Vln, child_Lln){

if (LN.Inroute.children_count<4){

LN.Inroute.Vln=4-LN.Inroute.children_count;

LN.Inroute.Lln=0;

LN.Inroute.Ext=localhost;}

else{

LN.Inroute.Ext=max_Lln(LN.children)

LN.Inroute.Vln=GetRemoteLN(LN.Inroute.Ext).InrouteVln;

LN.Inroute.tln=GetRemoteLN(LN.Inroute.Ext).InrouteLin+1}}

4.搜索树创建算法

当一个物理节点上存储的文件加入PZP网络时,将执行一下步骤:

(1)计算出该文件各个关键字对应的哈希键值

(2)检查本节点上是否已经存在包含该哈希键值的LN,如果没有,则创建该LNnew.

(3)检查该物理节点上是否已存在的其他LN,如果不存在,则向根服务器发送新LN消息:如果存在则利用该LN的根LN发现消息找到其所对应的根LN,即对应另一哈希数值区间的搜索树根,并由此确定LNnew本身所属的哈希数值区间的搜索树是否存在(步骤d确保每个搜索树根LN均保有所有搜索树根LN的信息),若存在,则转向LN加入算法;若不存在,则向根服务器发送新LN消息。

(4)根服务器接收到新LN消息,在LNnew所对应的哈希数值区间上新建一棵搜索树,即将该物理节点上的这个新创建的LN定义为该搜索树的根添加到本地搜索树根表中的对应行,随即将这张搜索树根表发给所有根LN进行更新。

新加入的逻辑节点LNnew仅在本地不存在其他LN的时候才向根服务器发起查询请求,而根服务器也仅需返回对应于LNnew所在哈希值区段的搜索树树根地址即可。

伪码如下:

CreatTree(KEY){

if(!existed(GetLocalLN)(KEY))

PN.CreateLN(KEY);

if(LNnum>0){

oot=getRoot(anotherLN);

if(Root=getRootLRoot,KEY)==null){

LNnew.send(Sever,msg_NEWLN,LNnew.KEY,LNnew.IP);

Server.Add(Server.getSector(KEY),LNnew.lP);

Server.Broadcast(Server.getRootListQ);}

else

LNnew.send(Root,msgNEWLN,LNnew.KEY,LNnew.IP);}

else

LNnew.send(Sever,msg_NEWLN, LNnew.KEY,LNnew.IP);}}

建立搜索树的目的即是将同在一个关键字哈希值区间内的文件逻辑上聚合在一起,当产生搜索请求时,搜索消息即可在某个搜索树内部进行,消除了盲目性,而搜索树的结构也保证了不会有消息循环和冗余。每个节点仅需负责简单的转发消息和查找自己的文件列表,负载分布合理,具有很高的效率。

5.逻辑节点加入算法

当一个新的LN:LNnew加入网络,并且由算法A中的c)步骤转向LN加入算法时:

(1)LNnew通过同一PN的其他搜索树节点获得自己所在搜索树的根LN节点。若该PN没有其他的LN时,则向根服务器查询根LN。

(2)LNnew向根节点LN发送新LN消息。

(3)从根节点开始,依照空余度路由转发LN加入消息,直到到达路由出口指向自身的节点LNi,即完成搜索。

(4)LN将LNi作为LNnew的父节点,并通知该当前节点和LNnew,二者随后更新自己的空余度路由表。

LNnew向其所属的搜索树的根节点LN1发出加入请求,根节点沿着空余度路由进行搜索,直到找到出u指向自己的逻辑节点LN9。

LNnew接入搜索树,成为LN9的子节点,则LN9更新其空余度路由,并向父节点LN2发出更新消息,以此类推,LN2和根节点LNI均更新空余度路由,LNnew加入过程完毕。

伪码如下:

Root.OnNEWLN(KEY, IP)

Node=Root;

while(node.Inroute.Ext!=node.IP){

node=GetRemoteLN(node.Inroute.Ext);}

LNi=node;

LNi.children[LNi.lnroute.children_count] =LNnew.IP;

LNnew.father=LNi.IP;}

采用空余度路由的理由是尽可能将新加入的节点往靠近根LN的地方放置,并且尽可能将各LN的子节点排满,避免在搜索树的各个LN间广播空余度查询消息时,造成对搜索树的大面积遍历,浪费网络资源。

参考文献:

1.詹春华,陈晓苏.对等网络搜索方法比较与分析.湖北工学院学报,2004.

2.陈志琦,苏德富.基于P2P技术的Gnutella网络搜索路由机制的改进.计算机工程与设计,2005.

3.周晋,路海明,卢增祥,李衍达.基于部分匹配方式的可扩展P2P搜索算法.清华大学学报:自然科学版,2004,44(10).

搜索算法 篇4

在现代社会中,火灾、爆炸、坍塌事故常有发生,救援过程中因建筑情况不清,意外坍塌事故等导致救援人员遇难的惨剧时有发生。为避免此类事故,应用机器人及时探知险情和受困人员的情况和位置有着极大的应用意义。论文中将机器人所面临的搜救环境抽象为一个迷宫,而搜救就是要在迷宫中先搜索到目标物并带着目标物返回到出发点处。

迷宫的种类[1]有很多,而用的比较普遍的是Perfect迷宫,所谓的Perfect迷宫是一种没有任何环路且没有任何不能到达的区域。本次实验中,所选择的迷宫环境都为Perfect迷宫。目前,经典的搜索路径算法有D*算法和A*算法,而在迷宫中运用最为普遍的搜索算法是泛洪算法,而泛洪算法是一种基于改进的深度优先搜索算法[2]。泛洪算法在搜索过程中多次遇到目标点,但它的目的是要从这些路径中找到最快到达目标点的一条路径,原始的泛洪算法不适合本次实验中的搜救应用,于是,我们在实验中是用深度优先搜索算法进行比较研究。Takayuki Goto,Takeshi Kosaka研究了A*以及D*算法在ITS(智能运输系统)和机器人路径规划中的应用,确定了A*算法以及D*算法的优势[3]。而对于A*算法中启发式函数的选取,已有多种选择。在启发式函数的选取上,有对A*算法估价函数所出现的问题,将距离和角度进行归一化处理[4];也有对当前节点进行评估的思想上,增加了最短路径中当前节点的父节点,并对当前节点与终节点的距离进行了评估,这使得A*算法的搜索方向更加趋向终点,从而提高了搜索速度[5];还有一般情况下对启发式函数的设定选择为两点间的欧几里得距离[6];

本次实验中,将分别对含有三种不同启发式函数的A*算法与深度优先搜索算法用于迷宫中进行比较仿真研究。

1 实验研究

1.1 实验研究方法

实验研究目的是将算法用于现实搜救中,既然是为了搜救,那么时间是关键,搜索迷宫所用时间的长短就成为评价算法优劣的主要因素。对于机器人来说,所处的迷宫环境是未知的,它只能通过传感器感测到目标点所在的大致位置,然后根据算法一步一步的搜索到目标物。从出发点处找到目标物时所耗的时间我们记录为搜索迷宫所用的时间,当然,搜救的目的不仅仅是为了找到目标物,同时是需要在找到目标物后将目标物带回至出发点处。从目标点返回到出发点时,如果沿之前的原路返回,那就会浪费很多没必要的时间,使搜救时间变长,所以我们要做的工作是要将之前的走过的路径进行优化,使机器人带着目标物返回出发点时不用走“冤枉路”,从而节省搜救时间。

真实环境中,目标物在目标点处通过敲打墙壁或地面等发出声音,模拟“呼救”,从而让机器人通过传感器感知到目标物。但由于外界因素(例如:传感器的精度,迷宫环境中障碍物对声音的阻碍作用等)的干扰会导致机器人只能判断出目标物的大致位置,这个大致位置是随着机器人离目标物越来越近而会越来越精确,直至找到目标物。

而在本次仿真实验中,为了能够比较真实的模拟真实环境,我们人为的让目标点坐标产生了一定的偏差,并且让这个偏差值随着机器人越来越靠近目标点而变得越来越小。

1.2 深度优先搜索算法

所谓“深度优先”,即:状态树的生长或展开,首先沿状态树的深度方向进行。深度优先搜索算法需要记录下状态树的生长过程,深度优先搜索算法是一种盲目的搜索算法,搜索中可能很多次的搜索到目标点,深度搜索算法通过不断剪枝,寻找出一条从起始点到目标点最近且最省时的路径,即深度优先搜索算法也是一种全局的搜索算法,这样的深度优先搜索算法运用到未知迷宫搜救中是没有意义的。而本次实验中,深度优先搜索算法是以找到目标物为目的,没有剪枝的步骤,只要搜索到目标物,迷宫的搜索过程就成功退出。

1.3 A*算法

A*算法是人工智能中的一种搜索算法,是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序(Node Ordering),使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价节点处于最短路线上的可能性的度量。A*算法中引入了评估函数,评估函数如下:

其中:n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。仿真实验中,我们为A*实现了三种启发式函数,如引言中所述,一种启发式函数为当前点到目标点的欧几里得距离评估,我们定义为A*(1);

即A*(1)算法的评估函数为:

其中启发式函数h1(i)为当前节点i到偏移目标点的欧几里得距离。

另一种启发式函数在第一种的启发式函数中增加了当前节点的父节点到目标点的欧几里得距离评估,我们定义为A*(2);

A*(2)算法的评估函数为:

j为当前节点的父节点,h2(i)为已评估出的当前节点i的父节点到偏移目标点的距离。

最后一种启发式函数是在第一种启发式函数的评估上加入了当前点到目标点的角度评估,我们定义为A*(3)。

A*(3)算法的评估函数为:

其中,为权重值,取ω1=0.55,ω2=0.45;θ为当前点到偏移目标点的直线与水平线的夹角,α为起始点到实际目标点的直线与水平线的夹角,角度如图2中标示;l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离。

2 仿真实验分析

实验的迷宫环境设置如下图所示,将环境划分为一个一个的栅格,红色栅格为障碍物,白色栅格为通道,生成的10个迷宫均为Pefect迷宫,保证了整个迷宫中至少有一条从起点到目标点的通道并不会产生环路。起点坐标设为(0,0),目标点坐标设为(24,24)。

由于机器人在检测呼救信号时存在不准确因素(例如:传感器的精度,迷宫环境障碍物对声音的阻碍作用等),都会导致机器人在搜索时存在或多或少的误差,所以仿真实验中,为了比较真实的模拟现实搜救环境,我们对目标点做了偏差处理,处理方式如图2中所示。

其中,(xs,ys)为起始点坐标,(x,y)为机器人当前所在位置坐标,(xt',yt')为偏移目标点的坐标,(xt,yt)为实际目标点坐标:

为目标点产生的偏移误差:

其中,k为权重值,通过实验,取得k=40,l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离,rand(-1,1)为随机数,随机数的取值范围为(-1,1)。

实验中,我们将三种A*算法分别在10个不同的Perfect迷宫中运行,统计结果如表1所示。

通过上表的结果分析可知,正如文献3中所述,加入了父节点评估的A*算法(即A*(2))在搜索时,提高了搜索速度;而在文献2中所述的提高搜索速度的优势在本次实验中没有很好的体现出来,这是因为,在本次实验中,我们加入了偏差值,对于A*(3)中的估价函数,不仅在距离上加入了偏差,同时在角度上也加入了偏差,从而使得A*(3)算法在本次搜索中没有优势。从表中我们还可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。

仿真实验中,对于返回路径的优化,我们通过算法设定,让机器人每走过一个栅格都将该栅格的状态标记为“已访问”,被标记为“已访问”的栅格,机器人在搜索时就不会再走,除非遇到是死路的栅格。那么在算法中我们定义两个状态,一个状态是通过栅格的次数(count),另一个状态是栅格是否为分支。当机器人搜索到目标点后,返回时只需要走count为1或者栅格为分支(is Branch=true)的路线就是返回的最优路线,且不会走“冤枉路”。

3 结论

本文通过仿真实验比较了A*算法与深度优先搜索算法在未知迷宫中的搜索应用,仿真实验中还同时比较了三种带有不同启发式函数的A*算法的应用,通过仿真实验比较得出的结果是:总体来说,未知迷宫中,在仅知道目标点的大概位置的情况下,进行搜索时,A*算法要优于深度优先搜索算法,而A*算法在启发式函数不同的情况下,搜索产生的结果也是不同的,从上述仿真实验结果的比较中可以得出,A*(2)算法搜索路径的时间是最优的,其次是A*(1)和A*(3)算法。同时,从实物实验比较结果也可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。深度优先搜索算法在未知迷宫中进行搜索时是盲目的,而A*算法在搜索过程中通过引入启发式信息来实现向目标节点移动的判别,无需遍历地图,使得计算复杂度相对较小,实现了快速、高效。但是,这也导致搜索的过程中排除了大量节点,而由于经验及实际问题的复杂性,引入启发信息的代价函数无法做到完全正确,这些被排除的节点可能就是最优路径的节点之一。

摘要：本文通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在标准迷宫中的应用,在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。机器人搜索的目的是为了进行搜救,因此机器人应该要在尽量短的时间内搜索到目标物并将目标物带回。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法。

关键词：迷宫搜索,深度优先搜索算法,A*算法

参考文献

[1]http://www.astrolog.org/labyrnth.htm.

[2]A.Francy Golda,S.Aridha,and D.Elakkiya,"AlgorithmicAgent for Effective Mobile Robot Navigation in anUnknown Environment."Intelligent Agent&Multi-AgentSystems,2009,IAMA 2009.

[3]Takayuki Goto,Takeshi Kosaka,and Hiroshi Noborio,"Onthe Heuristics of A*or A Algorithm in ITS and Robot Path-Planning,"Proceedings of the 2003 IEEE/RSJ InternationalConference on Intelligent Robots and Systems,pp.1159-1166,Oct,2003.

[4]史辉,曹闻,朱述龙,"A*算法的改进及其在路径规划中的应用"[J].测绘与空间地理信息,2009,32,6:208-211.

[5]张仁平,周庆忠,熊伟,"A*算法改进算法及其应用"[J].计算机系统应用,2009,98-100.

搜索算法 篇5

一直不知道该写什么内容，那天在工作中遇到了一个google收录后又突然消失的问题，后来部门的一位seo专员解决了这个问题，我想和大家分享一下。同时在根据自己的一些经验说说我对这三家搜索引擎算法的了解。

一个搜索引擎的算法，有很多的方面。主要是“域名、密度、内链、外链、相关度、服务器稳定、内容更新、域名时间、内容数量”这些方面。

这些都是搜索引起算法最核心的部分。说白了也就是你做关键词，给网站做优化需要注意的问题。只有做竞争很大网站优化的时候，才会考虑这么多要素。经常看到一些“seo高手”说，我没有优化，这个词就做到了第一位，或我网站名称一直在第一名等。那些都是没有什么竞争的词，这个时候，你只需要考虑密度即可。遇到那些竞争激烈的词，你就要注意更多的因素了，也就是那些牛人常说的，要主意细节问题。说这话的，基本都是技术有两下的。

然而这么要素，在三大搜索引擎中的权重又各不相同。例如百度非常看重密度，google很看重外链和外链的稳定，雅虎看重玉米的时间。他们都有自己的算法侧重点，想要在三大搜索引擎中获得好的排名，就都要考虑。

关于robots文件，百度完全不搭理这个东西。而google却非常看重。还有404和500错误。这些东西百度是从来不管的，而google是相当重视的，重视到你可怕的程度，

给公司做的网站，前段时间突然google的收录为零了。不是一个站，是大部分站点。当时找不到原因，我以为是几个网站内容重复性太高，而且共用一个模板照成的。当我的一个同事给这些网站做google地图的时候发现，无法验证那个文件。让服务器管理员找原因也没有找到，后来还是这位同事细心，发现了网站出现500错误。本应该是404的错误，却出现了500，就因为这一个原因，google就拒绝了收录，而且清空了数据。解决这个问题后，第二天google就重新收录了。

当时我就一个感慨，google真够变态的。做优化，必须要注重细节问题，不要以为自己很牛B了，其实还有很多问题你没有发现。什么是高手?高手就是可以解决难题的人。

其实google只是细节方面注意太多，最变态的莫过于雅虎了。难道是因为雅虎做搜索最早的缘故?雅虎对于作弊站点，毫不留情，与百度不相上下。

对于K掉IP，基本上搜索引擎很少去做。尤其是百度很少这样做，他会K掉大部分，而保留小部分站点，IP是很少封的。因为百度知道，国内还是虚拟主机的天下。然而老外IP多，服务器也多，国外的空间都是送IP的，所以雅虎看到你作弊，就会毫不留情的K掉你的IP。IP下的站点，就是不收录你，那怕你和那个作弊的站点没有任何关系。

从这些细节方面，我们就可以看出他们为什么会那样做了。国情不同啊，想要本地化，不和百度学真的不行。虽然百度经常很无耻的K掉你，而不给你赎罪的机会。

郁闷的是，我这个站的服务器IP就让雅虎给咔嚓了，百度也给降权了。还是google好，seo这个词的排名一直很稳定。

搜索算法 篇6

关键词 BOC 捕获 频谱 仿真搜索 正交

1 引言

由于GPS卫星发射的导航信号比较微弱，而且以固定的频率发射，因此很容易受到敌方的干扰。为了改善这种局面，1977年美国正式提出了“GPS导航战”（Navigation warfare）的概念[1-3]。但由于现行的军用和民用GPS信号的频谱是混叠使用的，所以美方对C/A码施放干扰信号也必然导致军用信号频谱的中央部分不能使用。为了改善GPS这种频谱结构的缺陷，美方经过大量的研究后，确定了最终方案：在现有L1和L2两个频段上附加新的军用信号，即M码。M码采用一种裂谱调制法，它把其大部分功率放在靠近分配给它的频带的边缘外，抗干扰能力主要来自不干涉C/A码或Y码接收机的强大的发射功率，而且M码信号的保密设计基于下一代密码技术和新的密钥结构，具有很高的保密性。实现M码分裂频谱调制方法有很多种，经过大量比较，确定了选用二进制偏移载波（BOC）调制技术，这是因为它不仅使M码信号的频谱能与现有信号的频谱很好的隔离，而且还有更好的性能。本文在介绍BOC调制技术的原理和分析其频谱结构的基础上，提出了基于并行码相位搜索的改进捕获算法，设计了正交IQ捕获算法，对两路并行捕获，捕获性能优于传统的捕获方法，仿真结果显示算法的正确性。

2 BOC调制信号的频谱与自相关特性

二进制偏置载波（BOC）调制，该调制提供两个相互独立的设计参数：

（1）副载波频率fs，单位MHz；

（2）扩频码速率fc，单位Mchip/s。

通过这两个参数，可以自由地将信号能量集中在所分配带宽的指定部分，以减少接收其他信号的干扰。

BOC调制信号通常被记作为BOC（fs，fc）或BOC（a，b），其中fs=af0，fc=bf0（a，b通常为正整数），基准频率f0=1.023MHz。

2.1 BOC调制信号的频谱特性

BOC（fs，fc）信号的归一化基带功率谱4-7：当n=2fs/fc为偶数时[4-7]，

（1）

当n=2fs/fc为奇数时，

（2）

采用BPSK调制方式，扩频码码率为fc的GPS C/A码信号的归一化基带功率谱为：

（3）

图1所示为 BOC（1，1）信号和GPS C/A码信号的归一化基带功率谱，可以看出BOC（1，1）相对于 GPS C/A码信号，最大的一个特点就是具有中心分裂的功率谱，这将有助于降低它与GPS C/A码信号的干扰，并且由于它在高频段具有更多的能量，它比GPS C/A码信号拥有更大的Gabor带宽， 这也意味着它具有更佳的捕获性能。

2.2 BOC调制信号的自相关特性

BOC调制信号的自相关函数，可以通过对BOC调制信号的功率谱做逆傅立叶变换得到。理想情况下（接收机前端带宽无限宽）BOC（pn，n）信号的自相关函数为[8]：

（4）

其中，p=1，2，3，…，k=■。

在（4）中令p=1，可得BOC（1，1）自相关函数RBOC （1，1）（τ）为：

（5）

采用BPSK调制方式的GPS C/A码信号的自相关函数RCA（τ）为：

其中k=2τ/Tc，Tc=1/fc。图2所示为BOC（1，1）信号和GPS C/A码信号的自相关函数，可以看到BOC（1，1）的自相关函数相对于GPS C/A码信号而言，具有多个峰值，这也对接收机提出了更高的要求。通常将自相关函数正中间的峰值称为主峰，而其它的峰称为旁峰。

3 捕获算法的设计

经典的并行码相位搜索框图如图3所示[9-10]：

本地产生的副载波与本地产生的伪码相乘之后变换到频域取共轭，输入信号经过傅立叶变换后与经过傅立叶变换的BOC码相乘，输出结果经过傅立叶逆变换 转换为时域信号，傅立叶逆变换输出的模值表示输入信号与本地伪码的相关结果。改进后的并行码相位算法框图如图4所示：

改进捕获算法如下：

（1）将接收到的中频信号取1ms的数据长度，记为x（n）；

（2）本地载波取中频信号IF±10KHz范围，步长取500Hz，生成41个本地中频载波，并对生成的本地载波进行采样，记为li（n）（i=1，2，…，21）；

（3）将x（n）和li（n）的转置点对点相乘，结果取FFT，记为Fi（k）；

（4）产生本地副载波，相位分别为0°和90°，两路信号分别进行FFT变换到频域中，并取共轭。记为f1*（k）和f2*（k）；

（5）Fi（k）分别与f1*（k）和f2*（k）点对点相乘，结果记为G1（k）和G2（k）；

（6）产生本地的C/A码，并对其进行采样，记为Cs（n）（s为卫星编号）；

（7）对Cs（n）进行FFT，变换到频域中，并取共轭，记为Cs（k）*；

（8）将G1（k）和G2（k）分别与Cs（k）*点对点相乘，结果为Rs1（k）和Rs2（k）；

（9）对Rs1（k）和Rs2（k）进行IFFT，变换到时域中，得到rs1（n）和rs2（n），得到其模平方rs1（n）2和rs2（n）2；

（10）比较rs1（n）2和rs2（n）2的最大值，选择判决那个大就选择哪个，记为rsi（n）2，最大值对应的坐标即为C/A码的起始点和载波粗频。

4 仿真结果及分析

高斯信道信噪比为0dB时的捕获结果如图5所示，局部放大图如图6所示。由图可以看到有1个主峰和2个次峰，这和BOC（1，1）信号的自相关函数有三个峰值是相符的，由图BOC（14，2）捕获图可以看出，峰值位于码相位45094和频率25.542MHz处，图7为BOC（14，2）信道加高斯干扰0dB-34dB的仿真结果。

由图仿真结果可知，当干扰为-36dB时，捕获算法完全失效，主峰与副峰比值基本相同，捕获结果完全被信号淹没，在干扰为-35dB到-27dB时，捕获算法仍然有效，但效果较差，此算法在大于-27dB高斯信道干扰下完全可以捕获到信号的初始码相位和载波频率，为进一步跟踪提供了粗略值。

5 结束语

改进的捕获算法基于并行码相位搜索算法，针对收发端载波不同的问题，在产生本地副载波时分别产生I路和Q路两路信号，分别基于捕获算法，最后对捕获到的峰值进行比较，这样可以选择最优的捕获结果。

参 考 文 献

[1] 杨东凯，樊江滨，张波，张敏译. GNSS应用与方法. 电子工业出版社. 2011.09 p.16-22

[2] 杨力，基于BOC调制的导航信号同步接收关键技术研究. 南京理工大学.2009.12

[3] 楚横林，李春霞. BOC调制导航信号关键技术研究. 2010 Radio Engineering Vol.40 No.6

[4] 王智，耿相铭. Galileo卫星导航系统中的BOC调制与接收技术.上海航天.2007年第6期

[5] Peter Rinder， Nicolaj Betelsen， Design of a single frequency GPS software receiver. Aalborg University 2004.

[6] D Akopian.Fast FFT based GPS satellite acquisition methods.IEE Proceedings Radar， Sonar and Navigation，2005，1 52（4）：277—286.

[7] 杨俊，武奇生. GPS基本原理及其Matlab仿真. 西安：西安电子科技大学出版社. 2006：126-181页

[8] Julien O，Cannon M E，Lachapelle G，et al.A New Unambiguous BOC（n，n） Signal Tracking Technique [A].In：Europe Navigation Conference GNSS 2004[C].2004：17-19P

[9] 刑兆栋. BOC 导航信号处理方法及卫星导航数据的传输. 北京航空航天大学. 2006：58-73页

[10] Kai Borre，Dennis M.AKos，Nicolaj Bertelsen Peter Rinder Soren Holdt Jensen，杨东凯，张飞舟，张波译. 软件定义的GPS和伽利略接收机. 国防工业出版社.2009.3

Based on Parallel Code Phase Search of BOC Signal Acquisition Algorithm of Design and Implementation

Xin Fuguo1，Li Rongfang2

（1. Shaanxi Post and Telecommunication College department of communication，Xianyang 712000，China）

（2. Shaanxi Post and Telecommunication College department of computer，Xianyang 712000，China）

Abstract BOC modulation，as a navigation signal system ，has such better performances as multipath-resistant and anti-jamming ，it can realize spectrum separation under the condition of carrier frequency being shared .This paper first analyzes the characteristic of the frequency spectrum of BOC signal and the autocorrelation function ， put forward based on the concurrent code phase search of the algorithm， the design of orthogonal orthogonal IQ acquisition algorithm， the two road parallel acquisition， the simulation results show the correctness of the algorithm and the superiority.

搜索算法综述 篇7

搜索 (Search) 是通过搜索方法实现从问题的表示到问题求解的过程描述。搜索算法是通过计算机的高性能来有目标地穷举一个问题解空间的部分或所有的可能情况, 从而求出问题解的一种方法。根据搜索有无引导启发信息, 可将其可分为一般搜索和启发式搜索。一般搜索, 是一种没有任何经验和知识引导的、由某种具体规则确定的非智能性搜索;启发式搜索 (Heuristic Search) 是一种有准备的、追求效率而有的放矢的智能搜索, 它要求依据某种与问题有关且有利于尽快找到问题解的知识及信息的引导, 通过逐一状态比较而找到符合规定条件的目标状态解。常用的搜索算法如图1所示。

2 状态空间搜索

状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说, 两点之间求一线路, 这两点是求解的开始和问题的结果, 而这一线路不一定是直线, 可以是曲折的。由于求解条件的不确定性、不完备性, 使求解问题的过程中分枝较多, 这些分支构成一个图, 这个图就是状态空间。问题的求解实际上就是在这个图中找到一条可以从开始到结果的路径, 而寻找路径的过程就是状态空间搜索。

问题的状态空间可用有向图来表达。若图中的每条边都是有方向的, 则称为有向图。有向图中的边是由两个顶点组成的有序对, 有序对通常用尖括号表示, 如< Vi, Vj>表示一条有向边, 其中, Vi是边的始点, Vj是边的终点。< Vi, Vj>和< Vj, Vi>代表两条不同的有向边。如图2 所示。

问题的状态空间图又被称为状态树 (State Tree) 。如图3 所示, 节点sk表示状态, 状态之间的连接采用有向弧 (Arc) , 弧上标以操作数O来表示状态之间的转换关系。

用状态空间法搜索求解问题, 首先要把待求解的问题表示为状态空间图, 把问题的解表示为目标节点sn。求解就是要找到从根节点s1 到达目标节点sn的搜索路径。状态空间图如图4 所示。

在状态图中寻找路径的方法可以看成一种图搜索策略。在状态图搜索中会涉及两个集合, 分别为OPEN表和CLOSED表, OPEN表和CLOSED表分别代表初始集合和满足终止条件的目标集合, 按一定规则把初始结点集合中转换到目标结点集合, 即为图中的路径求解问题。

状态图搜索流程为: (1) 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中; (2) 创建已扩展结点表CLOSED, 初始状态为空表; (3) 检查OPEN表, 若为空表, 则失败退出, 否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解, 成功退出; (4) 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中; (5) 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到表OPEN中, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针; (6) 按某种方法重排OPEN表; (7) 返回第三步继续操作。

从图搜索流程可以看出, 有按规则重排OPEN表的步骤, 该步骤为可选步骤, 是否按照某个规则或方法重新对OPEN表排序, 对应于图搜索过程中的一般搜索和启发式搜索。常用的状态空间图搜索算法有宽度优先搜索算法、深度优先搜索算法、A* 搜索算法等。

3 常用状态空间图搜索算法

3.1 宽度优先搜索

宽度优先搜索状态图搜索, 给定图G= (V, E) 和可以识别的源结点, 对图中的边进行系统性的探索, 以发现可以从源结点s到达的所有结点。该算法能计算出从源结点s到每个可到达结点的距离, 同时生成一棵宽度优先搜索树。该树以源结点s为根节点, 包含所有可以从s到达的结点。在宽度优先搜索树中, 从结点s到结点v的简单路径所对应的就是图结点s到结点v的最短路径。宽度优先搜索算法适用于有向图, 也可用于无向图。

宽度优先搜索的过程: (1) 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中; (2) 创建已扩展结点表CLOSED, 初始状态为空表; (3) 检查OPEN表, 若为空表, 则失败退出, 否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出; (4) 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中; (5) 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到表OPEN中, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针; (6) 返回第三步继续操作。

宽度优先搜索在搜索访问一层时, 需要记住已被访问的顶点, 以便在访问下层顶点时, 从已被访问的顶点出发, 搜索访问其邻接点。在搜索访问下层顶点时, 先从队首取出一个已被访问的上层顶点, 再从该顶点出发, 搜索访问它的各个邻接点。宽度优先搜索能在搜索树中找到从起始节点到目标结点的最短路径。

3.2 深度优先搜索算法

深度优先搜索总是对最近才发现的结点v的出发边进行探索, 直到该结点的所有出发边都被发现为止, 一旦v的所有出发边被发现, 则回溯到v的前驱结点, 搜索该前驱结点的出发边, 重复该过程, 直到从源结点可以达到的所有结点都被发现为止。在状态图中, 起始节点的深度为0, 其后继节点的深度为父节点深度加1。对有些问题, 其状态空间搜索树的深度可能为无限深, 为避免深度值太大, 通常会给出结点扩展的最大深度值, 任何节点的深度值达到最大, 都将其作为没有后继节点处理。

深度优先搜索过程如下:第一, 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中;第二, 创建已扩展结点表CLOSED, 初始状态为空表;第三, 检查OPEN表, 若为空表, 则失败退出。否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出;第四, 若节点n的深度为最大深度值, 则返回第三步;第五, 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中, 如果n没有后继, 返回第三步;第六, 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到OPEN表前, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针;第七, 返回第三步继续操作。

上述两种方法都是一般搜索策略, 非启发式搜索。如宽度优先搜索按照层次进行搜索, 按OPEN表的先后顺序从前到后依次进行考察;深度优先搜索是按照纵向深度进行搜索, 按照OPEN表的先后顺序从后向前依次进行考察。广度和深度优先搜索都没有依据问题本身的特征, 在扩展结点时, 没有分析扩展节点在问题求解上是否有利或能否找到最优解。一般搜索算法生成无用节点量大, 效率低。在扩展结点时, 依据问题本身的特征, 预估出结点的重要性, 就能在搜索时选择有利结点, 以便找到最优解。这种搜索策略为启发式搜索。

估计结点重要性的函数为评估函数f (x) , 评估函数f (x) 定义为从初始节点s1 出发, 约束地经过节点x到达目标节点sg的所有路径中最小路径代价的估计值。评估函数的一般形式为f (x) =g (x) +h (x) , 其中, g (x) 表示从初始节点s1 到节点x的实际代价, 通常称为代价函数;h (x) 表示从x到目标节点sg的最优路径的评估代价, 它体现了问题的启发式信息, 其形式要根据问题的特性确定;h (x) 称为启发式函数。因此, 在确定f (x) 时, 要协调好代价函数和启发式函数的比重。启发式方法把对问题状态的描述转换成对问题解决程度的描述, 这一程度用评估函数的值来表示。

3.3 A* 算法

A* (A-Star) 算法是一种求解出状态空间搜索的最短路径的最快方法。如果一个评价函数可以找出最短路径, 则称之为该函数可采纳性。A* 算法是一个可采纳的较好的算法。

3.3.1 A* 算法原理

A* 算法是一种有序搜索算法, 其评估函数f是根据找最小代价路径来估算结点。每个结点x的估价函数值为两个分量, 即从起始节点到节点x的代价和结点x到目标结点的代价。

A* 算法是将OPEN表中的结点按评估函数f (x) =g (x) +h (x) 进行排序的搜索过程。其中, g (x) 是对g* (x) 的估计, h (x) 为h* (x) 的下界, 即h (x) h* (x) 。g* (x) 是从起始节点S到结点x的最小代价;h* (x) 是从结点x到目标结点的最小代价, 若有多个目标结点, 则为其中最小的一个。

3.3.2 A* 算法搜索过程

第一, 把起始节点S放到一个未扩展结点表OPEN中, 记f=h。

第二, 创建已扩展结点表CLOSED, 初始状态为空表。

第三, 检查OPEN表, 若为空表, 则失败退出, 否则选取OPEN表中未设置过的具有最小f值的结点为最优结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出。若n为非目标结点, 扩展结点n, 生成结点n的后继结点next。

第四, 对所有后继结点操作:其一, 创建从后继结点next返回结点n的引用; 其二, g (next) =g (n) +g (n, next) ;其三, 如果n为OPEN表中的结点, 则该结点为old, 并把它添加至n的后继结点表中, 比较新旧路径代价, 如果g (next) <g (old) , 则重新确定old的父辈结点为n, 记录较小代价g (old) , 同时, 修正f (old) 的值, 若n非OPEN表中的结点, 则判断其是否在CLOSED表中;其四, 如果n在CLOSED表中, 则返回, 否则将其添加到OPEN表中, 并添加next的后继结点表;其五, 计算f值, 返回第三继续判断。

A* 算法实际上是一种基于宽度优先搜索基础上的启发式搜索算法, 通常采用估价函数:f (n) =g (n) +h (n) 对当前的搜索位置进行评估。

4 结语

搜索算法是利用计算机的高性能来有目的地穷举一个问题解空间的部分或所有的可能情况, 从而求出问题的解的一种方法。在上述几种搜索算法中, A* 算法是最优路径搜索方法, 其要解决的问题是如何设法从图中寻找到一条从起点A到目标点B的最优通路。地图寻径中, 搜索算法的应用在国内外研究中仍然是一个热点问题, 但目前仍没有一个完美的解决方案, 故对搜索算法进行进一步研究和改进有一定的学术和应用意义。

参考文献

[1]钟瑛.改进A*算法在游戏地图路径搜索中的应用研究[J].网络安全技术与应用, 2013 (8) .

[2]周先曙.最短路径问题及其解法研究[J].电脑知识与技术, 2010 (10) .

[3]邱磊.基于A*算法的游戏地图寻路实现及性能比较[J].陕西科技大学学报, 2011 (6) :89-93.

[4]翁惠玉, 俞勇.数据结构:题解与拓展[M].北京:高等教育出版社, 2011:151-155.

[5]Patrick Lester.A*Pathfinding for Beginners[EB/OL]. (2012-2-20) [2015-01-04].http://www.policyalmanac.org/games/a Star Tutorial.htm.

[6]陈和平, 张前哨.A算法在游戏地图寻径中的应用与实现[J].计算机应用与软件, 2005 (12) .

[7]刘敏.Dijkstra算法求解最短路径的设计与实现[J].电脑知识与技术, 2012 (12) :2759-2761.

禁忌搜索算法评述 篇8

工程领域内存在大量的优化问题, 对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识, 属于局部优化算法。智能随机算法不依赖问题的性质, 按一定规则搜索解空间, 直到搜索到近似优解或最优解, 属于全局优化算法, 其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法 (Tabu Search, TS) 最早是由Glover在1986年提出, 它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制, 采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦 (破禁) 准则来释放一些被禁忌的优良状态, 以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法, 可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。

迄今为止, TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域, 并显示出极好的研究前景[2,3,4,5,6,7,8,9,11,12,13,14,15]。目前关于TS的研究主要分为对TS算法过程和关键步骤的改进, 用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。

禁忌搜索提出了一种基于智能记忆的框架, 在实际实现过程中可以根据问题的性质做有针对性的设计, 本文在给出禁忌搜索基本流程的基础上, 对如何设计算法中的关键步骤进行了有益的总结和分析。

2 禁忌搜索算法的基本流程

TS算法一般流程描述[1]:

(1) 设定算法参数, 产生初始解x, 置空禁忌表。

(2) 判断是否满足终止条件?若是, 则结束, 并输出结果;否则, 继续以下步骤。

(3) 利用当前解x的邻域结构产生邻域解, 并从中确定若干候选解。

(4) 对候选解判断是否满足藐视准则?若成立, 则用满足藐视准则的最佳状态y替代x成为新的当前解, 并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象, 同时用y替换“best so far”状态, 然后转步骤 (6) ;否则, 继续以下步骤。

(5) 判断候选解对应的各对象的禁忌情况, 选择候选解集中非禁忌对象对应的最佳状态为新的当前解, 同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。

(6) 转步骤 (2) 。

算法可用图1所示的流程图更为直观的描述。

3 禁忌搜索算法中的关键设计

3.1 编码及初始解的构造

禁忌搜索算法首先要对待求解的问题进行抽象, 分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略, 主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示[2], 十进制编码将问题的解用一个十进制串来表示[3], 实数编码将问题的解用一个实数来表示[4], 在某些组合优化问题中, 还经常使用混合编码[5]、0-1矩阵编码等。

禁忌搜索对初始解的依赖较大, 好的初始解往往会提高最终的优化效果。初始解的构造可以随机产生, 但效果往往不够理想, 通常是基于问题特征信息, 借助一些启发式方法产生, 以保证初始解的性能。

3.2 邻域移动、邻域解及邻域解规模

邻域移动, 相关文献也称作邻域操作、邻域结构、邻域变换等。禁忌搜索要想不断进行就要依赖邻域移动来不断拓展搜索空间, 邻域移动是在当前解的基础上, 按照特定的移动策略产生一定数目的新解, 这些新解被称为邻域解, 新解的数目称为邻域解规模。邻域移动的设计通常与问题有关, 如排列置换类组合优化问题, 常用的邻域移动方法是交换、插入、逆序等[3,6,7,8]。不同的移动将导致邻域解个数及其变化情况的不同, 进而影响搜索的质量和效率。在一些应用中为了取得好的搜索效果, 会根据搜索的进展情况动态改变邻域移动策略, 即变邻域移动[9]。邻域移动的设计策略既要保证变化的有效性还要保证变化的平滑性, 即产生的邻域解和当前解既有不同, 又不能差异太大。不同使搜索过程向前进行, 不能差异太大保证搜索是有序而非随机的搜索。邻域解的规模, 也并不总是取可产生邻域解个数的上限, 可以根据需要和经验设定成小于上限的值, 以提高搜索的运行效率。

3.3 解的评价函数

解的评价函数, 相关文献又称其为适应值函数、适配值函数或适应度函数。对于禁忌搜索空间中的解, 通过评价函数来计算其对应的评价函数值, 评价函数值的大小代表了解的优劣程度。根据问题的特性, 可能评价函数值越大越好, 反之也可能越小越好。依据数学方法, 两种目标可以等价转换。直接把优化目标作为评价函数是一种简单、直观的方法, 同时任何与优化目标等价的变换函数也可以作为评价函数。有时, 目标函数的计算困难或是耗时较多, 则可以取体现问题目标的特征值来替代计算, 但必须要保证特征值与问题目标有一致的最优性。

与遗传算法的评价函数类似, 在求解带有约束的优化问题时, 可以将解违反约束的情况作为惩罚因子加入评价函数, 从而规避传统启发式方法中对于约束的复杂处理。基本形式如公式 (1) 。

其中, P (Rj, x) 为第j个约束的惩罚值, 当解满足约束时, 惩罚值为0。关于评价函数的设计详见文献[10]。

3.4 禁忌表、禁忌对象、禁忌长度、候选解及禁忌频率

禁忌表是用来存放禁忌对象的一个容器, 被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索, 可见禁忌表模拟了人的记忆机制, 防止搜索陷入局部最优, 进而探索更多的搜索空间。禁忌表可以使用数组、队列、栈、链表等顺序结构实现, 每个顺序结构的元素定义根据具体问题确定。

禁忌对象就是放入禁忌表中的元素, 归纳而言, 禁忌对象通常可选取状态 (解的编码) 本身或状态分量或适配值的变化等, 禁忌范围依次扩大[1]。其中选取状态本身易于理解, 也最为常用, 禁忌范围最小。

禁忌长度就是每个禁忌对象在禁忌表中的生存时间, 也称为禁忌对象的任期。当一个禁忌对象加入禁忌表时, 设置其任期为禁忌长度值, 搜索过程每迭代一次, 禁忌表中的各禁忌对象的任期自动减1, 当某一禁忌对象任期为0时, 将其从禁忌表中删除。任期不为0的禁忌对象处于禁忌状态, 不能被搜索过程选为新解。

候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价 (包括空间和时间) , 要求禁忌长度和候选解集尽量小, 但禁忌长度过小将使搜索无法跳出局部最小, 候选解集过小将使搜索早熟收敛。候选解集的大小常根据问题特性和对算法的要求确定, 禁忌长度的选取则主要有静态和动态两种方法。静态方法是指在搜索过程中, 禁忌长度是一个固定值, 比如, 其中n为问题维数或规模。动态方法是指在搜索过程中, 禁忌长度也是动态变化的, 当算法搜索能力较强时, 可以增大禁忌长度从而延续当前的搜索能力, 并避免搜索陷入局部优解, 反之亦然。

禁忌频率记录每个禁忌对象出现在禁忌表中的次数, 以此作为搜索过程的重要参考, 如若某个对象出现频繁, 则可以增加禁忌长度来避免循环。此外可以把某对象的禁忌频率作为评价解的因素加入评价函数来指导搜索过程。

3.5 特赦准则

特赦准则, 相关文献也称为藐视准则、破禁准则[11]、释放准则等。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解 (或状态) 被禁时, 能够释放特定解 (或状态) , 从而实现高效的全局优化搜索。

3.6 终止准则

终止准则也称停止准则, 即算法在何条件下停止搜索过程。实际应用中无法使用在禁忌长度充分大的条件下实现状态空间的遍历这一理论收敛条件, 往往使用如下近似终止 (收敛) 准则。

(1) 算法迭代次数达到指定最大次数停止[8,11]。

(2) 最优解的目标函数值小于指定误差。

(3) 最优解的禁忌频率达到指定值。

4 总结和展望

本文简述了禁忌搜索算法的发展、特点及应用, 给出了基本禁忌搜索算法实现的流程, 对禁忌搜索设计过程中的关键步骤进行了分析和总结, 为推广禁忌搜索算法在优化领域的应用有一定意义。

今后关于禁忌搜索算法的研究热点主要有以下几个方面。

(1) 与其他优化算法结合, 如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合, 构成更新型的混合优化算法[2,4,5,12,13,14,15]。

(2) 为推广禁忌搜索算法在超大规模优化领域中的应用, 突破禁忌搜索的串行性限制, 研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略[1]。

(3) 对禁忌搜索算法本身的关键步骤进行改良设计。如根据禁忌频率信息在算法中增加集中搜索和分散搜索, 分别实现优良区域的重点搜索和搜索范围的扩展。

(4) 探索禁忌搜索算法适于应用的新的优化领域。

搜索算法 篇9

关键词：禁忌搜索算法,最短路径优化算法,智能路由,Dijkstra算法

0 引言

计算机网络的运行质量与路由的选择方法密切相关。不同的信息传输要求可以选择和采用不同的路由选择方法。目前的网络已经十分庞大, 并且以后发展的趋势会越来越大, 传统的互联网络路由协议会显得有些力不从心, 因此使用禁忌搜索算法对路由 (链路-状态路由选择算法 (Link-State Routing, L-S) ) 进行优化, 有着十分重要的作用。禁忌搜索算法是人工智能的一种体现, 是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象, 并在进一步的迭代搜索中尽量避开这些对象, 从而保证对不同的有效搜索途径的探索。该算法优化最短路径算法不仅能够优化路由的选路方式和选路速度, 还能对路径上Qos进行优化, 使网络发挥到最大的性能。

1 禁忌搜索算法求解最短路径优化问题的数学模型框架

假设:已知整个网络的拓扑结构和各链路的长度, 求网络中任意2个给定节点之间的最短通路。若将已知的各链路的长度改为路由时延或其他参数, 例如, 带宽, 经过的节点数, 平均通信量, 平均队列长度等因素及其给组合, 就相当于求任意2个节点之间且有最小时延或最小代价的通路。因此, 求最短通路的算法且有普遍意义。

输入:图G= (B (G) , E (G) ) 有一个源顶点s和一个汇顶点t, 以及对所有的边ij∈E (G) 的非负边长Cij。

输出:G中从S到T的最短路径的长度。

第0步:从对每个顶点做临时标记L开始, 做法如下:L (S) =0, 且对除S外所有的顶点L (I) =∞。

第1步:找带有最小临时标记的顶点 (如果有结, 随机地取一个) 。使该标记变成永久标记, 即该标记不再改变。

第2步:对每个没有永久标记但是又带有永久标记的顶点相邻的顶点j, 按如下方计算一个新的临时标记:L (j) =Min{L (i) +Cij}, 求最小是对所有带有永久标记的顶点i做的。

第3步:判断最新永久顶点y与最新临时顶点x是否相等, 如果相等则标记此路径为冗余路径:H=Dis{L (y) -L (x) }。再判断顶点y, x延伸节点集合里是否分别存在x, y顶点.如果是则将之删除。重复第2步和第3步, 直到所有的顶点都打上了永久标记为止。

2 禁忌搜索算法的基本框架

2.1 初始化阶段

步骤1:加载问题相关数据, 初始化变量, 生成初始解x0∈X (X为可行解空间) , 清空禁忌表, 设计数器为0。

2.2 搜索阶段

步骤1:搜索不在禁忌表内或满足藐视法则的邻域移动x*∈N (x0) 奂X, 其中f (x*) ≤f (x) , 坌x∈N (x0) , 而N (x0) 是x0的所有邻域解。

步骤2:更新禁忌表T及目前最优解的记录, 执行邻域移动x0←x*。

步骤3:判断是否已达到终止条件。如过达到, 则终止搜索并输出最优解;否则, 计数器记录累加1并返回此阶段步骤1继续执行。

3 算法验证

在此验证测试中, 通过设置不同的算法参数, 分别对10个例题重复进行求解, 将得出的结果进行统计分析, 以获得算法最优参数设置的方法。

4 禁忌表的大小

禁忌表的长度过小会导致搜索迂回进行, 从而陷入局部最优的状态;而禁忌表长度过长, 则会对搜索进行过度的限制, 从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间, 并且将该区域平均分为5个区间, 区间的界限为 (0.5+2.5/4 x) n, (x∈[0, 4]) 取整的结果, 其中n为顶点数目, x为禁忌表长度系数。

5 算法最大迭代次数

在此参数的测试中, 我会先给一个较大的迭代次数作为迭代上限, 如顶点数目在50个以下的实例中设置为2000, 顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数, 这个迭代次数称为最优迭代值, 以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。

6 测试方法

本次测试中, 使用10个例题进行, 每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据, 上述测试会重复5次。因此, 在本次测试中会产生10×5×3×5=750组数据。

利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图” (图1) 。横轴代表了禁忌长度系数;纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε= (C-C*) /C*×100%。其中, C为算法计算出的路径总距离, C*为问题已知的最优解的总距离。

根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图” (图2) 。我把横轴设为各个初始解生成算法, 而纵轴依然表示了与例题已知最优解偏离百分比, 图表中的各条折线, 表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。

图2可以总结出, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 并且使用任意内接法作为初始解生成方法, 所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的 (0.67%) 。

当两个参数的组合达到较低的偏离百分比时, 我们希望能通过最少的迭代次数来获得较低的偏离百分比, 所以, 平均最低的最优迭代值是各个例题的最优参数的组合。

至于算法最大迭代次数的测试方法, 我先对表1中的十个最短路径问题按顶点数量分成两组, 分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较, 从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。

注:表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.

从表1中可以获悉当顶点数目不大于50时, 用任意内接法生成初始解, 且禁忌表长度系数为3时, 若要获得质量较佳的解算法所需的最大迭代次数至少为1306次;同样道理, 当顶点数目大于50时, 若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此, 我建议当顶点数目不大于50时, 算法最大迭代次数应设为2000次;当顶点数目大于50时, 算法最大迭代次数应设为4000次。

编译环境及所描述的测试环境, 均在同一台机器上执行。机器的硬件如下, 处理器为Intel Core i7-2610UE Processor (1.5 GHz) 、内存4GB。值得一提的是, 此程序在运行时, 中央处理器并不是满负载运行, 故处理器的时钟频率不能用来计算程序执行的时间及效率。

7 测试小结

虽然课题并未通过大规模的测试来获得算法参数的精确设定方法, 但通过前面几个小节的测试和分析, 可以总结出以下结论:

(1) 参数的设置会因问题的实例不同而有所差异;

(2) 总的来说, 初始解的生成算法对最终解的质量并无明显的影响, 但建议使用任意内接法;

(3) 禁忌表长度对最终解的质量有明显的影响, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 所获得的最终解的偏离值是最低的;

(4) 当顶点数目不大于50时, 最大迭代次数设为2000;当顶点数目大于50时, 最大迭代次数应设为4000。

8 总结

在实际应用中, 没有一种算法对任何问题都是有效的, 不同的算法有不同的适用领域, 也有它不适合求解的问题类型。因此, 算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果, 以下几点是在未来我研究的主要方向:

(1) 在本文中的禁忌搜索算法主要使用了全邻域搜索, 所以当顶点数目增加时, 算法的搜索速度会变得较慢, 在未来的研究, 我会尝试使用各种算法缩小邻域的搜索范围, 以增加搜索速度。

(2) 对算法加入多样性和集中性策略, 以加快跳出局部最优的能力。

(3) 将禁忌搜索算法与算法进行混合, 拓展算法的适用域, 提高算法的性能。

博弈及其常用搜索算法初探 篇10

搜索算法是人工智能的一个基本问题。算法的好坏直接关系到智能系统的性能与效率, 也是人工智能领域核心问题之一。搜索就是根据实际的问题, 在推理过程中发掘可利用的知识, 进而找到一条代价较小的解决问题的途径。搜索有两种形式:盲目搜索和启发式搜索。盲目搜索又称为无信息搜索, 仅仅根据预先制定的策略进行搜索, 在搜索中获得的新知识不用来改进策略。启发式搜索在搜索过程中, 需要对每一个搜索位置进行评估, 从而得到最好的位置再进行下一步的搜索, 直到目标达成。在人机博弈过程中, 博弈树搜索算法是核心, 它与规则及估值构成一个完整的系统。

2 博弈树

博弈是一类富有智能行为的竞争活动, 如下棋、打牌、战争等, 是启发式搜索的一个重要应用领域。最简单的一种博弈是双人完备信息博弈。双人完备信息博弈指两位选手对垒, 轮流走步, 每一方不仅知道对方已经走过的棋步, 而且还能估计出对方未来的走步, 对弈的结果是一方赢, 另一方输, 或者双方和局。这里就以双人完备信息博弈作为主要的对象, 为考虑复杂的博弈打下基础。

设博弈的双方中一方为甲方, 另一方为乙方。在博弈过程中, 某一方当前有多个行动方案可供选择时, 他总是挑选对自己最为有利而对对方最为不利的行动方案。此时, 如果我们站在甲方的立场上, 则可供甲方选择的若干行动方案之间是“或”的关系, 因为这是主动权在甲方手里, 他可以选择这些行动方案中的任何一个行动方案。但是, 若乙方也有若干个可供选择的行动方案, 则对甲方来说这些行动方案之间是“与”的关系, 因为乙方走棋时主动权在乙方手里, 这些可供选择的行动方案中的任何一个都可能被乙方选中, 甲方必须考虑对自己最不利的情况的发生。这个博弈的过程用图表示出来, 得到的就是一颗“与/或”树, 如图1所示。“与/或”树始终是站在某一方的立场上得出的, 对于不同的走棋方“与/或”树不同。描述博弈过程的“与/或”树就是博弈树 (game tree) 。图1中方形节点代表轮到甲方走棋的棋局, 圆形节点代表轮到乙方走棋的棋局。

博弈树的每个结点代表一个问题, 根结点代表初始问题。具有儿子的结点称为非端结点, 每个非端结点或具有与儿子, 或者具有或儿子。如果任何一个或儿子代表的问题得到解决, 则具有或儿子的结点代表的问题就得到解决;如果所有与儿子代表的问题都得到解决, 则具有与儿子的结点代表的问题得到解决。没有儿子的节点称为端结点, 每个端节点代表了一个或者可解或者不可解的基本问题。博弈树搜索是寻找一棵在某种条件下最好的解树。

3 算法

3.1 极大极小法

极大极小算法是为博弈中的一方寻找一个最优行动方案的方法。为了找到当前的最优行动方案, 需要对各个行动方案可能产生的后果进行比较。具体地说, 就是要考虑每一方案实施后对方可能采取的所有行动, 并计算可能的分值。为计算分值, 需要定义一个估值函数, 用来估算当前博弈树叶节点的分值。当叶节点的估值计算出来后, 再推算出父节点的分值。推算的方法是, 对于“或”节点, 选其子节点中一个最大的分值作为父节点的分值, 这是为了使自己在可供选择的方案中选出一个对自己最有利的方案;对于“与”节点, 选其子节点中一个最小分值作为父节点的分值, 即考虑最坏的情况。如果一个行动方案获得较大的倒推值, 则它就是当前最好的行动方案。图1给出了计算倒推值得实例。详细描述如下:假使最后一层叶子节点为终节点, 并且已经计算估值函数值如图所示。由于最后一层为或节点, 其父节点为与节点, 那么在父节点进行求值时, 取其子节点中的最大值为其值, 对节点E来说, 其子节点K、L中最大值为20, 故E取值20。对节点B来说, 其为或节点, 其子节点E、F中最小值为19, 故其取值为19。通常将取极大值的一方称为Max, 另一方称为Min。

3.2 剪枝技术

用极大极小算法求倒推值的过程中, 存在着两种明显的冗余现象。第一种现象是极大值冗余, 如图2 (a) 所示的博弈树, 我们要用极大极小值算法找出极大值节点A的最佳着法。先对A的第一个子节点B进行搜索, 得出B的各子节点的评价分别是20、25、19和30, 那么B的值为19。节点A的值应是节点B和节点C的值中之较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的诸子节点的值中之极小者, 此极小值一定小于等于节点D的值, 因此也一定小于节点B的值, 这表明继续搜索节点C的其他诸子节点E、F...已没有意义, 它们不能做任何贡献, 于是可以把以节点C为根的子树全部剪去。这种优化称为α剪枝。图2 (b) 是与极大值冗余对偶的现象, 称为极小值冗余。节点A的值应是节点B和节点C的值中之较小者。现在已知节点B的值小于节点D的值。由于节点C的值应是它的诸子节点的值中之极大者, 此极大值一定大于等于节点D的值, 因此也一定大于节点B的值, 这表明继续搜索节点C的其他诸子节点已没有意义, 可以把节点C为根的子树全部剪去, 这种优化称为β剪枝。

3.3静态估值函数与算法

对于博弈树求解有了良好的搜索算法还只是问题的一个方面, 问题的另一个方面就是静态估值函数。只有有了良好的静态估值函数才能保证较快地找到正解。而静态估值函数是对博弈的综合评估, 该函数的好坏直接决定解题能力强与弱。通常一个优秀的选手总有一个良好的对棋局的判断能力, 能够协调各棋子的关系、取舍, 有机地组织各棋子的进攻步调, 控制棋局的发展。如果要把这一整套的思维物化成一个数值函数来评估, 本身就是一个相当复杂的问题。有时一个损失极大的走步, 在若干步之后体现出强大的优越性, 有时一个看似取得明显实利的走步, 却在对方步步紧逼之下变得极为不利。怎样评估一个棋局的优越性是值得思考的问题。然而无论怎样设计静态估值函数, 都难免有山脊、平原和小丘现象出现, 这些现象的产生是问题本身所具有的, 估值函数无法克服, 主要通过搜索算法来解决。

4总结

本文着重讨论了什么叫博弈, 及博弈问题的两种常用解法, 并对静态估值函数进行了定性的分析。在实际应用中, 应综合考虑算法及估值函数的设计, 这样才能更好地解决博弈问题。

参考文献

[1]Stuart Russell, Peter Norvig著, 姜哲、金奕江、张敏、杨磊, 等译.人工智能——一种现代方法 (第二版) [M], 北京:人民邮电出版社, 2004.

[2]肖齐英, 王正志.博弈树搜索与静态估值函数[J], 计算机应用研究, 1997年第4期.

[3]李红, 吴粉侠, 刘小豫.博弈树搜索算法研究[J], 长春工程学院学报 (自然科学版) , 2007年第8卷第2期.

[4]孙伟, 马绍汉.博弈树搜索算法设计和分析[J], 计算机学报, 1993年5月.

[5]杨涛, 何志均, 俞瑞钊.博弈树函数及其计算优化[J], 计算机学报, 1988年2月.

[6]岳金朋, 冯速.博弈树搜索算法概述[J], 计算机系统应用, 2009年第9期.

[7]张聪品, 刘春红, 徐久成.博弈树启发式搜索的α-β剪枝技术研究[J], 计算机工程与应用, 2008.

搜索引擎的现状及算法研究 篇11

关键词：搜索引擎构成,算法,搜索工具

0 引言

随着信息爆炸时代的来临, 互联网上充斥着大量的信息, 越来越让人应接不暇。在这种情况下, 用于信息检索的搜索引擎工具应运而生, 它帮助人们在海量信息中寻找着自己感兴趣的内容, 成为了网民生活中不可缺少的一部分。

本文首先介绍了当前搜索引擎的发展情况, 然后介绍常用的搜索算法, 并对当前国外常用的搜索工具进行了比较分析, 在文章的最后进行总结和展望。

1 搜索引擎的现状

1.1 搜索引擎的原理

搜索引擎 (Search engines) 实质上是一种网页网址检索系统, 提供分类和关键词检索的途径。它根据检索规则从其他信息服务器上得到数据并对数据进行加工处理, 自动建立索引, 并通过检索接口为用户提供信息查询服务, 能够自动对网络资源建立索引或进行主题分类, 并通过查询语法为用户反馈相应的资源[1]。

1.2 搜索引擎的构成

搜索引擎主要由搜索器、索引器、检索器和用户接口等四个部分组成。

(1) 搜索器。搜索器的功能是在互联网中漫游、发现和搜集信息。它要尽可能多、尽可能快地搜集各种类型的新信息。同时因为互联网上的信息更新很快, 所以还要定期更新己经搜集过的旧信息, 以避免死连接和无效连接。

(2) 索引器。索引器的功能是理解搜索器所搜索的信息, 从中抽取出索引项, 用于表示文档以及生成文档库的索引表。索引器可以使用集中式索引算法或分布式索引算法[3]。一个搜索引擎的有效性在很大程度上取决于索引器的质量。

(3) 检索器。检索器的功能是根据用户的查询在索引库中快速检出文档。进行文档与查询的相关度评价, 对将要输出的结果进行排序, 并实现某种用户相关性反馈机制。

(4) 用户接口。用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。

1.3 搜索引擎的分类

根据不同的分类方法, 可以对搜索引擎进行不同的分类。常见的分类方法主要有五种:按搜索内容的详略划分, 按搜索资源的来源划分, 按覆盖范围划分, 按检索方式划分和按检索机制划分[3]。

2常用搜索算法

搜索算法主要是应用于搜索器和索引器上, 这里着重介绍二种用于索引器的算法:根据Web结构对网页内容进行分类的索引器算法和根据用户需求对网页检索进行分类的索引器算法, 以及一种搜索器算法即增量方法的搜索器。这三种算法在实践中具有广泛的应用。

2.1 根据Web结构来对网页进行内容分类

传统的分类方法为基于网页文本或利用人工进行分类, 由于网页文本可能并不含有准确表示网页所属类别的关键字, 而利用人工分类又可能有较大的主观性而且速度较慢, 故可以利用Web结构进行较为准确客观快速的分类[4]。

(1) Web结构。一个网页可以分为标题 (title) 、网页文本 (Full text) 、锚文本 (Anchor text) 、扩展锚文本 (Extended anchor text) 和链接 (Link) 。

(2) 实现步骤。利用Web结构对网页进行分类, 需要如下的步骤: (1) 摘取网页重要的特性来训练一个基于网页文本分类的分类器; (2) 利用锚文本和扩展锚文本来产生虚拟文本代替原有的网页文本, 再对虚拟文本进行分类; (3) 将步骤 (1) 和 (2) 产生的结果进行合并来提高准确性。

(3) 小结。通过将基于页面文本、锚文本、扩展锚文本三种分类方法合并, 分类的准确性可达到90%以上, 而单独利用一种方法最多只有75%左右的准确性。

2.2 根据用户需求对网页检索进行分类

网页不仅可以根据其内容有不同的分类, 根据用户使用目的的不同, 也可以进行分类。通过对用户需求进行分类, 再把网页分成对应的类别, 可以提高网页检索的准确性。

2.2.1 用户需求分类

用户需求可以分为搜索主题、搜索主页、搜索服务。

(1) 搜索主题是指用户输入关键词, 寻找这个词的解释、说明, 一种“是什么”的搜索, 是搜索信息的。如“堰塞湖”、“什么是堰塞湖”。

(2) 搜索主页是指用户寻找某一特定网站的具体网址, 是一种“在哪里”的搜索。如搜索“中南大学主页”。

(3) 搜索服务是搜索提供相应服务的网页或告诉他如何得到某一服务的网页, 是一种“怎么办”的搜索。如“买奥运门票”。

2.2.2 分类方法

由于分类方法的相似性, 这里只讨论对搜索主题、搜索主页两种需求进行分类的方法。常见的有四种分类方法。

(1) 利用关键词词性。主页搜索通常只含有名词, 主题搜索含有动词, 如果含有除系动词以外的动词就认为是主题搜索。

(2) 作为链接文本的出现率。若某关键词经常出现在链接文本中, 则认为该搜索为主页搜索。

(3) 关键词常属类别。有一些词通常常用于主题搜索, 而另一些词常用于主页搜索。

(4) 关键词间的依赖性。若几个词间的依赖性大于设定的主题搜索阈值或主页搜索阈值, 则认为它是主题或主页搜索。

2.2.3 小结

由于用户在输入同样的关键字时, 可能有不同目标, 所以无法达到完全准确分类, 通过对上述四种分类方法的合并, 可以有效提高分类的准确性。

2.3 利用增量方法实现搜索器

由于Web中网页经常发生变化, 搜索引擎为了保证搜索结果的有效性就要经常利用搜索器更新数据库中的现有网页。通过对Web中网页更新的观察, 发现不同类型的网页具有不同的更新频率, 可以根据网页的特性, 逐渐地对数据库中的信息进行更新。

2.3.1 相关数据的调查

通过对25, 000, 000个网页四个月的观察, 发现了Web中网页的变化具有如图1所示的规律, 不同后缀名网页生命周期具有如图2所示的规律。

(1) 网页变化规律。横坐标表示发生变化的时间间隔, 纵坐标表示发生变化的网页数量占总网页的比例。

(2) 网页生命周期。横坐标表示网页生命周期的长短, 纵坐标表示具有这种生命周期的网页数量占所有网页的比例。

2.3.2 增量搜索器设计思想

通过2.3.1的分析, 我们可以设计稳定的爬行器 (steady crawler) , 它持续地访问Web中的网页并增量地更新。通过使用增量搜索器可以保持数据库中信息的及时性并提高数据库中信息的质量。

设计增量搜索器时, 根据网页的更新周期, 来决定不同的时间间隔再次访问哪些不同类型的网页, 又根据网页的生命期决定用新发现的网页替换哪些网页[5]。

2.3.3 小结

与传统的周期性更新数据库全部信息的方法相比, 增量搜索器通过有效利用Web中网页更新和生命周期的特性, 提供了一种更有效率, 更节省网络带宽, 并能更加及时发现网络中新页面的搜索器方法。

3 具体实例

介绍和分析了国内外著名的搜索引擎工具Google (谷歌) , 百度和Yahoo (雅虎) 。

3.1 Google

Google成立于l997年, 是目前规模最大的搜索引擎。Google的搜索规则:以关键词搜索时, 返回结果中包含全部及部分关键词;短语搜索时默认以精确匹配方式进行;不支持单词多形态和断词查询;字母无大小写之分.默认全部为小写。Google借用Dmoz的目录索引提供分类目录查询, 默认按PageRank的分值高低对网站进行排序。

3.2 百度

百度成立于2000年, 是全球最大的中文搜索引擎, 主旨是“让人们最便捷地获取信息, 找到所求”, 同样采用基于内容的搜索方法。网页的排名根据关键词分数, 域名权重, 链接分数, 用户数据, 网站内容分数和人干干预六大因素来计算PageRank[5]。

3.3 Yahoo

Yahoo, 曾经的搜索引擎之王, 最早的目录索引之一, 也是目前重要的搜索服务网站, 其数据库中的注册网站无论是在形式上还是内容上质量都非常高。由于Yahoo的分类库是由人工维护的, 也不提供全文关键词检索服务, 因此对于较为专业偏僻的查询很难提供满意的结果。

4 结语

不可否认, 搜索引擎自身技术还存着一些有等解决的问题, 如语义检索、内容检索等, 视频检索也越来越成为人们关注的重点之一。

搜索引擎的未来发展方向, 主要有网站内和企业局域网内搜索引擎的普及化, 某一领域内的搜索专业化, 搜索内容的多样化, 搜索形式的个性化、智能化等。

参考文献

[1]Amit Singhal and Marcin Kaszkiel, "A Case Study in Web Search using TREC Algorithms", International World Wide Web Conference (WWW) , 2001.

[2]Charu C.Aggarwal, Fatima Al-Garawi and Philip S.Yu, "Intelligent Crawling on the World Wide Web with Arbitrary Predicates", International World Wide Web Conference (WWW) , 2001.

[3]In-Ho Kang and GilChang Kim, "Query type classification for web document retrieval", SIGIR Special Interest Group on Information Retrieval (SIGIR) , 2003.

[4]候越先, 张鹏, 于瑞国.基于内容相关性挖掘的反馈式搜索引擎框架[J].天津大学学报, 2008