当前位置：文档库 › 实验一,盲目搜索算法

实验一,盲目搜索算法

实验一：盲目搜索算法

一、实验目的

掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。

二、实验环境

PC机一台，VC++6.0

三、实验原理

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。同时，宽度优先搜索算法是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

其基本思想是：

(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。

(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。

(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。

(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回

到n的指针。

(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。

宽度优先搜索示意图和宽度优先算法流程图如下图1和图2所示：

图1、宽度优先搜索示意图

图2、宽度优先算法流程图

四、实验数据及步骤

这部分内容是通过一个实例来对宽度优先算法进行一个演示，分析其思想。问题描述了《迷宫问题》的出路求解办法。

定义一个二维数组：

int maze[5][5] = {

0， 1， 0， 0， 0，

0， 1， 0， 1， 0，

0， 0， 0， 0， 0，

0， 1， 1， 1， 0，

0， 0， 0， 1， 0，

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。题目保证了输入是一定有解的。下面我们队问题进行求解：

对应于题目的输入数组：

0， 1， 0， 0， 0，

0， 1， 0， 1， 0，

0， 0， 0， 0， 0，

0， 1， 1， 1， 0，

0， 0， 0， 1， 0，

我们把节点定义为(y，x)，(y，x)表示数组maze的项maze[x][y]。于是起点就是(0，0)，终点是(4，4)。我们大概梳理一遍：

初始条件：起点Vs为(0，0)，终点Vd为(4，4)，灰色节点集合Q={}，初始化所有节点为白色节点，说明：初始全部都是白色（未访问），即将搜索起点（灰色），已经被搜索过了（黑色）。开始我们的宽度搜索。执行步骤：

1.起始节点Vs变成灰色，加入队列Q，Q={(0，0)}

2.取出队列Q的头一个节点Vn，Vn={0，0}，Q={}

3.把Vn={0，0}染成黑色，取出Vn所有相邻的白色节点{(1，0)}

4.不包含终点(4，4)，染成灰色，加入队列Q，Q={(1，0)}

5.取出队列Q的头一个节点Vn，Vn={1，0}，Q={}

6.把Vn={1，0}染成黑色，取出Vn所有相邻的白色节点{(2，0)}

7.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，0)}

8.取出队列Q的头一个节点Vn，Vn={2，0}，Q={}

9.把Vn={2，0}染成黑色，取出Vn所有相邻的白色节点{(2，1)， (3，0)}

10.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，1)， (3，0)}

11.取出队列Q的头一个节点Vn，Vn={2，1}，Q={(3，0)}

12. 把Vn={2，1}染成黑色，取出Vn所有相邻的白色节点{(2，2)}

13.不包含终点(4，4)，染成灰色，加入队列Q，Q={(3，0)， (2，2)}

14.持续下去，知道Vn的所有相邻的白色节点中包含了(4，4)……

15.此时获得最终答案

我们来看看广度搜索的过程中节点的顺序情况：

图3 迷宫问题的搜索树

图中标号即为我们搜索过程中的顺序，我们观察到，这个搜索顺序是按照上图的层次关系来的，例如节点(0，0)在第1层，节点(1，0)在第2层，节点(2，0)在第3层，节点(2，1)和节点(3，0)在第3层。

我们的搜索顺序就是第一层->第二层->第三层->第N层这样子。

我们假设终点在第N层，因此我们搜索到的路径长度肯定是N，而且这个N一定是所求最短的。

我们用简单的反证法来证明：假设终点在第N层上边出现过，例如第M层，M

所以根据广度优先搜索的话，搜索到终点时，该路径一定是最短的。五、实验核心代码

/**

* 广度优先搜索

void course(char **maze,int hang,int lie)

{

int i=1,j=1,n=-1;

step *Step; //定义一个存储行走路线的栈

Step=new step [hang*lie];

if(maze[1][1]=='1')

{

cout<<"此路无法行走!!!"<

getchar();

exit(0);

}

else

{

n++;

maze[i][j]='.';//.表示入口

Step[n].x=i; //记录入口的坐标

Step[n].y=j;

while(maze[hang][lie]!='.')

{

//'1'表示走不通，'+'表示已经走过但不通又回来的路径，'.'表示已经走过并通了的路径

if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+')//向右走{

maze[i][j+1]='.';

j=j+1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i+1][j]!='1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+') //向下走{

maze[i+1][j]='.';

i=i+1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i][j-1]!='1'&&maze[i][j-1]!='.'&&maze[i][j-1]!='+')//向左走

{

maze[i][j-1]='.';

j=j-1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+')//向上走

{

maze[i-1][j]='.';

i=i-1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i+1][j+1]!='1'&&maze[i+1][j+1]!='.'&&maze[i+1][j+1]!='+')//向右下走

{

maze[i+1][j+1]='.';

j=j+1;

i=i+1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i+1][j-1]!='1'&&maze[i+1][j-1]!='.'&&maze[i+1][j-1]!='+')//向右上走

{

maze[i+1][j-1]='.';

j=j+1;

i=i-1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i-1][j+1]!='1'&&maze[i-1][j+1]!='.'&&maze[i-1][j+1]!='+')//向左下走

{

maze[i-1][j+1]='.';

j=j-1;

i=i+1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else

if(maze[i-1][j-1]!='1'&&maze[i-1][j-1]!='.'&&maze[i-1][j-1]!='+')//向左上走

{

maze[i-1][j-1]='.';

j=j-1;

i=i-1;

n++;

Step[n].x=i;

Step[n].y=j;

cout<<"第"<

"<<"("<

}

else //返回上一步

{

if(i==1&&j==1) //当回到入口时，说明无通路，结束循环

break;

else

{

maze[i][j]='+'; //将走不通的点置为+

n--;

i=Step[n].x;

j=Step[n].y;

cout<<"此路不通!返回至上一步:

"<<"("<

}

if(i==hang&&j==lie)

cout<<"成功走到出口!!!"<<" "<<"共"<

}

outway(maze,hang,lie,i,j);//输出结果}

实验结果如下：

实验图中点的坐标转化为问题描述中的点：

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

六、实验总结

通过本次实验，我掌握了宽度优先搜索算法的思想方法，对于其分析流程有了很清晰的思路，盲目搜索算法中的宽度优先搜索算法应用于实际生活中求解分析问题就有很重要的意义。

禁忌搜索算法浅析

禁忌搜索算法浅析摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索 1禁忌搜索算法概述禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。 TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 2禁忌搜索算法的基本思想禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁

搜索策略实验报告

学生实验报告实验课名称：人工智能实验项目名称：八数码实验专业名称：计算机科学与技术班级： 2012240201 学号： 201224020102 学生姓名：张璐教师姓名：陈亮亮 2014年12 月13 日

实验日期：2014 年12 月9 日实验室名称：明远2202

最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s[3][3]中所处行号，j_0：0在s[3][3]中所处列号)也存储在DATA中。五．源程序： struct array { int id; int depth; int Wx; //错位个数 int moveNum;//计算移动距离 int a[MAX_X][MAX_Y]; int x; //0的横坐标（在数组里的） int y; //0的纵坐标 }; class EightDigital { public: EightDigital(int a[MAX_X][MAX_Y],int b[MAX_X][MAX_Y]); ~EightDigital(); bool safe(int x,int y); //判断与0相邻的位置能否交换，防止数组越界bool compare(); //判断是否到达目标 void search(int x,int y); //搜索目标 void addOpenTable(int x0,int y0,int x1,int y1);//x0,y0是交换前0的坐标，x1,y1是交换后0的坐标,加入open表 void addCloseTable(); //create close table void deleteOpenTable(); void insertSort(); void exchange(int x0,int y0,int x1,int y1); //交换数组值，移动0 int Wx(); //计算错位个数 void print(); //打印数组 bool haveSolution(); int moveNum();

网上搜索的方法和技巧

网上搜索的方法和技巧我们已经知道网上有多种多样的教育资源，从技术上讲，它们是在Internet的多种服务功能的支持下实现的，包含WWW、e-mail、Usenet、FTP、BBS等，其中发展最快，也是最为流行的是WWW。因此我们着重介绍WWW信息的检索方法。据1999年底的统计，网上大约有15亿个网页，并且以每天增加190万个网页的速度在增长，到2002年已达到80亿个网页。要想在这么大的一个资源库中查找一条具体的信息，犹如大海捞针一般。因此，有人发出这样的感叹:"我们淹没在数据资料的的海洋中,却又在忍受着知识的饥渴"。现在出现了许多种在网上查找信息的方法。这些方法可以分为两类:一类是有既定目标的查找，一类是没有目标的查找，而后者往往是指一种网上"冲浪"游戏。在具有既定目标的情况下，如果已有信息线索，可以用浏览器航行的办法寻找信息对象;如果信息线索未定，则需要利用搜索工具首先获得信息线索。搜索工具又有传统工具和现代工具之分。传统工具是在索引数据库中进行主题树/目录检索或KWDSEs(关键词搜索引擎)进行建设而索引库的建设是一个极其繁重的任务，现在已经可以利用"机器人"程序来帮忙，它们通过跟踪最新建立的HTML网页的URL对整个网络进行浏览，可以在网上从这一个网站爬到另一个网站，并记录下它们访问过的网页的各自特征(这种只有十来年历史的搜索技术就被称为传统工具了，你觉得奇怪吗?)。而现代搜索工具是利用智能代理来工作，它们不是对整个网络进行索引，而是在接到一个新任务时就出发，去搜索网上资源并提取有价值的信息。因此，智能代理是利用神经网络技术进行搜索，它试图去发现自然语言与样本网页的模式及它们之间的相互关系，这些将与新近发现的网上资源相匹配，最后以一串网址的形式供用户访问。图2_3_10显示了网上信息检索工具的选择方法。 (一)搜索工具在Internet上现有的检索工具成百上千，比较普及且功能较强的就有几十种。这些检索按照其工作原理的不同，大概可以分为3种类型:

盲目搜索

盲目搜索搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造盲目搜索也叫无信息搜索，只适合用于求解比较简单的问题。我们没有指定问题的任何推理信息，例如要搜索这一部分而不是另一部分，就像到目前为止的只要发现一条到目标的路径即可。这种过程被称为是盲目的。盲目搜索过程只把算子应用到节点，它没有使用问题领域的任何特殊知识（除了关于什么动作是合法的知识外）。最简单的盲目搜索过程就是广度优先搜索。该过程把所有的算子应用到开始节点以产生一个显式的状态空间图，再把所有可能的算子应用到开始节点的所有直接后继，再到后继的后继，等等。搜索过程一律从开始节点向外扩展。由于每一步将所有可能的算子应用到一个节点，因此可把它们组成一个叫后继函数的函数。当把后继函数应用到一个节点时，产生一个节点集，该节点集就是把所有能应用到那个节点的算子应用到该节点而产生的。一个节点的后继函数的每一次应用称为节点的扩展相同代价搜索是广度优先搜索的一种变体，在该方法中，节点从开始节点顺着代价等高点向外扩展，而不是顺着相同深度等高线。如果图中所有弧的代价相同，那么相同代价搜索就和广度优先搜索一致。反过来，相同代价搜索可以看作是下一章要讲的启发式搜索的一个特殊情况。广度优先和相同代价搜索方法的简要描述只给出了它们的主要思想，但是要解决其他复杂的情况则需要技术改进

二分搜索实验报告

竭诚为您提供优质文档/双击可除二分搜索实验报告篇一：算法设计与分析二分查找实验报告课程设计说明书设计题目：二分查找程序的实现专业：班级：设计人：山东科技大学年月日课程设计任务书学院：信息科学与工程学院专业：班级：姓名：一、课程设计题目：二分查找程序的实现二、课程设计主要参考资料（1）计算机算法设计与分析（第三版）王晓东著（2）三、课程设计应解决的主要问题（1）二分查找程序的实现（2）（3）四、课程设计相关附件（如：图纸、软件等）：（1）（2）五、任务发出日期：20XX-11-21课程设计完成日期：

20XX-11-24 指导教师签字：系主任签字：指导教师对课程设计的评语成绩：指导教师签字：年月日二分查找程序的实现一、设计目的算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。二、设计要求给定已按升序排好序的n个元素a[0:n-1]，现要在这n 个元素中找出一特定元素x。实现二分搜索的递归程序并进行跟踪分析其执行过程。用顺序搜索方法时，逐个比较a[0:n-1]中的元素，直至找出元素x，或搜索遍整个数组后确定x不在其中。这个方

法没有很好的利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要o(n)次比较。要求二分法的时间复杂度小于o(n)。三、设计说明（一）、需求分析二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用o(logn)时间完成搜索任务。该算法的流程图如下：（二）、概要设计二分查(:二分搜索实验报告)找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果 x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。由于二分查找的数组不一定是一个整数数组，所以我采用了c++中的模板函数，将排序函数sort和二分查找函数binarysort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。由于查找的数组的长度不固定，所以我用了c语言中的malloc和realloc函数，首先定义一个数组指针，用malloc 函数该它分配空间，然后向数组中存数，当数组空间满时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以篇二：二分搜索实验报告

搜索引擎的使用方法和技巧

百度搜索引擎的使用方法和技巧学生姓名：学院：信息技术学院专业：信管(电) 班级：学号：指导教师：完成日期： 2015年3月28日辽东学院 Eastern Liaoning University

一、简单搜索 1. 关键词搜索只要在搜索框中输入关键词，并按一下“搜索”，百度就会自动找出相关的网站和资料。百度会寻找所有符合您全部查询条件的资料，并把最相关的网站或资料排在前列。小技巧：输入关键词后，直接按键盘上的回车键（即Enter健），百度也会自动找出相关的网站或资料。关键词，就是您输入搜索框中的文字，也就是您命令百度寻找的东西。可以是任何中文、英文、数字，或中文英文数字的混合体。可以命令百度寻找任何内容，所以关键词的内容可以是：人名、网站、新闻、小说、软件、游戏、星座、工作、购物、论文、、、例如：可以搜索[windows]、[918]、[F-1赛车]。可以输入一个关键词，也可以输入两个、三个、四个，您甚至可以输入一句话。例如：可以搜索[博客]、[原创爱情文学]、[知音，不需多言，要用心去交流；友谊，不能言表，要用心去品尝。悠悠将用真诚，尊敬和大家来建立真正的友谊]。注意：多个关键词之间必须留一个空格。 2. 准确的关键词百度搜索引擎严谨认真，要求一字不差。例如：分别输入 [舒淇] 和 [舒琪] ，搜索结果是不同的。分别输入 [电脑] 和 [计算机] ，搜索结果也是不同的。因此，如果您对搜索结果不满意，建议检查输入文字有无错误，并换用不同的关键词搜索。 3. 输入两个关键词搜索输入多个关键词搜索，可以获得更精确更丰富的搜索结果。例如，搜索[悠悠情未老]，可以找到几千篇资料。而搜索[悠悠情未老]，则只有严格含有“悠悠情未老”连续5个字的网页才能被找出来，不但找到的资料只有几十篇，资料的准确性也比前者差得多。因此，当你要查的关键词较为长时，建议将它拆成几个关键词来搜索，词与词之间用空格隔开。多数情况下，输入两个关键词搜索，就已经有很好的搜索结果。 4. 减除无关资料有时候，排除含有某些词语的资料有利于缩小查询范围。百度支持“-“功能，用于有目的地删除某些无关网页，但减号之前必须留一空格，语法是“A -B”。

搜索引擎-第二次实验报告

实验二：实验一、实验目的：根据网络爬虫的基本原理，实现一个简易网络爬虫，需要达到以下指标： 1、种子URL为https://www.wendangku.net/doc/4811452392.html,； 2、至少抓取10000个页面； 3、至少完成3轮抓取，每轮给出更新的URL及其数量； 4、实现ＵＲＬ判重，列出每轮爬去时重复的URL数量； 5、数据存放到数据库中，能抽取出网页中的标题、页面生成日期（http协议中的时间），至少包含标题、时间、url、抓取时间、网页正文这几个字段。二、实验方案： 1.爬虫分析与设计我们组应用的是java来写爬虫，我们应用SSM框架将数据库和应用程序连接起来，可以在程序中更简单的进行数据库插入、查询等操作。在对url处理的时候我们用的是Java的URL类，通过这个类可以获得请求头的一些信息，例如编码方式。如何获取url，我们一开始遇到了一些问题，直接解析网页中的ref 标签的时候得到的不全是网页链接，所以转换思路，我们先得到页面中的标签，然后再得到标签里边href中的url，然后再对url进行处理。在处理url的时候，因为网页中的url并不是全部以http开头的，所以在url获取部分，对url的格式进行判断，如果通常格式就进行修改，例如，有的链接是”#”，我们就把开始搜索的url加到它的前边，形成一个正确的url。

图1：应用URL类获取网页内容图2：利用url请求头获取编码信息图3：获取a标签

图4-1：获取url 图4-2：获取url

图5：url判重 2.数据库分析与设计我们设计了两个表，一个是未爬取url表，两一个是已经爬取url表。未爬取的表中村的是搜索判重之后，还没有爬取的url，已爬取的存储爬取到的信息。图6：判重后需要爬取的url表图7：爬取后url信息存储表