资源描述：
《人工智能 acm-搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、搜索技术包含的内容回溯法回溯+剪枝法广度搜索双向广度优先搜索A，A*算法渐进深度优先算法爬山法分支限界法遗传算法与或图与博弈树模拟退火法1.回溯法回溯法概念回溯法也称试探法.它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。回溯策略回溯搜索的示意1AB28C11DE3F69G10HI4J57K状态空间中回溯搜索图中虚线箭头的方向表明了搜索的轨迹，结点边的数
2、字表明了被搜索到的次序回溯法分析采用递归，算法简单，时间复杂度比较大采用迭代法，算法设计与题目相关度大，时间复杂度较小。递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：ProcSearch(当前状态);beginIf当前状态等于目标状态thenexit;for对所有可能的新状态Search(新状态)；endProcedureBACKTRACK(n)；{k:=l；repeatifTK(x1,x2,...xK-1)中的值未取遍then{xK:＝TK(x1，x2，...,xK-1)中未取过的一个值；ifBK(x1,x2,...,xK)then//状态结点
3、(x1,...xk)被激活ifk＝nthenoutput(x1,x2,...,xk)//输出一个回答结点e1sek:＝k+l；}//深度优先e1sek:＝k-l；//回溯untilk＝0；end；{BACKTRACK}本课件题库网站http://acm.sdut.edu.cn/judgeonline/problemlist1400题马的走法在一个4*5的棋盘上，马的起始位置坐标（纵、横）位置由键盘输入，求马能返回初始位置的所有不同走法的总数。（马的位置不能重复，马走“日”字。）SampleinputOutputfortheinput224596Input输入数据只有一行，有两个用空格分开的整
4、数，表示马所在的初始位置坐标。首行首列位置编号为（11）。Output输出一行，只有一个整数，表示马能返回初始位置的所有不同走法的总数。 如果输入的马的初始位置超出棋盘边界，则输出ERROR。马的走法分析（1）由于4*5问题规模小，采用基于递归的回溯法问题定义：（1）采用二维数组表示棋盘。（2）马走步表示方法二维数组，{{-1，-2}，{-1，2}，{-2，1}，{-2，-1}，{1，2}，{1，-2}，{2，1}，{2，-1}}，8个方向。（3）棋盘的最小坐标，左下角为（1，1）（4）棋盘越界条件0≤x≤4,0≤y≤5（5）走过的棋盘位置应该设置一个标示。马的走法分析（3）递归的回溯算法可
5、描述为：proceduresearch(now:position);{now是当前位置}beginfor马从当前位置now出发走一步到位置next的每一种走法dobeginifnext在棋盘内andnext位置没有走过thenifnext=出发点then不同走法总数加1elsebegin标记next已经走过了;search(next)取消位置next的标记;end;end;end;#include using namespace std; constintROWS = 4;//行数constintCOLUMS = 5;//列数intchess[ROWS][COLUMS]
6、;//棋盘intnumCount= 0;intposX,posY;intdirection[2][8]={{-1,-1,-2,-2,2,2,1,1},{-2,2,1,-1,1,-1,2,-2}};//马走"日"字voidSolve(intx,inty) {inti,j,desX,desY; for (i=0;i<8;++i) {desX= x+direction[0][i];//目标位置x坐标desY= y+direction[1][i];//目标位置y坐标if (desX>=0&&desX<4&&desY>=0&&desY<5&&chess[desX][desY]==0)
7、 {//满足规则，走到目标处，并继续搜索chess[desX][desY] = 1;Solve(desX,desY);chess[desX][desY] = 0; } else if (desX==posX&&desY==posY) {//回到了起点numCount++; } } }intmain() {cin>>posX>
