搜索问题
计算机学院2006级师范班程文华
搜索被称为“通用的解题法”，在算法和人工智能方面占有非常重要的低位，特别是在各类ACM程序设计比赛中非常常见，在题目中一般位于中间位置，作为中等难度的题目出现。因此我们需要着重掌握各类的搜索算法，才能面对各类即将到来的ACM大赛。“只要功夫深，铁棒磨成针”，“冰冻三尺，非一日之寒”，要能熟练的掌握和AC比赛中的题目，必须在熟练掌握各类搜索算法的基础上勤加练题，也是唯一的好方法。
本次讲解中，首先给出有关搜索的基本概念，然后针对各类专题，讲解具体的几个例题并加于分析（注：题目全部选自poj中的题目）。
一概念介绍
状态（state）问题在某一时刻的进展情况的数学描述。
算符（operator）/ 状态转移问题从一种状态变换成另一种(或几种)状态的操作。
解答树搜索的过程实际是在遍历一个图，它的结点就是所有的状态，有向边对应于算符，而一个可行解就是一条从起始节点出发到目标状态集中任意一个结点的路径。特个图称为状态空间（state space），这样的搜索称为状态空间搜索（Single-Agent Search），得到的遍历树称为解答数。
基本搜索法：
枚举枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。枚举算法的特点比较单纯，往往容易写出程序，也容易证明算法的正确性和分析算法的时间复杂度，可以解决一些很小的问题。它的缺点是效率特别低，往往很多题目不能用枚举方法，用了只会超时。所以它适应于容易找到状态并且状态较少的题目。没有信心确定其状态较少，请勿立即动手写程序！
深度优先搜索DFS（有时称为回溯法）遵循的搜索策略是尽可能深地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探索到的边，就沿此边继续搜索下去。当结点V的所有边都已被探寻过时，搜索将回溯到发现结点V有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择另一个未发现的结点作为新的源结点重新上面的过程，直至所有的结点都搜索到。
宽度优先搜索 BFS 遵循的搜索策略是从源结点开始，把所有该结点的子结点都搜索完，在搜索每个结点的时候都把其子结点都放入一个队列的后面等待以后搜索，当把此层结点全部搜索完时，所有的下层结点也就进入了队列，继续这样的过程。当仍然没有找到解并且还有没有搜索到的结点时，以没有搜索的结点作为源结点继续上述的搜索过程，直至找到解。
剪枝在搜索的过程中，在还没到达叶结点之前就可以判断以此结点为根的子树不可能包含可行解或者最优解，因此不需要扩展这颗树，就像拿一把剪刀把这颗子树剪去，称为剪枝。
还有一些搜索算法的概念没有给出如分支限界搜索，迭代加深搜索，迭代加宽搜索，A*算法等。他们都各种有适应的范围，也是较为复杂的搜索。
专题1：深度优先搜索DFS
深度优先搜索有很多呈现形式，一般用递归解决，但也可循环等解决，不管用什么实现，其都会遵循深度优先思想。下面是递归实现的程序框架，供初始学习者参考：
Procedure DepthFirstSearch(State:Statetype;depth:integer);
Begin
For Operand:=1 to Operandcount(State) do
Begin
NewState:=DoOperand(State,Operand);
If Answer then
PrintAnswer
Else if depth Search(NewState,depth); End; End; 说明：函数名为DepthFirstSearch。有两个形参State和depth，分别代表初始状态和搜索的层数。for语句从1开始循环所有能用的算符，循环体里意义是:初始状态上作用一种算符得到新的状态，随后就判断此状态是否为问题的解，如果是的话就输出之，不是的话向下递归，以新的状态作为初始状态，层数加1做为新的层数开始新的判断。这个框架只是最简单的，它有很多可以变形。另外，还有一些地方需要注意。 另给出一个C的深搜框架：（引自张邦佐老师的课件） void Backtrack(int t) { if(t>n) Output(x); else for(int i=f(n,t);i<=g(n,t);i++) { x[t]=h[i]; if ((Constraint(t)&& Bound(t)) Backtrack(t+1); } } （1）循环解决的深搜（此题又像枚举） 1166 The Clocks Description There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o'clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90' (degrees) clockwise on those clocks which are affected according to figure 2 below. Input Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. Output Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o'clock. You are convinced that the answer is unique. Sample Input 3 3 0 2 2 2 2 1 2 Sample Output 4 5 8 9 大概题意： 有九个时钟，每个时钟只有4种状态：12：00，3：00，6：00，9：00。分别用0，1，2，3代替。现在有9种操作，如表2所示，每种操作能使对应的钟顺时针旋转90度。现在给出9个时钟的初始状态，问怎么用最少的操作使得这9个时钟都指向12：00。 输入给出9个数字，用1，2，3，4代表每个时钟的初始状态。输出要求给出操作代号，此操作代号按升序排列。 4种状态9种操作 解题思想： 可以观察到这九个时钟都是按顺时针旋转，由于求最少的操作数，我们知道一个时钟如果旋转4次，那么它就回到了初始位置，相当于没有操作，那么上面的4次操作是多余的，不可能成为解，因此可以得出结论，每个操作，如操作1 ABDE 最多只需要操作3次，最少是不操作。那么9个时钟的有4^9种方法，此数字并不是很大，完全可以在有限的1000ms 运行出结果。因此可以用最笨的方法解决。本题如果先不对程序加以分析和解剖，洞察问题的本质和寻找规律，那么将是非常严重的问题，不但效率低，甚至严重超时。 参考代码： #include using namespace std; int temp[9];//存储每一列时钟的状态 int main() { int move[9][9]={ //操作表，对对应有操作为1 {1,1,0,1,1,0,0,0,0}, {1,1,1,0,0,0,0,0,0}, {0,1,1,0,1,1,0,0,0}, {1,0,0,1,0,0,1,0,0}, {0,1,0,1,1,1,0,1,0}, {0,0,1,0,0,1,0,0,1}, {0,0,0,1,1,0,1,1,0}, {0,0,0,0,0,0,1,1,1}, {0,0,0,0,1,1,0,1,1} }; int ways[9]; //各操作的遍数 bool find; int clock[9]; //时钟的初始状态 int i,j; for (i=0;i<9;i++) { cin>>clock[i]; } //下面9层循环遍历了所有可能的出现的情况 for (ways[0]=0;ways[0]<4;ways[0]++) for (ways[1]=0;ways[1]<4;ways[1]++) for (ways[2]=0;ways[2]<4;ways[2]++) for (ways[3]=0;ways[3]<4;ways[3]++) for (ways[4]=0;ways[4]<4;ways[4]++) for (ways[5]=0;ways[5]<4;ways[5]++) for (ways[6]=0;ways[6]<4;ways[6]++) for (ways[7]=0;ways[7]<4;ways[7]++) for (ways[8]=0;ways[8]<4;ways[8]++) { find=true; for (i=0;i<9;i++) //对每个时钟旋转 { temp[i]=clock[i]; for (j=0;j<9;j++) { temp[i]+=ways[j]*move[j][i]; } temp[i]%=4; if(temp[i]!=0) { find=false; break; } } if(find) { for (i=0;i<9;i++) { for (j=0;j { cout< } } cout< return 0; } } return 0; } （2）递归解决的简单搜索 1562 Oil Deposits Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. Input The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket. Output are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets. Sample Input 1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0 Sample Output 1 2 2 大概题意： 有一个GeoSurvComp地质勘探公司正在负责探测地底下的石油块。这个公司在一个时刻调查一个矩形区域，并且创建成一个个的格子用来表示众多正方形块。它然后使用测定设备单个的分析每块区域，决定是否有石油。一块有石油小区域被称为一个pocket，假设两个pocket是相邻的，然后他们就是相同石油块的一部分，石油块可能非常的大并且包涵很多的pocket。你的任务就是在一个网格中存在多少个石油块。输入首先给出图的大小，然后给出这个图。*代表没有石油，@代表存在石油。输出每种情况下石油块的个数。 解题思想： 对于个给出的图，用一个整型的二维数组代表有无石油，然后循环这个二维数组，如发现存在石油，则以这个方格为起始结点进行深搜，如发现石油就标记为-1，然后继续遍历这个二维数组，直至找到下一个有石油的方格，找到一个计数加1。最后的计数即为所求的石油的方块数。 参考代码： ?#include ?using namespace std; ?void seach(int x,int y); ?char oil[100][100]; ?bool visit[100][100]; ?int m,n; ?int go[8][2]={{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};//算符存入一个二维数组里 ?void seach(int x,int y) ?{ ?int i; ?visit[x][y]=true; ?for (i=0;i<8;i++) ?{ ? if((x+go[i][0])>=0&&(x+go[i][0]) ?{ ?seach(x+go[i][0],y+go[i][1]); ?} ?} ?return; ? ?} ?int main() ?{ ?int j; ?while (cin>>m>>n&&(m||n)) ?{ ? ?for (int i=0;i ?{ ?for (j=0;j ?{ ?cin>>oil[i][j]; ?visit[i][j]=false; ?} ?} ?int count=0;//计数值 ?for (i=0;i ?{ ?for (j=0;j ?{ ? if(oil[i][j]=='@'&&!visit[i][j]) ?{ ?seach(i,j); ?count++; ?} ?} ?} ?cout< ?} ?return 0; ?} ? （3）递归解决的带剪枝的深搜 2248 Addition Chains Description An addition chain for n is an integer sequence with the following four properties: ?a0 = 1 ?am = n ?a0 < a1 < a2 < ... < a m-1 < am ?For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable. For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5. Input The input will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n. Output For each test case, print one line containing the required integer sequence. Separate the numbers by one blank. Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space. Sample Input 5 7 12 15 77 Sample Output 1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77 大概题意： 一个整数n的加法链就是一个满足下面性质的序列： ?a0 = 1 ?am = n ?a0 < a1 < a2 < ... < a m-1 < am ?对于每个k (1<=k<=m) 存在两个整数(不一定不同) i 和j (0<=i, j<=k-1) 有ak=ai+aj 你被给定一个n，你的工作是构造一个最短长度的加法链，假设这样的序列超过一个，任何一个合适的序列均可。输入包括很多种测试实例，每个测试实例由一行组成，即就是n，然后输出这个加法链的数字序列。 解题思想： 由于每个数字都是由前面的两个数字之和。并且要使这个数字链最短。那么我们可以深搜一下，假设后面的数是由前面的两个数字的和,前面的两个数是我们可以逐渐往前扫描，那么算符就是前面的两个数相加，得到后面的数，这样深搜下去，并且记录找到解后这个数据链的长度。当数据长度最短时即为所求的解，这里为了加快寻找速度，对于一些不必要搜索的我们不需要去搜索，于是就把它剪去。 参考代码： #include #include using namespace std; int n,page, ans, a[100], r[100], d[202]; void dfs(int); void print(); void init(); int main() { while(scanf("%d", &n) && n) { init(); page=0; dfs(0); print(); } return 0; } void init() { int i; ans = n; a[0] = 1; for(i = n; i <= n + n; i ++) d[i] = 0; for(i = n - 1; i > 0; i --) d[i] = d[i + i] + 1; //d[i]中存放到给定数字的最短的距离数} void print() { int i; for(i = 0; i < ans; i ++) { printf("%d ", r[i]); } printf("%d\n", n); } void dfs(int l) { int i, k; if(l + d[a[l]] >= ans) //剪枝，当搜索到的长度加上从此数到给定的数最短//的距离的值比已搜到的最短的距离还要长时，则不需要深搜下去，直接跳出，继续相邻结//点的搜素 { return; } if(a[l] == n) { ans = l; for(i = 0; i < l; i ++) { r[i] = a[i]; } return; } for(i = l; i >= 0; i --) //此两层循环即为循环所有算符，以找到新的状态 { for(k = i; k >= 0; k --) { a[l + 1] = a[i] + a[k]; //后一个数由前两个个值之和得到 if(a[l + 1] > a[l] && a[l + 1] <= n) //排除不符合的情况 dfs(l + 1); } } } 专题2：宽度优先搜索BFS （1）从结点V开始，给V标上已到达（或访问）标记——此时称结点V还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。 （2）访问邻接于V且尚未被访问的所有结点——这些结点是新的未被访问的结点。将这些结点依次放置到一个未检测结点表（队列Q）中（末端插入）。 （3）标记V已被检测。 （4）若未检测结点表为空，则算法终止；否则从未检查结点表的表头取一结点作为下一个待检测结点。 按照广度优先的顺序遍历状态空间，一般用open，close表来实现。不要用循环队列，因为需要保存已出列的结点。算法框架如下： Procedure BreadthFirstSearch（InitialState:StateType）; Begin Enqueue(InitialState)； While Not EmptyQueue do Begin Dequeue（State）； For Operand：=1 to OperandCount（State） do Begin NewState：=DoOperand（State，Operand）； If Answer（NewState） then PrintAnswer； Else Enqueue（NewState）； End； End； End； 说明：函数名为BreadthFirstSearch，只有一个形参InitialState表示初始状态。函数体内开始是一个进队列函数，把初始状态进队列，然后就是一个循环语句，如果队列不为空则循环，循环体内是首先把队列的头结点取出，然后循环算符，产生此结点的所有后继结点，若出现解，者打印输出，若还没出现解则如队列。 （1）常见求最少步数宽搜 2243 Knight Moves Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy. Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part. Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b. Input The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Output For each test case, print one line saying "To get from xx to yy takes n knight moves.". Sample Input e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6 Sample Output To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves. 大概题意： 一个8行8列的棋谱，任意给出knight的两个位子，问按照knight的走法，从其中的一个位子出发，问至少需要经过几步到达另外一个位子。行用1-8表示，列用a-h表示。输出格式见上。 解题思想： 起始位子作为初始结点进入队列，然后取出第一个结点，把knight能走的位子依次全部进入队列，在进入队列前判断是否为终结点。开辟一个二维数组记录步数。 参考代码： ?#include ?#include ?using namespace std; ?struct point ?{ ?int x,y; ?}; ?int chessboard[8][8];//记录步数 ?vector ?point p; ?bool find; ?int index; ?int start_x,start_y,end_x,end_y; ?void deal(int x,int y,int time) ?{ ?if(x==end_x&&y==end_y) ?{ ?find=true; ?return; ?} ?if(x-2>=0&&y-1>=0&&chessboard[x-2][y-1]==-1) ?{ ?chessboard[x-2][y-1]=time+1; ?p.x=x-2; ?p.y=y-1; ?v.push_back(p); ?} ?if(x-2>=0&&y+1<8&&chessboard[x-2][y+1]==-1) ?{ ?chessboard[x-2][y+1]=time+1; ?p.x=x-2; ?p.y=y+1; ?v.push_back(p); ?} ?if(x+2<8&&y+1<8&&chessboard[x+2][y+1]==-1) ?{ ?chessboard[x+2][y+1]=time+1; ?p.x=x+2; ?p.y=y+1; ?v.push_back(p); ?} ?if(x+2<8&&y-1>=0&&chessboard[x+2][y-1]==-1) ?{ ?chessboard[x+2][y-1]=time+1; ?p.x=x+2; ?p.y=y-1; ?v.push_back(p); ?} ?if(x-1>=0&&y+2<8&&chessboard[x-1][y+2]==-1) ?{ ?chessboard[x-1][y+2]=time+1; ?p.x=x-1; ?p.y=y+2; ?v.push_back(p); ?} ?if(x-1>=0&&y-2>=0&&chessboard[x-1][y-2]==-1) ?{ ?chessboard[x-1][y-2]=time+1; ?p.x=x-1; ?p.y=y-2; ?v.push_back(p); ?} ?if(x+1<8&&y+2<8&&chessboard[x+1][y+2]==-1) ?{ ?chessboard[x+1][y+2]=time+1; ?p.x=x+1; ?p.y=y+2; ?v.push_back(p); ?} ?if(x+1<8&&y-2>=0&&chessboard[x+1][y-2]==-1) ?{ ?chessboard[x+1][y-2]=time+1; ?p.x=x+1; ?p.y=y-2; ?v.push_back(p); ?} ? ?} ?int main() ?{ ? ?char _s,_e; ?int s,e; ?while (cin>>_s>>s>>_e>>e) ?{ ?start_x=(int)(_s-'a'); ?start_y=s-1; ?end_x=(int)(_e-'a'); ?end_y=e-1; ? memset(chessboard,-1,sizeof(chessboard)); ?chessboard[start_x][start_y]=0; ?p.x=start_x; ?p.y=start_y; ?v.clear(); ?v.push_back(p); ?find=false; ?index=0; ?while (!find) ?{ ? deal(v[index].x,v[index].y,chessboard[v[index].x][v [index].y]); ?index++; ?} ?cout<<"To get from "<<_s< knight moves."< ?} ?return 0; } （2）宽搜经典 3278 Catch That Cow Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N(0 ≤ N≤ 100,000) on a number line and the cow is at a point K(0 ≤ K≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. * Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute * Teleporting: FJ can move from any point X to the point 2 ×X in a single minute. If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it? Input Line 1: Two space-separated integers: N and K Output Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow. Sample Input 5 17 Sample Output 4 Hint 实验名称:启发式搜索算法 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) 1、程序源代码 #include 编号 南京航空航天大学毕业论文 题目启发式搜索算法在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.doczj.com/doc/9d16388807.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 实验一启发式搜索算法 学号：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八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个 深度学习模型剪枝的评述 摘要 近年来，深度神经网络在机器视觉和自然语言处理领域都取得了巨大的成功。然而，要将这些模型部署到诸如机器人芯片、智能手机等微型嵌入式设备上仍是一个巨大的挑战。因此，对于这样的平台，模型压缩是一种降低内存消耗和计算复杂度的合理解决方案，目前处理这一问题的技术手段仍然是模型剪枝，而通道级别的模型剪枝又是最有效的手段之一。因此如何有效的实现通道级别的模型剪枝是至关重要的，并且一直是一个具有大量研究成果的主题。 本文阐述了近年来出现的通道级别模型剪枝的主要技术手段，我们主要讨论各个论文的研究成果和遇到的问题，以及根据共同的特点按类别组织的解决方案列表，并且还列出了各个实验结果之间的比较。 关键词：深度学习，模型压缩，通道剪枝 一．引言 在最近这几年中，深度学习赢得了越来越多的关注，并且促进了非常多领域的突破，这依赖于深度神经网络百万甚至千万级别的参数量，和图形处理器的高速计算能力都起着至关重要的作用。 然而，深度学习模型不管在训练还是在部署到设备上时都存在需要问题。比如，[1]在2012年的ImageNet Challenge中取得了突破性的成果，使用了包含6000万个参数的5个卷积层和3个全连接层的网络。通常需要两到三天的时间在NVIDIA K40机器来训练整个模型的ImagetNet数据集。有时在仅依赖于全连接层的架构中，参数的数量可以增长到数十亿[2]。另一方面，卷积运算消耗了大量的计算资源，而这在移动设备上是非常稀缺的，数十亿的网络参数对于嵌入式设备来说也是高存储开销。以VGG-16模型为例，它拥有超过1.38亿个参数，占用超过500MB的内存空间。同时，224×224图像的分类需要300亿次浮点运算(FLOPs)。显然，将如此大的模型直接部署到嵌入式设备中是不切实际的。 因此，在精度没有明显下降的情况下压缩深度模型是一个关键问题。在这种情况下，许多模型压缩方法也相继被提出。最近的一些压缩和加速方法，包括权值剪枝[3-5]、网络量化[6-8]、低秩近似[9,10]、高效模型设计[11-12]。神经元剪枝方法[3]通过去除一些不那么重要的连接，使权值变得稀疏。网络量化针对存储空间压缩问题，提出了一种降低参数表示精度的网络量化[7]算法。低秩近似[9]利用低秩矩阵技术将权值矩阵分解成几个存储空间较小的小矩阵。但是以上方法或多或少存在一些问题，权值剪枝与网络量化需要特殊的软硬件结合使用才能达到好的效果，低秩近似对于1*1的卷积并无效果。而高效模型设计更多关注设计一些不同的网络模型而不是优化已有的卷积运算或者网络架构来压缩加速。 通道剪枝[4,5]是另一种权值剪枝方法，不同于神经元剪枝。与去除单个神经元连接相比，修剪整个通道有两个优点。首先，它不引入原始网络结构的稀疏性，因此不需要对生成的模型进行特殊的软硬件实现。其次，推理阶段不需要庞大的磁盘存储和运行时内存。 本文综述了近年来通道剪枝在深神经网络的压缩和加速研究进展，这些研究引起了深度 AlphaBeta剪枝算法 关于AlphaBeta剪枝的文章太多，这个方法是所有其它搜索方法的基础，得多花些时间认真地理解。 先把基本概念再回顾一遍： 节点：在中国象棋中就是一个棋盘的当前局面Board，当然该轮到谁走棋也是确定的。这里的圆形节点表示终止节点，在中国象棋里就是一方被将死的情况（或者到达了搜索的最大深度），后续不会再有着法产生，游戏如果走到这里就会结束。在引擎里通常给红方一个很大的评估值，如+30000，给黑方一个很小的评估值，如-30000，来方便地判断这种结束局面。（胜利局面有稍微不同的表示法，用-30000+层数ply来表示） 连线：表示一步着法Move，通过这步着法后，局面发生变化，先后手也要交换。 层：通常的术语是ply，复数形式是plies，也有称为levels，当然与depth也是对应的。这个术语是为了与比赛里常说的回合相区分，一个回合通常包含2步，这个ply就表示某一方走了一步。根节点记为0层，以下的层数递增。 深度depth：要注意是从下到上的，还是从上到下的。（1）通常的算法书中都是从下到上递增的，即根节点为最大搜索深度，走到最底部的叶子结点为0，这种算法只要记住一个depth 值就可以了。（2）而另一种记法是根部结点为0，越向下depth增加，这时在搜索时就要传递2个参数值，depth和maxDepth，稍微有点啰嗦，应该也会影响一点效率。另外在探查置换表中的结点时，用第（1）种记法也方便一些，因为要知道从当前节点迭代的深度值，否则还要在置换表中保存depth和maxDepth两个值。 AlphaBeta剪枝方法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。 这种方法的前提假设与Minimax也是一样的： 1）双方都按自己认为的最佳着法行棋。 2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算法描述） 3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。 但要注意：用Negamax风格来描述的AlphaBeta中的评估函数，对轮到谁走棋是敏感的。 也就是说： 在Minimax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋评估值仍是100。 但在Negamax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋时评估值要为-100。 谈搜索算法的剪枝优化 许晋炫 【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧。首先由回溯法解决迷宫问题展开论述，介绍了什么是剪枝；而后分析剪枝的三个原则棗正确、准确、高效，并分别就剪枝的两种思路：可行性剪枝及最优性剪枝，结合例题作进一步的阐述；最后对剪枝优化方法进行了一些总结。 【关键字】搜索、优化、剪枝、时间复杂度 引论 在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。 所以，对程序进行优化，就成为搜索算法编程中最关键的一环。 本文所要讨论的便是搜索算法中优化程序的一种基本方法棗“剪枝”。 什么是剪枝 相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 1、这个方向有路可走，我没走过 2、往这个方向前进 3、是死胡同，往回走，回到上一个路口 4、重复第一步，直到找着出口 这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。 我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？ 答案是：可以的。 剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。 搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。 剪枝的原则 1、正确性 正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也 启发式搜索——初识A*算法 A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。 深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。 ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2005年第45卷第S1期 2005,V o l.45,N o.S15/39 1748-1752 最大频繁项集挖掘中搜索空间的剪枝策略 马志新, 陈晓云, 王 雪, 李龙杰 (兰州大学信息科学与工程学院,兰州730000) 收稿日期:2005-05-20 基金项目:国家自然科学基金资助项目(60473095)作者简介:马志新(1973-),男(汉),甘肃,副教授。 E-mail:mazhx@lz https://www.doczj.com/doc/9d16388807.html, 摘 要:最大频繁项集挖掘可以广泛应用在多种重要的Web 挖掘工作中。为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略。这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝。应用该策略,对M A FI A 算法进行改进优化。实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原M AF IA 算法提高3～5倍。 关键词:W eb 挖掘;最大频繁项集;剪枝策略;搜索空间中图分类号:T P 311文献标识码:A 文章编号:1000-0054(2005)S 1-1748-05 Pruning strategy for mining maximal frequent itemsets MA Zhixin ,CHE N Xiaoyun ,WANG Xue ,LI Lon gjie (School of I nformation Science and Engineering ,Lanzhou University ,Lanzhou 730000,China ) Abstract :M in ing maximal frequent itemsets is a fundamental problem in man y practical w eb m ining ap plications.T his paper presen ts ESEquivPS (exten sion sup por t equivalency pruning strategy),a n ew search space p runing s trategy for mining m axim al frequent itemsets to effectively reduce the s earch s pace.ESE qu ivPS w as based on a depth-first travers al of lexicographic su bset en umer ation tree and uses equivalency of item's ex tension supports to pru ne s earch space.Furthermore,th e M AFIA (m axim al frequen t items et alg or ith m)w as improved by u sing ESEquivPS.T he ex perimental r esu lts show that ES EquivPS can efficiently redu ce the search space.E specially on s pars e dataset w ith longer items ets ,the siz e of search s pace can be trimmed off by 2/3and n ew algorithm runs around three to five times fas ter th an previou s M AFIA algorithm. Key words :w eb m ining; maximal frequent items ets ; pruning strategy;search space 频繁项集挖掘是一类重要的数据挖掘问题,可以广泛应用在客户行为模式分析、网页关联分析、日志分析和网络入侵检测等重要的Web 挖掘工作中。 该问题描述如下:给定事务数据库D ,项目集合I 和用户指定的支持度阈值 ,频繁项集挖掘是在D 中找出支持度大于或等于阈值 的所有项集。 典型的频繁项集挖掘算法是A priori 以及在此基础上的各种改进算法[1],该类算法采用自底向上广度优先的思想,依次计算出所有的频繁1项集,频繁2项集,直到找出所有的频繁项集。当出现大量长的频繁项集时,该类算法代价很高,需要多次扫描数据库并且产生大量的候选项集,对于长度为m 的频繁项集需要枚举出所有可能的2m -2个子集,出现组合问题,导致算法效率低下或无法计算。因此,最大频繁项集挖掘和封闭频繁项集挖掘方法受到该研究领域的重视,先后提出多种重要的最大频繁项集挖掘算法和封闭频繁项集挖掘算法[27]。 如何有效地进行搜索空间剪枝是最大频繁项集挖掘研究工作的一个核心[6]。本文提出了一种新的搜索空间剪枝策略:扩展支持度相等性剪枝策略ESEquivPS (ex tension support equivalency pruning strateg y ),该策略基于词典序子集枚举树,利用树中子节点与父节点的扩展集中相同项的扩展支持度相等的特性,对搜索空间进行削减。该策略可以方便的应用到各种最大频繁项集挖掘算法中,大幅度提高算法的效率。本文结合ESEquivPS 对MA FIA 算法进行了优化改进,并在不同特征的Web 数据集上进行了实验验证。实验结果表明,该剪枝策略可以有效削减搜索空间,改进后的算法效率明显优于原有的MAFIA 算法。 1 最大频繁项集挖掘与搜索空间剪枝策略 最大频繁项集挖掘问题具体描述如下。 启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案， 以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型 下面我们举一个例子——Betsy 的旅行(USACO)。 题目简述：一个正方形的小镇被分成N 2个小方格，Betsy 要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N ，计算出Betsy 能采用的所有的旅行路线的数目。 实际上，由于Betsy 的每一次移动，只会影响到附近的格子，所以每次执行剪枝判断时，应当只对她附近的格子进行检查： 对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy 每次移动到一个新位置，都只会使与之相邻的至多4个格子的标志值发生变化，只要检查它们的标志值即可。 而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对Betsy 附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理： 上图给出了可以剪枝的三种情况。由于Betsy 到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。 一、 优性剪枝 下面举一个应用最优性剪枝的典型例题——最少乘法次数。 题目简述：由x 开始，通过最少的乘法次数得出n x ，其中n 为输入数据。（参见参考书目1） 因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列{}i a ，满足 ???><<=+==)1(),1()1(1i i k j a a i a k j i 要求n a t =，并且使t 最小。 我们选择回溯法作为本程序的主体结构：当搜索到第i 层时，i a 的取值范围 搜索中的剪枝优化 在11+-i a 到2*1-i a 之间，为了尽快接近目标n ，应当从2*1-i a 开始从大到小为i a 取值，当然，选取的数都不能大于n 。当搜索到n 出现时，就得到了一个解，与当前保存的解比较取优。最终搜索结束之后，即得到最终的最优解。 如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化： 优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是i a ，即当前搜索深度为i ）： ????? ?=i a n h 2log 然而，这个估价函数的准确性太差，特别是当i a 大于2 n 时，h 只能等于1，根本不能发挥剪枝的作用。因此，无论是深度优先的回溯法还是宽度优先的A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。 下面，我们再讨论一些进一步的优化手段—— 优化之五：当数列中的当前最大数i a 超过2 n 后，原估价函数就难以发挥作用了。但是，此后的最优方案，实际上就等价于从1a 到i a 这i 个数中，选出尽可能少的数（可重复），使它们的和等于n 。这个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。 二、“最少乘法次数”的估价函数的改进： 最初的估价函数的设计思路实际上是在当前数列i a a ,,1 的基础上理想化的构造i p i i a a a 2,,4,2 ，当i p i p a n a 122+<<时，原估价方法认为只需再进行一次加法，即找一个数与i p a 2相加就够了。 然而，这只是保证了能够得到大于等于n 的数，并不一定恰好得到n 。我们可以作如下分析： 首先，任何一个自然数i 都可以表示成),()12(2___-∈+Z m k m k 的形式，我们可以设)(i k 表示一个自然数i 所对应的k 值。显然，对于任何两个自然数a 和b ，都有()()(){}b k a k b a k ,min ≥+（我们由此可以很容易的联想到“奇+奇=偶，偶+偶=偶，奇+偶=奇”的性质）。 然后，我们再研究前述估价时所构造的数列： i p i i i a a a a a a 2,,4,2,,,,21 （其中，i p i p a n a 122+<<） 在应用新的剪枝判断之前，我们应当先检验()()??p a a n i i ≥+-12/log ，这个条件可以保证只有构造上述数列才是最优的。 若存在自然数()p j j ≤≤1，使得() ()n k a k i j >2，由()()(){}b k a k b a k ,min ≥+， 则有()()()()()p t j n k a k a k a a k i j i t i p i t ≤≤>≥≥+2222 n a a i p i t ≠+∴22 （()()b k a k =是b a =的必要条件） 即i p i j a a 2,,2 中的任何一个数与i p a 2相加都不可能得到n 。 所以，如果i j i p a a n 122->-，则在得到i p a 2后，至少还需要再进行两次加法 人工智能基础实验报告 实验名称：八数码问题 姓名：张俊 学号：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 火力网的搜索优化方案 搜索是万能算法，如果加上剪枝，它将变的更加完美，必要的剪枝可以使程序的效率成几何倍数的增长，所以可以说剪枝是搜索的生命。 问题：火力网（见附录一） 初解：由于最大节点数只有10*10=100个，因此考虑用深度优先搜索解决。在最初的棋盘上对所有的空地放上或拆除碉堡，用类似八皇后问题的回溯法很容易编出程序（见附录二）。但发现到当n>=8时，程序已经不能很快出解了，剪枝势在必行。 剪枝一：改变数据结构，使数据结构为算法服务。 原来用的是二维数组，在搜索时不免因为大量的非空节点（有墙或被控制）使找空节点的效率十分低下。方案：可以将所有的空节点放在一个数组中，记录x,y坐标。 剪枝二：避免重复的搜索，使搜索有序。（下界剪枝） 有时可能出现第I次搜索先选了A格子，后选了B格子，而又在第J次搜索先选了B格子，后选了A格子 为了避免重复的搜索，可以在每次选择一个空地放之后在编号大于它的空地中找下一个可放的位置，这样减去了大量的重复。 剪枝三：对不可能大于Max的进行剪枝。（上界剪枝） 比如现在已经放了n个碉堡，还剩m块空地，若n+m<=Max，那么就不可能大于Max了。 所以，需要对全部未扩展节点+已扩展节点仍不能大于Max的进行剪枝。 ***以上只是对于搜索的最一般剪枝方法，与题目关系不大，以 下是针对题目的剪枝。 剪枝四：对横路径数&竖路径数剪枝。 对于一个题目中的图，如果可以看成由空地组成的路径，就可以计算出有多少个横路径和竖路径。比如 122 3333 44 5555 有5条横路径 156 1356 56 2456 6条竖路径。 把题目中的空地抽象成横路径和竖路径后，由于每条路径最多放一个碉堡。根据抽屉原理，碉堡数不超过横路径数或者竖路径数。如果找到方案可以达到最大，那么就输出结束。（这样比 n*n/2更加优秀）。 实验二：A*算法 一、实验目的 了解启发式搜索算法的基本思想，掌握A*算法的基本原理和步骤。学会对于算法的正确应用，解决实际生活中的问题。学会区分与盲目搜索算法的不同之处。 二、实验环境 PC机一台，VC++6.0 三、实验原理 A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC （Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS 一样，进行启发式的搜索。 A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 A*算法的公式为：f(n)=g(n)+h(n)，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。 对于函数h(n)，估算距离常用的方法有： 曼哈顿距离：定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|。 搜索问题 计算机学院2006级师范班程文华 搜索被称为“通用的解题法”，在算法和人工智能方面占有非常重要的低位，特别是在各类ACM程序设计比赛中非常常见，在题目中一般位于中间位置，作为中等难度的题目出现。因此我们需要着重掌握各类的搜索算法，才能面对各类即将到来的ACM大赛。“只要功夫深，铁棒磨成针”，“冰冻三尺，非一日之寒”，要能熟练的掌握和AC比赛中的题目，必须在熟练掌握各类搜索算法的基础上勤加练题，也是唯一的好方法。 本次讲解中，首先给出有关搜索的基本概念，然后针对各类专题，讲解具体的几个例题并加于分析（注：题目全部选自poj中的题目）。 一概念介绍 状态（state）问题在某一时刻的进展情况的数学描述。 算符（operator）/ 状态转移问题从一种状态变换成另一种(或几种)状态的操作。 解答树搜索的过程实际是在遍历一个图，它的结点就是所有的状态，有向边对应于算符，而一个可行解就是一条从起始节点出发到目标状态集中任意一个结点的路径。特个图称为状态空间（state space），这样的搜索称为状态空间搜索（Single-Agent Search），得到的遍历树称为解答数。 基本搜索法： 枚举枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。枚举算法的特点比较单纯，往往容易写出程序，也容易证明算法的正确性和分析算法的时间复杂度，可以解决一些很小的问题。它的缺点是效率特别低，往往很多题目不能用枚举方法，用了只会超时。所以它适应于容易找到状态并且状态较少的题目。没有信心确定其状态较少，请勿立即动手写程序！ 深度优先搜索DFS（有时称为回溯法）遵循的搜索策略是尽可能深地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探索到的边，就沿此边继续搜索下去。当结点V的所有边都已被探寻过时，搜索将回溯到发现结点V有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择另一个未发现的结点作为新的源结点重新上面的过程，直至所有的结点都搜索到。 人工智能技术报告 启发式搜索 产生背景： 何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 定义： 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径， 可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n) 是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了。 算法举例 启发算法有：蚁群算法，遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。 分析：蚁群算法 蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，指的是一种源于自然现象的算法，也是一种meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。 蚂蚁觅食原理： 自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后， 它们仍然能很快重新找到新的最佳路线。《人工智能基础》实验报告-实验名称：启发式搜索算法
启发式搜索算法解决八数码问题(C语言)
启发式搜索算法在N数码问题中的应用
实验一 启发式搜索算法
剪枝综述
AlphaBeta剪枝算法
谈搜索算法的剪枝优化
启发式搜索A星算法
最大频繁项集挖掘中搜索空间的剪枝策略
启发式优化算法综述
搜索方法中的剪枝优化
(完整版)启发式搜索算法
火力网搜索剪枝
实验二、A＊搜索算法
c语言技巧之搜索剪枝
(启发式搜索)
相关主题
文本预览