(完整版)启发式搜索算法

人工智能基础实验报告

实验名称：八数码问题

姓名：张俊

学号：2220092333

指导老师：邓安生

启发式搜索算法

1. 实验内容：

使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题A *算法，采用估价函数

()()()()

w n f n d n p n ??=+???， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的

熟练掌握启发式搜索A *算法及其可采纳性。

3. 实验原理

八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

4.源代码

#include

#include

#include

#include

#include

#include

#include //以上为C++源文件

using namespace std;

static int space=0;

int target[9];

class EightNum//定义一个EightNum 类

{

public:

int num[9];

int f;//初始状态与目标状态相比，棋子错放个数

int deap;//深度

int evalfun;//状态的估价值

EightNum *parent;

//以下为类内成员函数的声明

EightNum(int nnum[9]);

int get_evalfun();

int get_deapfun();

void eval_func(int id);

int Canspread(int n);

void Spreadchild(int n);

void getnum(int num1[9]);

void setnum(int num1[9]);

void show(void);

int operator ==(EightNum& NewEightN);

int operator ==(int num2[9]);

int Shownum();

};

//-----------------------以下为EightNum类成员函数定义-----------------// class Stack

{

private:

EightNum * eightnum;

public:

Stack * next;

EightNum * Minf();

EightNum * Belong(EightNum * suc);

void Putinto(EightNum * suc);

};

EightNum::EightNum(int nnum[9]){//此函数功能为：初始化num[]；for(int i=0;i<9;i++)

num[i]=nnum[i];

f=0;

deap=0;

parent=NULL;

}

int EightNum::get_evalfun(){

return evalfun;

}

int EightNum::get_deapfun(){

return deap;

}

void EightNum::eval_func(int id){//此函数为估价函数

int i,qifa;

qifa=0;

switch(id){

case 1:{

for(i=0;i<9;i++){

if(num[i]!=target[i])

qifa++;

}

break;

}

case 2:{

int j, h1,h2;

for(i=0;i<9;i++){

for(j=0;j<9;j++){

if(num[j]==i)h1=j;

if(target[j]==i)h2=j;

}

qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3)));

}

break;

}

case 3:{

int j, h1,h2;

for(i=0;i<9;i++){

for(j=0;j<9;j++){

if(num[j]==i)h1=j;

if(target[j]==i)h2=j;

}

qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3)));

}

qifa=3*qifa;

break;

}

default :break;

}

f=qifa;

if(this->parent==NULL) deap=0;

else deap=this->parent->deap+1;

evalfun=deap+f;

}

int EightNum::Canspread(int n)

{//判断空格"0"可否移动

int i,flag = 0;

for(i = 0;i < 9;i++)

if(this->num[i] == 0)break;

switch(n)

{

case 1:

if(i/3 != 0)flag = 1;break;

case 2:

if(i/3 != 2)flag = 1;break;

case 3:

if(i%3 != 0)flag = 1;break;

case 4:

if(i%3 != 2)flag = 1;break;

default:break;

}

return flag ;

}

void EightNum::Spreadchild(int n)

{//扩展child节点的子节点

int i,loc,qifa;

for(i = 0;i < 9;i++)

this->num[i] = this->parent->num[i];

for(i = 0;i < 9;i++)

if(this->num[i] == 0)break;

if(n==0)

loc = i%3+(i/3 - 1)*3;

else if(n==1)

loc = i%3+(i/3 + 1)*3;

else if(n==2)

loc = i%3-1+(i/3)*3;

else

loc = i%3+1+(i/3)*3;

qifa = this->num[loc];

this->num[i] = qifa;

this->num[loc] = 0;

}

void EightNum::getnum(int num1[9]){ for(int i=0;i<9;i++)

num1[i]=num[i];

}

void EightNum::setnum(int num1[9]){ for(int i=0;i<9;i++)

num[i]=num1[i];

}

void EightNum::show(){//输出函数

for(int i=0;i<9;i++){

cout<

if((i+1)%3==0)

cout<<"\n";

}

cout<<"--------------------";

}

int EightNum::Shownum()

{

if(this == NULL)return 0;

else

{

int n = this->parent->Shownum();

this->show();

cout<

return n+1;

}

}

int EightNum::operator ==(EightNum& NewEightN){

int compere=1;

for(int i=0;i<9;i++)

if(num[i]!=NewEightN.num[i]){

compere=0;

break;

}

if(compere==0) return 0;

else return 1;

}

//-----------------------以下为分函数的定义---------------------//

//判断是否有解的函数

int solve(int num[9],int target[9]){

int i,j;

int num_con=0,tar_con=0;

for(i=0;i<9;i++)

for(j=0;j

if(num[j]

num_con++;

if(target[j]

tar_con++;

}

num_con=num_con%2;

tar_con=tar_con%2;

if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1))

return 1;

else

return 0;

}

EightNum * Stack::Minf()

{

Stack * qifa =this->next;

Stack * min = this->next;

Stack * minp = this;

EightNum * minx;

while(qifa->next != NULL)

{

if((qifa->next->eightnum->get_evalfun()) < (min->eightnum->get_evalfun()))

{

min = qifa->next;

minp = qifa;

}

qifa = qifa->next;

}

minx = min->eightnum;

qifa = minp->next;

minp->next = minp->next->next;

free(qifa);

return minx;

}

//判断节点是否属于OPEN表或CLOSED表

EightNum * Stack::Belong(EightNum * suc)

{

Stack * qifa = this-> next ;

if(qifa == NULL)return NULL;

while(qifa != NULL)

{

if(suc==qifa->eightnum)return qifa ->eightnum;

qifa = qifa->next;

}

return NULL;

}

//把节点存入OPEN 或CLOSED 表中

void Stack::Putinto(EightNum * suc)

{

Stack * qifa;

qifa =(Stack *) malloc(sizeof(Stack));

qifa->eightnum = suc;

qifa->next = this->next;

this->next = qifa;

}

int BelongProgram(EightNum * suc ,Stack *Open ,Stack *Closed ,EightNum goal,int m )

{

EightNum * qifa = NULL;

int flag = 0;

if((Open->Belong(suc) != NULL) || (Closed->Belong(suc) != NULL))

{

if(Open->Belong(suc) != NULL) qifa = Open->Belong(suc);

else qifa = Closed->Belong(suc);

flag=1;

}

else

{

Open->Putinto(suc);

suc->eval_func(m);

}

return flag;

}

//扩展后继节点总函数

void Spread(EightNum * suc, Stack * Open, Stack * Closed, EightNum goal,int m)

{

int i;

EightNum * child;

for(i = 0; i < 4; i++)

{

if(suc->Canspread(i+1))

{

space++;

child = (EightNum *) malloc(sizeof(EightNum));

child->parent = suc;

child->Spreadchild(i);

child->eval_func(m);

if(BelongProgram(child, Open, Closed, goal,m)) //判断子节点是否属于OPEN或CLOSED表

free(child);

}

}

}

//执行函数

EightNum * Process(EightNum * org, EightNum goal, Stack * Open, Stack * Closed,int m)

{

while(1)

{

if(Open->next == NULL)return NULL;

EightNum * minf =Open->Minf();

Closed->Putinto(minf);

if((*minf)==goal)return minf;

Spread(minf, Open, Closed, goal,m);

}

}

//------------------------A*算法搜索函数----------------------//

void A(int id,EightNum start,EightNum Target)

{

EightNum * result;

space=0;

float time;

Stack *Open = (Stack *) malloc(sizeof(Stack));

Open->next = NULL;

Stack *Closed = (Stack *) malloc(sizeof(Stack));

Closed->next = NULL;

clock_t startt,finisht;

startt=clock();//开始时间

start.eval_func(id);

Open->Putinto(&start);

result = Process(&start, Target, Open, Closed,id); //进行剩余的操作

cout<<"\n搜索过程:\n"<Shownum()<

finisht=clock();

time=(float)(finisht-startt);

cout<

cout<

cout<<"ms, ";

cout<<"所耗空间:";

cout<

cout<<"块, "<

}

//-----------------------------主函数-----------------------------//

int main(void)//主函数

{

int i,j;

int flag;

int num[9];

int error;

do{

error=0;

cout<<"请输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开):"<

for(i=0;i<9;i++){

flag=0;

cin>>num[i];

for(j=0;j

if(num[j]==num[i])

flag=1;

if(num[i]<0||num[i]>8||flag==1){

error++;

}

}

if(error!=0)

cout<<"输入数据错误!请重新输入!"<

}while(error!=0);//输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开）；

int error1;

do{

error1=0;

cout<<"请输入新的目标状态(用0代表空格,“棋子”间用空格隔开):"<

for(i=0;i<9;i++){

flag=0;

cin>>target[i];

for(j=0;j

if(target[j]==target[i])

flag=1;

if(target[i]<0||target[i]>9||flag==1){

error1++;

}

}

if(error1!=0)

cout<<"输入数据错误!请重新输入!"<

}while(error1!=0);//输入八数码问题的目标状态(用0代表空格,中间用空格隔开）；

EightNum start(num),Target(target);

int m=solve(num,target);//判断初始状态到目标状态是否有解，有解返回1，误解返回0；if(m==0){

cout<<"此状态无解!"<

return 0;

}

int id=0;

while(id!=3){

cout<<"1. 错放的棋子个数为;\n2.每个棋子与目标位置之间的距离总和为;"<

cout<<"3.结束，退出程序！"<

cout<<"\n请选择功能,分别输入“1”“2”“3”进行选择："<

cin>>id;

switch(id){

case 1:{

cout<<"错放的棋子个数结果为:\n(以下逐一展示搜索过程：)"<

A(1,start,Target);

break;}

case 2:{

cout<<"每个棋子与其目标位置之间的距离总和为:\n(以下逐一展示搜索过程：)"<

A(2,start,Target);

break;}

default: break;

}

}

cout<<"啊啊….程序结束!!";

}

实验截图

实验中遇到的问题

1：开始程序只能运行一种方式即按照错位个数搜索，后经过查找相关资料，修改后可程序可进行选择，两种方法结合在一起根据选择运行。

实验总结

通过本次实验让我对八数码问题有了进一步的了解，也对一般图搜索和启发式搜索问题的解决有了更深的理解，启发式函数是通过考虑搜索算法的可采纳性，根据定义的评价函数选择最佳路径的一种方法，根据不同的函数可能得到不同的搜索路径，通过这次实验让我对这类游戏行的程序更加有兴趣，也让我的编程更加熟练和编程的思维更清晰了点，从而对学习编程更加有兴趣了。

启发式搜索 八数码问题

启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。

《人工智能基础》实验报告-实验名称：启发式搜索算法

实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解8数码问题 （1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n） 其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。 （2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。 实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路 八数码问题的求解算法 （1）盲目搜索 宽度优先搜索算法、深度优先搜索算法 （2）启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)

实验一 启发式搜索算法

实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰

一、实验内容： 使用启发式搜索算法求解8数码问题。 1、编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个

搜索引擎的排名原理

搜索引擎排名的原理 要了解搜索引擎优化，首先了解搜索引擎的基本工作原理。搜索引擎排名大致上可以分为四个步骤。 爬行和抓取 搜索引擎派出一个能够在网上发现新网页并抓取文件的程序，这个程序通常被称为蜘蛛或机器人。搜索引擎蜘蛛从数据库中已知的网页开始出发，就像正常用户的浏览器一样访问这些网页并抓取文件。 并且搜索引擎蜘蛛会跟踪网页上的链接，访问更多网页，这个过程就叫爬行。当通过链接发现有新的网址时，蜘蛛将把新网址记录入数据库等待抓取。跟踪网页链接是搜索引擎蜘蛛发现新网址的最基本方法，所以反向链接成为搜索引擎优化的最基本因素之一。没有反向链接，搜索引擎连页面都发现不了，就更谈不上排名了。 搜索引擎蜘蛛抓取的页面文件与用户浏览器得到的完全一样，抓取的文件存入数据库。 索引 搜索引擎索引程序把蜘蛛抓取的网页文件分解、分析，并以巨大表格的形式存入数据库，这个过程就是索引。在索引数据库中，网页文字内容，关键词出现的位置、字体、颜色、加粗、斜体等相关信息都有相应记录。 搜索引擎索引数据库存储巨量数据，主流搜索引擎通常都存有几十亿级别的网页。 搜索词处理 用户在搜索引擎界面输入关键词，单击“搜索”按钮后，搜索引擎程序即对输入的搜索词进行处理，如中文特有的分词处理，对关键词词序的分别，去除停止词，判断是否需要启动整合搜索，判断是否有拼写错误或错别字等情况。搜索词的处理必须十分快速。 排序 对搜索词进行处理后，搜索引擎排序程序开始工作，从索引数据库中找出所有包含搜索词的网页，并且根据排名计算法计算出哪些网页应该排在前面，然后按一定格式返回“搜索”页面。 排序过程虽然在一两秒之内就完成返回用户所要的搜索结果，实际上这是一个非常复杂的过程。排名算法需要实时从索引数据库中找出所有相关页面，实时计算相关性，加入过滤算法，其复杂程度是外人无法想象的。搜索引擎是当今规模最大、最复杂的计算系统之一。 但是即使最好的搜素引擎在鉴别网页上也还无法与人相比，这就是为什么网站需要搜索引擎优化。

最佳优先模式--搜索引擎算法分析

最佳优先模式--搜索引擎算法分析 搜索时大部分用户只关注排在最前面的搜索结果。尽管视系统，用户，任务和界面的不同，具体的搜索结果数量也不同，但可以肯定的是前三个搜索结果将吸引你80%的主意力。搜索结果第一页的其他链接也会得到部分关注，但其后的内容则不然。 有两个原因决定了这很重要。首先，搜索的最简单用例就是：浏览有用的搜索结果。用户输入关键词，扫视前面几个搜索结果，点击链接，搜索就完成了。要让搜索简单，快速，有用，最佳优化搜索模式非常重要。其次，最前面的几个搜索结果对于查询重构有着极大的影响。用户输入搜索字词，浏览最初的几个结果，然后再试试搜索其他的内容。大约20%~50%的搜索都包括查询重构。前三个搜索结果是用户界面的重要组成部分。 因此，选择搜索引擎时，应该首先考虑最佳优先模式。高质量，透明，灵活的结果排序算法是成功的关键。他们自始至终都应该是优秀而出色的，能够根据特定内容集而变或是随着应用的独特需求而变。其算法应该包括： 相关性 包括主题的相关性，目的在于将搜索关键字和内容文本元数据匹配起来。有效算法包括词汇排序，相似性，位置，频度和文档长度等。短标题里的精确词汇匹配比起长篇内容里的AND共现匹配要有价值得多。在一个网页上反复出现，但在网站上其他地方却难寻踪迹的词语其权重也更高。相关性算法必须处理好文本查询的特殊情况，包括复数和其他单词变体，比如诗人和诗歌。只有做出调整才能在查准率和查全率之间取得合适的平衡。相关性是典型的搜索引擎默认设置，而且事实上往往也是一种混合模式，把多种算法整合到一个平衡的解决方案中。 流行性 在大多数情境中，社会化数据能够极大地改善语义算法。谷歌的PageRank算法把链接视为投票，这是一个大获成功的做法。如今流行性已经成为典型的多算法度量。在Flickr 上，照片的兴趣度有浏览数，评论数，注释数和收藏次数等决定。在亚马逊网站上，用户按照最畅销或最佳评论来排序。不过，及时用户按照相关性来排序时，社会化数据也影响着搜索结果的显示排序。 日期 默认日期排序并不好，但这一选项也自有用处。尤其是对于新闻和邮件应用来说，按照反向时间顺序（即最新的内容优先显示）相对更加常见。在许多情况下，出版日期或是修改日期可以为通用相关性算法提供有价值的数据，从而改善首选搜索结果的实时性。 格式 在单一形式中，格式和内容类型就像过滤器一样有用，用户可以选择只查看特定格式的内容，比如图片，视频或新闻。而且，他们还可以帮助改善最佳搜索结果。比如，在企业内

启发式搜索算法解决八数码问题(C语言)

1、程序源代码 #include #include struct node{ int a[3][3];//用二维数组存放8数码 int hx;//函数h（x）的值，表示与目标状态的差距 struct node *parent;//指向父结点的指针 struct node *next;//指向链表中下一个结点的指针 }; //------------------hx函数-------------------// int hx(int s[3][3]) {//函数说明：计算s与目标状态的差距值 int i,j; int hx=0; int sg[3][3]={1,2,3,8,0,4,7,6,5}; for(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++; return hx; } //-------------hx函数end----------------------// //-------------extend扩展函数----------------// struct node *extend(node *ex) { //函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值 int i,j,m,n; //循环变量 int t; //临时替换变量 int flag=0; int x[3][3];//临时存放二维数组 struct node *p,*q,*head; head=(node *)malloc(sizeof(node));//head p=head; q=head; head->next=NULL;//初始化 for(i=0;i<3;i++)//找到二维数组中0的位置 { for(j=0;j<3;j++)

几大搜索引擎排名算法趣味解析

几大搜索引擎排名算法趣味解析 做优化最关心的是什么，当然是在几大搜索引擎的排名，几年的淘汰，现在的格局是百度一家独大，然后带领360和新搜狗二个小弟，谷歌中国只剩下不到3%的市场，基本上可以忽略不计，但是谷歌毕竟在全球还是搜索老大，粉丝效应还有一些的用户。 百度：个人觉得百度在排名算法是最人性的，虽然说这个话可能引来好多人的吐槽，因为好多人深受百度其害，认为百度是是难伺候的，算法层出不穷，而且经常所谓的大姨妈，很是伤了好多人的心，但是从我感觉来看，从来没有感受过百度所谓的K站，优化手法也是一直采用正规的白帽手法，几年来优化过的一些站也是得到了自己心仪的排名，为什么说百度最人性呢，最近上了一个新站，到现在差不多刚好一个月的时间，虽然关健词的指数都不高，不过几个关健词已经齐齐的奔入了百度前三页，而且还在稳步的上升中，为什么能这样呢，就是因为百度的新站效应这个人性化的举措，好些优化人士也说，只要你网站按照百度要求搭建，然后内容建设也符合百度规律，那么你网站上线收录不久后百度就会给部份关健词相应的排名，大家都知道优化是一个相当枯燥的事情，能坚持是一件相当困难的事情了，给了甜头，当然有干下去的动力，只要你持续，那后来一定会收到一个比较理想的排名的，但是也有好些人一直所谓的抱怨这，抱怨那，一直没有得到自己想要的排名，这个呢估计得自己找原因了， 360：上线以来，给了人们好大的期望，但是我感觉期望的这部份人应该大部份是来自百度受害者，欺许能在这里得到心灵的安慰，也就出现了一些研究360排名的人，但是至今网上也没有关于这方面的文章，个人感觉360应该没有什么核心算法，搜索结果跟百度也是惊人的雷同，新站基本上不可能在360出现排名，一些老站排名和百度差不多，为什么新站不给排名呢，估计是在等百度排名稳定后再抄袭，这个也就是最近百度频繁推出新算法的的原因，推出新算法一方面是为了提高体验，一方面是打造技术门槛防止被抄袭。 谷歌：在说谷歌之前先上一幅图，这个是这几天在A5上面看到的一篇文章 现在不知道还有多少人是这样的，经常聊天的时候也听到类似的一些观点，认为谷歌怎么怎么的好，谷歌虽然是全球巨头，但是谷歌中文我感觉来是最差的，排版布局上面首先就让人看得难受，我也不知道好多人所说的谷歌好是指的是谷歌中文，还是谷歌英文了，也不知道他们到底是谷歌的用户，还是谷歌的粉丝，还是因为就像以前流行的那样，搜索用谷歌，聊天用MSN等这样的，谷歌中文排名也是我感觉最简单的，那就是一句话外链至上，就是如果你有足够的外链，

启发式搜索算法在N数码问题中的应用

编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月

南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）：

启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法

The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent https://www.sodocs.net/doc/8318660259.html,pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency. This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data. Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm

经典搜索核心算法：BM25算法

相对于TF-IDF 而言，在信息检索和文本挖掘领域，BM25算法则更具理论基础，而且是工程实践中当仁不让的重要基线（Baseline）算法。BM25在20世纪70年代到80年代被提出，到目前为止已经过去二三十年了，但是这个算法依然在很多信息检索的任务中表现优异，是很多工程师首选的算法之一。 今天我就来谈谈BM25算法的历史、算法本身的核心概念以及BM25的一些重要变种，帮助你快速掌握这个信息检索和文本挖掘的利器。 BM25的历史 BM25，有时候全称是Okapi BM25，是由英国一批信息检索领域的计算机科学家开发的排序算法。这里的“BM”是“最佳匹配”（Best Match）的简称。 BM25背后有两位著名的英国计算机科学家。第一位叫斯蒂芬·罗伯逊（Stephen Robertson）。斯蒂芬最早从剑桥大学数学系本科毕业，然后从城市大学（City University）获得硕士学位，之后从伦敦大学学院（University College London）获得博士学位。斯蒂芬从1978年到1998年之间在城市大学任教。1998年到2013年间在微软研究院剑桥实验室工作。我们之前提到过，美国计算机协会ACM 现在每三年颁发一次“杰拉德·索尔顿奖”，用于表彰对信息检索技术有突出贡献的研究人员。2000年这个奖项颁给斯蒂芬，奖励他在理论方面对信息检索的贡献。BM25可谓斯蒂芬一生中最重要的成果。 另外一位重要的计算机科学家就是英国的卡伦·琼斯（Karen Sp?rck Jones）。周一我们在TF-IDF 的文章中讲过。卡伦也是剑桥大学博士毕业，并且毕生致力于信息检索技术的研究。卡伦的最大贡献是发现IDF 以及对TF-IDF 的总结。卡伦在1988年获得了第二届“杰拉德·索尔顿奖”。 BM25算法详解 现代BM25算法是用来计算某一个目标文档（Document）相对于一个查询关键字（Query）的“相关性”（Relevance）的流程。通常情况下，BM25是“非监督学习”排序算法中的一个典型代表。

2016年度--百度最新收录规则和百度搜索引擎排名规则

百度收录规则 第一：百度对关键词的排名。 1、百度进一步提高了自身产品关键字排名的顺序，包括百度百科、百度地图、百度知道、百度贴吧等属于百度自己的产品。还有就是和百度自己合作的网站权重也提高了，因为百度能选择和其他网站合作，也是对他们的网站考察过的。 2、百度排名次序由原来的每星期调整1 次排名，到现在1 天都有可能3-4 次的排名调整; 3、百度对信息比较真实的网站排名会靠前点。公司性质的网站要比个人性 质的网站排名更有优势；对于一些垃圾站点，抄袭网站、模仿网站一律不给于排名。 第二：百度对网站的收录。 1、百度对新站的收录时间简短，从以前的半个月到一个月时间，简短到现 在的一到两周。 2、新的站点，几乎不是多需要去注重外部连接数量及质量了，只需要你尽 量做好站内内容的质量和经常更新即可。 3、百度网页的大更新是以前的星期三更新，更改为星期四更新。 第三：百度对网站的内部链接和内容。 1、网站页面、站点里面有大量JS 代码内容的给于适当降权处理; 2、网站有弹窗广告这样的站点，百度给以降权处理; 3、参与AD 联盟站点的给以适当降权; 4、友情连接过多的站点(10-20 合理)，或者是不雅站点友情链接网站的， 给于降权处理; 5、导出的单向连接过多，给于降权处理;针对黑链及连接买卖的站点 第四：从网站外链权重来分析。 1、博客评论和论坛签名百度现在已经不给予外链权重; 2、对大型门户网站的外链权重有一定的加强，对门户网站的外链权重算法 也做出了调整。

第五：百度排名算法（Rankingalgorithm）是指搜索引擎用来对其索引 中的列表进行评估和排名的规则。排名算法决定哪些结果是与特定查询相关的。 一、从百度枢纽字排名对网站收录方面来看。 1、收录周期缩短，特别是新站，收录已经从以前的一个月缩短到一周左右 的时间。 2、网站收录收录页面有所增加。 3、新站收录几乎不需要有什么外部链接，只要有内容就行了。 4、更新时间：天天更新是7-9 点下站书5-6 点，晚上10-12 点;周三大更新，调整为每周四大更新凌晨 4 点。每月大更新※时间是11 号和26 号，特别是26 号，更新幅度最大，K 站也是最多的。企业站建议懒的话，每周四前更新一下内容，勤快的话，天天更新 3 篇。 二、从百度对枢纽词排名方面看。 1、百度进一步对自己产品枢纽词排名次序加强，百度自己的产品主要有百 度知道、贴吧、百科等。 2、百度赋予了自己合作伙伴很好的枢纽词排名。 3、百度排名次序调整後周期缩短，原来一个星期进行一次排名，现在是一 天三四次的排名顺序(如图：※)调整。例如：百度工控设备维修行业的更新排名 次序变化规律是：排名第一位的变化较少，2-9 位排名位置变化频繁。其中在该 行业中的电路板维修的几十个网站的枢纽词排名进行观察时，发现除了百度排名 第一位的位置之外，其它的排名位置没有一个不乱的。 4、百度对于不同地区、不同城市、不同网络排名位置也有所变化，例如湖 南与广东；长沙与深圳；电信与网通等排名位置都不一样。 5、公司网站排名较之个人网站排名有优先权。这可能是百度对清理网站低 俗内容专项的一种举措，又或者是百度对个人站不放心的缘故所致…! 6、百度认为是垃圾站的排名也不好。由于有个别网站为了省时、省事、省 心，就使用了相同的模板，结果百度调整之后，百度流量就基本上缺失.以至于 有些站基本上就没有什么流量。 7、权重高网站要比权重低的网站好很多。纵观站长网，在这次调整中不但 没有泛起枢纽词排名降低，相反得到了晋升。这可能就是站长日精于勤的缘故吧。 8、百度对搜素引擎的人工干涉与干预进一步加强。如果你的网站关键词排 名很高，而内容简单，无更新.虽然从百度过去的流量很大，如果百度就有可能 通过人工干涉干与，给你网站枢纽词降权甚至百度收录中剔除去。 第六：百度算法调整后新规则： 一、百度加强了站点用户体验提升，对用户体验不好的站点进行了降权。 1、百度把新站收录审核时间变短，出现2-3 天内就可以收录。 (1)未来日期都会出现在收录结果中，百度为了搜索结果更加准确，引用了 文章中出现的日期，不过没有进行当天日期的比较处理。 (2)百度最近一天收录结果不准确。 (3)当天首页快照，网站能有当天的首页快照，当天快照，原来只有谷歌才 有，百度改进算法中在学习谷歌的。 2、百度调整了对站点重复的SPAM 内容站点降权。百度对于网站的原创性要求更高，层次等级很明显的得到了改进。在自己的网站上发表文章，但文章标题

主流搜索引擎算法讲解大全

主流搜索引擎算法讲解大全 １．引言 万维网WWW（World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。1998年WWW上拥有约3.5亿个文档[14]，每天增加约1百万的文档[6]，不到9个月的时间文档总数就会翻一番[14]。WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。 传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观性强，费用高，更新速度慢[2]。 最近几年，许多研究者发现，WWW上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1] ，同年J. Kleinberg提出了HITS算法[5]，其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。 文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。第3部分对这些算法做了评价和总结，指出了存在的问题和改进方向。２．WEB超链分析算法 ２.１Google和PageRank算法 搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page 实现的一个原型系统[2]，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。 ２.１.１PageRank算法 PageRank算法基于下面2个前提： 前提1：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威（Authoritive）网页。

启发式搜索A星算法

启发式搜索——初识A*算法

A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。

深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。

搜索引擎去重算法

搜索引擎去重算法 了解搜索引擎原理的都知道，搜索引擎在创建索引前会对内容进行简单的去重处理。 那么，在动不动就会以亿计出现的网页面前，搜索引擎是如何在短时间内对这些页面进行去重处理的呢？ 其实，说起来也很简单，主要有三步：特征抽取—>文档指纹生成—>相似性计算。比较经典的几个去重算法，如下： 一、Shingling算法 所谓Shingling，即将文档中出现的连续汉字序列作为一个整体，为了方便后续处理，对这个汉字片段进行哈希计算，形成一个数值，每个汉字片段对应的哈希值成为一个Shingle，而文档的特征集合就是有多个Shingle构成的。 举个简单的例子：【搜索引擎在创建索引前会对内容进行简单的去重处理】。既定采用4个汉字组成一个片段，那么这句话就可以被拆分为：搜索引擎、索引擎在、引擎在创、擎在创建、在创建索、创建索引，直到的去重处、去重处理。 则这句话就变成了由20个元素组成的集合A，另外一句话同样可以由此构成一个集合B，将A与B求交得C，将A与B求并得D，则C除以D即为两句话的相似程度。

当然，在实际运用中，搜索引擎从效率计，对此算法进行了优化，新的方式被称之为SuperShingle，据说，此方法效率十分之高，计算一亿五千万个网页，该方法可以在3小时内完成，而按照上述的方法，即便是3千万个网页，也需要10天。 二、SimHash算法 SimHash算法可能是目前最优秀的去重算法之一，Google内部应该采用以SimHash 算法为基础的改进去重方法来对网页进行预处理，而且已对此算法申请了专利保护。 SimHash算法中需要特别注意有文档指纹计算方式以及相似文档查找方式： 1、文档指纹计算方式 首先，从文档内容中抽取一批能代表该文档的特征，并计算出其权值w（这里可以延伸到TF-IDF算法）； 然后，利用一个哈希函数将每个特征映射成固定长度的二进制表示，既定为6比特的二进制向量及其权值，则一篇文章就会变成如下所示“ 100110 w1

搜索引擎的排名原理

搜索引擎的排名原理 要了解搜索引擎优化，首先了解搜索引擎的基本工作原理。搜索引擎排名大致上可以分为四个步骤。 1、爬行和抓取 搜索引擎派出一个能够在网上发现新网页并抓取文件的程序，这个程序通常被称为蜘蛛或机器人。搜索引擎蜘蛛从数据库中已知的网页开始出发，就像正常用户的浏览器一样访问这些网页并抓取文件。 并且搜索引擎蜘蛛会跟踪网页上的链接，访问更多网页，这个过程就叫爬行。当通过链接发现有新的网址时，蜘蛛将把新网址记录入数据库等待抓取。跟踪网页链接是搜索引擎蜘蛛发现新网址的最基本方法，所以反向链接成为搜索引擎优化的最基本因素之一。没有反向链接，搜索引擎连页面都发现不了，就更谈不上排名了。 搜索引擎蜘蛛抓取的页面文件与用户浏览器得到的完全一样，抓取的文件存入数据库。 2、索引 搜索引擎索引程序把蜘蛛抓取的网页文件分解、分析，并以巨大表格的形式存入数据库，这个过程就是索引。在索引数据库中，网页文字内容，关键词出现的位置、字体、颜色、加粗、斜体等相关信息都有相应记录。 搜索引擎索引数据库存储巨量数据，主流搜索引擎通常都存有几十亿级别的网页。 3、搜索词处理 用户在搜索引擎界面输入关键词，单击“搜索”按钮后，搜索引擎程序即对输入的搜索词进行处理，如中文特有的分词处理，对关键词词序的分别，去除停止词，判断是否需要启动整合搜索，判断是否有拼写错误或错别字等情况。搜索词的处理必须十分快速。 4、排序 对搜索词进行处理后，搜索引擎排序程序开始工作，从索引数据库中找出所有包含搜索词的网页，并且根据排名计算法计算出哪些网页应该排在前面，然后按一定格式返回“搜索”页面。

排序过程虽然在一两秒之内就完成返回用户所要的搜索结果，实际上这是一个非常复杂的过程。排名算法需要实时从索引数据库中找出所有相关页面，实时计算相关性，加入过滤算法，其复杂程度是外人无法想象的。搜索引擎是当今规模最大、最复杂的计算系统之一。 但是即使最好的搜素引擎在鉴别网页上也还无法与人相比，这就是为什么网站需要搜索引擎优化。没有SEO的帮助，搜索引擎常常并不能正确返回最相关、最权威、最有用的信息。

百度搜索引擎自然排名算法

百度搜索引擎自然排名算法 搜素动力营销也就成为众多企业的必备营销之道。搜素动力营销的英文是也即是凡是 所说的SEO，从狭义的角度而言，实足以搜索动力为前言发生的行为或勾当从而抵达销售方针的历程都可以称为 搜刮动力营销。SEO追求是高性价比，也等于盼愿能够以最小投入失踪掉最年夜的流量，并为企业带来收益。为您收集这里 搜刮动力的营销形式从广告触发事理上可以分为关头词告白、定向告白，从独霸及投放体例上可以分为SEO 奉行、竞价奉行、品牌专区、上网盟奉行、开放平台等。我们这里所提到的SEO投放功能，是对以上几种告白功效 集团剖析。深山老林网路营销课程总结了影响SEO投放功效有如下几个要素。 一、行业及营业要素 差此外行业和同业业内差此外业务在SEO奉行中暗示出来的功效截然分歧，在举办SEO奉行预估及优化进程 中要考虑这方面的影响。教育行业、汽车行业、金融行业等经常有对照高的奉行功效。 二、网站要素 这是一个最为焦点的要素。网站做为奉行的着陆点，网站的掀开速度、网站内容、及用户体验直接影响转 化，做好网站优化和运营可以提到几倍的功效。可是若是网站杂乱，无法给拜访者供给有价钱的信息，那么SEO 的功效就会大打折扣。在奉行初期，每汲引一个点的转化率，功效将会翻1到2倍。故网站的优化在SEO奉行中最 为严重。 三、投放优化要素 告白在投放后需要活期优化，差此外搜刮动力有差此外投放端方及推广特征，还会触及

到预算解救、用户 定位，季节要素、地域性、素材的创意等各方面。一直去解救告白投放，才会大白哪一种是客户最为喜爱的， 告白投放也才调抵达最优。此外针对有些产物区域客户不同很大的，可以选择在差异地区投放差别情势的告白 投放优化无绝顶，用专业本事去优化投放，可以有用节约资金，汲引功效。良多企业投放告白就长时刻的疏 于打点，告白不绝是一成不乱，这样自然就会形成资金的糜掷了。 四、品牌要素 营销进程中品牌要素的影响可以说是抉择性的。SEO的奉行要按照品牌差此外影响力阶段合理设置投放预算 及投放渠道，从而掉掉最优功效。大品牌曾经组成公信力，轻易完成贩卖转化。小品牌不为人知，即使用户点 击了但因为对产品缺乏信任度仍是大约会走人。 五、搜刮动力要素 差此外搜刮动力市场份额差别，受众属性互异，在SEO奉行中要按照品牌定位、产品及地区特点等，选择符 合的搜刮动力举办投放。百度引擎做为前期试探市场及放量是对照好的选择，谷歌用来定位专业人士及港澳台用户 。要是企业产品是面向高端的客户，那么采纳谷歌睁开SEO无疑是最明智的决议。 六、告白情势要素 企业SEO奉行KPI的要求曾经着重了投放差此外告白情势。垂青品牌揭示的奉行选择网盟产品为宜，垂青功 效的奉行则可以选择竞价奉行。当然在奉行的进程中品牌及功效的奉行只是侧重差别，很少有企业举办双方面 的奉行。

搜索引擎的架构

搜索引擎的架构设计 对李彦宏不陌生吧，他说：搜索引擎不是人人都能做的领域，进入的门槛比较高。所以啰，本文只是通过查阅资料陈述鄙人陋见而已。 当然，对如下截图就更熟悉不过了 怎么李彦宏敢说这么牛的话？你说国内著名搜索引擎公司百度（https://www.sodocs.net/doc/8318660259.html,/）总裁不牛咋个整得成？ 搜索引擎的门槛到底有多高？搜索引擎的门槛主要是技术门槛。对于一个复杂的系统来说，各方面的技术固然重要，但整个系统的架构设计也同样不可忽视 一、搜索引擎架构设计： 搜索引擎架构图： 如图所示，一个搜索引擎通常是由搜索器、分析器、索引器、检索器和用户接口五部分组成：

1．搜索器 通常也可称为蜘蛛(Spider)、机器人(Robot)、爬行者(crawler)或蠕虫(Worm)等，其实质是一种计算机程序，按照某种策略自动地在互联网中搜集和发现we b信息。它要尽可能多、尽可能快地搜集各种类型的新信息，同时由于网上的信息更新很快，需要定期更新已经搜集过的旧信息，以避免死链接和无效链接。目前通常有两种搜集信息的策略： ●顺从一个起始URL集合开始，顺着这些URL中的链接，以宽度优先、深度优先或启发式方式等循环地在互联网中发现新的信息。这些起始URL可以是任意的URL，也可以是一些非常流行、包含很多链接的站点。 ●将Web空间按照域名、IP地址或国家域名划分，每个搜索器负责一个子空间的穷尽搜索。搜索器搜集的信息类型多种多样，包括HTML、XMLL、New sgroup文章、FTP文件、字处理文档以及多媒体信息等。搜索器通常可采用分布式或并行计算技术，以提高信息发现和更新的速度。 搜索器在工作过程中主要需考虑以下几个问题： (1)Web信息的选择。 (2)Web页面的更新频率 (3)减少搜索器对Web服务器的负担 (4)并行工作 2．分析器 分析器即分析程序，功能是理解搜索器所搜索的信息。它通过一些特殊算法，从Spider程序抓回网页源文件中抽取出索引项。同时，分析程序还将此网页中的超链接提取出来，返回给搜索程序，以便Spider进一步深入搜索信息。 3．索引器 索引器将生成从关键词到URL的关系索引表。索引表一般使用某种形式的倒排表（Inversion List），即由索引项查找相应的URL。一个搜索引擎的有效性在很大程序上取决于索引的质量。 4．检索器 检索器的主要功能是根据用户输入的关键词，在索引器形成的倒排表中进行查询，同时完成页面与查询之间的的相关度评价，对将要输出的结果进行排序，并提供某种用户相关性的反馈机制。 5．用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制 二、搜索引擎的实现原理，可以看作四步：从互联网上抓取网页→建立索引数据库 →在索引数据库中搜索→对搜索结果进行处理和排序。而搜索引擎的策略都是采用服务器群集和分布式计算技术，其是面向互联网访问者的。 三、实例——对新闻搜索 “用户”通过提交查询请求给“查询服务器”，服务器在“索引数据库”中进行相关网页的查找，同时“网页评级”把查询请求和链接信息结合起来对搜索结果进行相关度的评价，通过“查询服务器”按照相关度进行排序，并提取关键词的内容摘要，组织最后的页面返回给“用户首先，我们提交要搜索的关键字，其搜索引擎就会经过查询处理与分词（我觉得这里的关键问题就是词法和语义分析），然后由搜索系统程序从网页索引数据库中找到符合该关键

人工智能启发式图搜索算法

启发式图搜索算法 摘要：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。进行搜索技术一般需要某些有关具体问题领域的特性的信息。 关键词：启发式搜索；估价函数；有序搜索；A*算法； 正文： 启发式图搜索的意义因为无信息图搜索算法的效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。所以引入了启发式图搜索算法。 启发式图搜索算法就是进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。关于图搜索的启发式搜索算法就叫做启发式图搜索算法。 启发式图搜索策略：假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。 启发信息按其用途可分为下列3种： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。 (3) 用于决定某些应该从搜索树中抛弃或修剪的节点。 启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。所谓的估价函数就是为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 有序搜索应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索 (best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 有序状态空间搜索算法 (1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。