图搜索问题求解--实验报告

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图的搜索与应用实验题目：图的深度和广度搜索与拓扑排序设计成绩报告成绩指导老师一、实验目的1.掌握图的邻接表的存储形式。

2.熟练掌握图的搜索策略，包括深度优先搜索与广度优先搜索算法。

3.掌握有向图的拓扑排序的方法。

二、实验要求及实验环境实验要求：1.以邻接表的形式存储图。

2.给出图的深度优先搜索算法与广度优先搜索算法。

3.应用搜索算法求出有向图的拓扑排序。

实验环境：寝室+机房+编程软件（NetBeans IDE 6.9.1）。

三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）数据类型定义：template <class T>class Node {//定义边public:int adjvex;//定义顶点所对应的序号Node *next;//指向下一顶点的指针int weight;//边的权重};template <class T>class Vnode {public:T vertex;Node<T> *firstedge;};template <class T>class Algraph {public:Vnode<T> adjlist[Max];int n;int e;int mark[Max];int Indegree[Max];};template<class T>class Function {public://创建有向图邻接表void CreatNalgraph(Algraph<T>*G);//创建无向图邻接表void CreatAlgraph(Algraph<T> *G);//深度优先递归搜索void DFSM(Algraph<T>*G, int i);void DFS(Algraph<T>* G);//广度优先搜索void BFS(Algraph<T>* G);void BFSM(Algraph<T>* G, int i);//有向图的拓扑排序void Topsort(Algraph<T>*G);/得到某个顶点内容所对应的数组序号int Judge(Algraph<T>* G, T name); };主程序流程图：程序开始调用关系：主函数调用五个函数 CreatNalgraph(G)//创建有向图 DFS(G) //深度优先搜索 BFS(G) //广度优先搜索 Topsort(G) //有向图拓扑排序 CreatAlgraph(G) //创建无向图其中 CreatNalgraph(G) 调用Judge(Algraph<T>* G, T name)函数；DFS(G)调用DFSM(Algraph<T>* G , int i)函数；BFS(G) 调用BFSM(Algraph<T>* G, int k)函数；CreatAlgraph(G) 调选择图的类型无向图有向图深 度 优 先 搜 索广度优先搜索 深 度 优 先 搜 索 广度优先搜索拓 扑 排 序程序结束用Judge(Algraph<T>* G, T name)函数。

Project 4（一）实验方法：1. （构造样本库）对每一幅图像利用DoG 算子寻找关键点，每个关键点处构造SIFT 向量，该幅图像的所有关键点的SIFT 矢量构成该图像的特征矢量集。

所有图像的特征矢量集构成样本库特征矢量集；2. （匹配检索）求出需要检索的图像的特征矢量集，用ANN 搜索算法，与样本库特征矢量集进行相似度匹配并输出最相似的前K 张图。

（二）实验算法原理：1. 图像的多尺度表示：利用SIFT 算法提取特征时的尺度不变性，对图像的SIFT 特征构成样本库。

构建尺度空间，在尺度空间内找到稳定的关键点。

尺度空间定义为：(,,)(,,)(,)L x y G x y I x y σσ=*其中222()/221(,,)2x y G x y eσσπσ-+=是尺度可变的高斯函数核。

2. 关键点的构造：为得到关键点，构建高斯差分尺度空间：(,,)[(,,)(,,)](,)(,,)(,,)D x y G x y k G x y I x y L x y k L x y σσσσσ=-*=-检测(,,)D x y σ的局部极值点作为候选关键点。

极值点定义为，检测点和它同尺度的八个相邻点和上下相邻尺度对应的9*2共26个点相比较，若是最小值或者最大值，就认为该点是该尺度下的特征点。

为增强匹配稳定性，提高抗噪声能力，需要剔除不良特征点，即： 1） 低对比度的关键点 2） 不稳定的边缘响应点。

具体剔除方法为：1）对(,,)D x y σ在候选点x 处进行泰勒展开式到二次项：221(x)2T T D DD D x x x x x∂∂=++∂∂ 对其求极值得到212ˆD D x x x -∂∂=-∂∂，计算1ˆˆ()2DD x D x x ∂=+∂，若ˆ|()|0.3D x<则剔除。

2）计算Hessen 矩阵：边缘响应点剔除通过Hessen 矩阵来确定是否剔除：xxxy yx yy D D H D D ⎡⎤=⎢⎥⎣⎦222222(),(),()()()(1)()xx yy xx yy xy Tr H D D Det H D D D Tr H r r Det H r rαβαβαβαβαββ=+=+=-=+++===若该点不满足22()(1)()Tr H r Det H r+<则剔除。

深度优先搜索实验报告引言深度优先搜索（Depth First Search，DFS）是图论中的一种重要算法，主要用于遍历和搜索图的节点。

在实际应用中，DFS被广泛用于解决迷宫问题、图的连通性问题等，具有较高的实用性和性能。

本实验旨在通过实际编程实现深度优先搜索算法，并通过实际案例验证其正确性和效率。

实验中我们将以迷宫问题为例，使用深度优先搜索算法寻找从入口到出口的路径。

实验过程实验准备在开始实验之前，我们需要准备一些必要的工具和数据。

1. 编程环境：我们选择使用Python语言进行编程实验，因其语法简洁而强大的数据处理能力。

2. 迷宫地图：我们需要设计一个迷宫地图，包含迷宫的入口和出口，以及迷宫的各个路径和墙壁。

实验步骤1. 首先，我们需要将迷宫地图转化为计算机可处理的数据结构。

我们选择使用二维数组表示迷宫地图，其中0表示墙壁，1表示路径。

2. 接着，我们将编写深度优先搜索算法的实现。

在DFS函数中，我们将使用递归的方式遍历迷宫地图的所有路径，直到找到出口或者遇到墙壁。

3. 在每次遍历时，我们将记录已经访问过的路径，以防止重复访问。

4. 当找到出口时，我们将输出找到的路径，并计算路径的长度。

实验结果经过实验，我们成功地实现了深度优先搜索算法，并在迷宫地图上进行了测试。

以下是我们的实验结果：迷宫地图：1 1 1 1 11 0 0 0 11 1 1 0 11 0 0 0 11 1 1 1 1最短路径及长度：(1, 1) -> (1, 2) -> (1, 3) -> (1, 4) -> (2, 4) -> (3, 4) -> (4, 4) -> (5, 4)路径长度：7从实验结果可以看出，深度优先搜索算法能够准确地找到从入口到出口的最短路径，并输出了路径的长度。

实验分析我们通过本实验验证了深度优先搜索算法的正确性和有效性。

然而，深度优先搜索算法也存在一些缺点：1. 只能找到路径的一种解，不能确定是否为最优解。

第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。

二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。

4. 动态规划算法：0-1背包问题。

三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2. 查找算法：查找算法用于在数据集中查找特定的元素。

常见的查找算法包括顺序查找和二分查找。

3. 图算法：图算法用于处理图结构的数据。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。

4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。

常见的动态规划算法包括0-1背包问题。

四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。

（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。

（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。

（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。

（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。

（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。

2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。

人工智能第一次实验报告图搜索策略班级：姓名：学号：一、实验目的1. 加深对各种图搜索策略概念的理解；2. 进一步了解启发式搜索、α-β剪枝等概念；3. 比较并分析图搜索策略的实质，通过实验理解启发式搜索的意义。

二、实验要求以九宫问题/八数码问题为例，以某种搜索策略编程演示其搜索过程，最好能采用全局择优搜索，其中的启发式函数自己设计；三、实验算法1.有解和无解如何判定？答：计算两种状态的逆序值，若两者奇偶性相同则可达，不然两个状态不可达。

下面是判断的调用函数：int panduan(struct point x,struct point y)//判断是否有解{int i,j,no=0,a[9],b[9],temp1,temp2,num1=0,num2=0;for(i=0;i<3;i++)for(j=0;j<3;j++){a[no]=x.path[i][j];b[no]=y.path[i][j];no++;}for(i=0;i<9;i++){temp1=0;temp2=0;for(j=i+1;j<9;j++){if(a[j]<a[i]) temp1++;if(b[j]<a[i]) temp2++;}num1+=temp1;num2+=temp2;}if(num1%2==num1%2)return 1;else return 0;}2.启发式函数如何设定？答：比较当前状态和目标状态不同位的个数，数值越小的越接近，因此优先扩展，当为0是表示打到目标：int decide(struct point *x) //h函数&判断函数{int i,j;int no=0; //no是数字不同的个数for(i=0;i<3;i++)for(j=0;j<3;j++) //循环比较if(x->path[i][j]!=end.path[i][j])no++;return no;}3.open表和close表如何实现？答：以结构体存储open表和close表，struct point{int step;//step用于存储相异的元素int path[3][3];struct point *next;}start,end;struct point *open[362880];struct point *closed[362880];4.关键的函数有哪些？①．该函数实现空格的上移：struct point up(struct point *b,int x,int y){point newone=*b;char a;if(x>=0&&x<=2&&y>=0&&y<=2){a=newone.path[x][y];newone.path[x][y]=newone.path[x-1][y];newone.path[x-1][y]=a;}return newone;}②．该函数用于将open表中数据排序：void paixu(){int i,a=optail;struct point *x;for(i=optail;i<ophead;i++)if(open[optail]->step<open[i]->step)a=i;for(i=optail;i<a;i++){x=open[i+1];open[i+1]=open[i];open[i]=x;}}③．Main函数中部分代码，用于实现九宫格的移动：if(num!=0){for(i=0;i<3;i++) //找空格for(j=0;j<3;j++){if(closed[cl]->path[i][j]==0){x=i;y=j;}}point *up=(point *)malloc(sizeof(struct point));//向上 *up=*closed[cl];if(x>0){up->path[x][y]=up->path[x-1][y];up->path[x-1][y]=0;}if(testhash(up)){up->step=decide(up);up->next=closed[cl];open[optail]=up;paixu();optail--;}else free(up);point *down=(point *)malloc(sizeof(struct point));//向下 *down=*closed[cl];if(x<2){down->path[x][y]=down->path[x+1][y];down->path[x+1][y]=0;}if(testhash(down)){down->step=decide(down);down->next=closed[cl];open[optail]=down;paixu();optail--;}else free(down);point *left=(point *)malloc(sizeof(struct point));//向左 *left=*closed[cl];if(y>0){left->path[x][y]=left->path[x][y-1];left->path[x][y-1]=0;}if(testhash(left)){left->step=decide(left);left->next=closed[cl];open[optail]=left;paixu();optail--;}else free(left);point *right=(point *)malloc(sizeof(struct point));//向右 *right=*closed[cl];if(y<2){right->path[x][y]=right->path[x][y+1];right->path[x][y+1]=0;}if(testhash(right)){right->step=decide(right);right->next=closed[cl];open[optail]=right;paixu();optail--;}else free(right);}cl++;}四、实验结果1. 要求有实验运行结果截图，以及必要的说明；输入数据：运行结果：2. 对所采用的策略进行性能分析。

八数码问题（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。

这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。

现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。

该问题称八数码难题或者重排九宫问题。

（二）问题分析八数码问题是个典型的状态图搜索问题。

搜索方式有两种基本的方式，即树式搜索和线式搜索。

搜索策略大体有盲目搜索和启发式搜索两大类。

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

1、启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。

所以引入启发式搜索策略。

启发式搜索就是利用启发性信息进行制导的搜索。

它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。

所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。

即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

启发函数设定。

对于八数码问题，可以利用棋局差距作为一个度量。

搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

（三）数据结构与算法设计该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：struct Chess//棋盘{int cell[N][N];//数码数组int Value;//评估值Direction BelockDirec;//所屏蔽方向struct Chess * Parent;//父节点};int cell[N][N]; 数码数组：记录棋局数码摆放状态。

int Value; 评估值：记录与目标棋局差距的度量值。

Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。

人工智能九宫格重移——搜索1.问题描述：八数码问题也称为九宫问题。

在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。

棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。

棋子移动后，状态就会发生改变。

解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。

所以147258369是无解的情况。

由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。

3.BFS算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找3.1．BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。

对九宫重排问题，即构造广度优先搜索树，从初始状态，利用广度优先搜索算法逐步找到目标状态的节点。

3.2．状态空间表示状态空间用一维数组表示，每个节点存放在Bfstr结构体中的字符now中，从第一行开始从左往右给九宫格标号0……8，字符串now元素下标代表格子位置，而now数组中对应数组的值代表九宫格中存放的数码，用数值9代表空格。