HNUSTC语言基础,简单数据结构,acm入门,第一讲,搜索

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,C,语言基础，简单数据结构，,ACM,入门讲座,搜索部分,Bjut,：,mark063,2010.10.30,1,C,语言是什么,for,while,ifelse,switch , case,函数调用,变量，数组，结构体声明,&,*,-,|,&,=,+,+=,输入输出,scanf, printf,freopen(“in.txt”,”r”,stdin);,2,ACM/ICPC,ACM-ICPC,以团队的形式代表各学校参赛，每队由,3,名队员组成。每位队员必须是在校学生，有一定的年龄限制，并且最多可以参加,2,次全球总决赛和,5,次区域选拔赛。,比赛期间，每队使用,1,台电脑需要在,5,个小时内使用,C,、,C+,或,Java,中的一种编写程序解决,7,到,10,个问题。程序完成之后提交裁判运行，运行的结果会判定为正确或错误两种,3,其他比赛,Topcoder,，,Codeforces,平均每周一次，还定期有其他形式的比赛，要求快速准确的构造算法写代码能力,有道难题，百度之星，每年,5,，,6,月份,数学建模，校内赛,4,，,5,月，全国,9,月,4,参考书目,图书馆有关,acm,的书,网上,OJ,5,天津赛区,哈尔滨赛区,6,POJ 2027 No Brainer,Time Limit:,1000MS,Memory Limit:,30000K,Total Submissions:,15196,Accepted:,10314,Description,Zombies love to eat brains. Yum.,Input,The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line X Y, where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive.,Output,For each data set, there will be exactly one line of output. This line will be MMM BRAINS if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be NO BRAINS.,Sample Input,3 4 5 3 3 4 3,Sample Output,NO BRAINS,MMM BRAINS,MMM BRAINS,7,Description,Zombies love to eat brains. Yum.,Input,The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line X Y, where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive.,Output,For each data set, there will be exactly one line of output. This line will be MMM BRAINS if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be NO BRAINS.,8,ACM,题型分类,1,，基本算法,2,，图算法,3,，数据结构,4,，搜索,5,，动态规划,6,，贪心,7,，数学,8,，计算几何,9,，模拟,9,搜索概论,搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。,但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。,本节目标：希望同学们对于任意一个问题，,1.很快建立状态空间,2.提出一个合理算法,3.简单估计时空性能,10,搜索分类,盲目搜索,：,按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。,启发式搜索,：,在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。,11,搜索算法,盲目搜索：,1. 广度优先搜索（Breadth First Search）,2. 深度优先搜索（Depth First Search）,3. 纯随机搜索、重复式搜索、迭代加深搜索、,迭代加宽搜索、柱型搜索,启发式搜索：,1. A*算法,2. IDA*算法,12,DFS&BFS,深,搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。,广搜例子,:,你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方,13,状态空间,明确以下概念：,状态：,问题在某一时刻进展状况的数学描述。,状态转移：,问题从一种状态到另一种或几种状态的操作。,状态空间：,一个“图”，图结点对应于状态，点之间的边对应于状态转移。,搜索：,寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。,14,搜索基础,搜索是常人最容易想到的解题办法，可以说所有题都可以用搜索解决，但是没有剪枝搜索可以看成是穷举法，时间上无法忍受,15,8,皇后问题,给定,8*8,棋盘，要在上边放子，要,求各棋子在同一行，同一列，同,一斜边上不能有两个或两个以上的子，找到所有的放子方法，并输出放子过程与种类数。,16,深搜,：可运行代码在备注中,17,一个从起始状态到达目标状态包含多步操作，而每一步操作又有几种可能，只有正确的操作才能达到目标（如八皇后问题），这样的问题可以看做是一个树。,如果按照,1-2-4-5-3-6-7,的顺序，叫深度优先,(DFS),如果按照,1-2-3-4-5-6-7,的顺序，叫广度优先,(BFS),1,2,3,4,5,6,7,概述,18,void DFS(int k),/,处理第,k,步, if (k=n),/,已经处理到第,n,步，到达目的状态,输出结果,else,/,处理第,k,步,for (int i=1; i=m; i+),/,第,k,步中有,m,种可能,处理第,k,步,DFS(k+1),；,/,进入第,k+1,步,深度优先,(DFS),模板：,19,帮助小明,小明参加一个抢东西的电视节目。这个节目很有意思，一共有,n,个东西可以拿,(n50),每个参加活动的人不能拿重量超过,m(m2000),的东西，而每个东西都有它的价值,v,，有的高有的低，帮助小明安排要拿的东西，使总价值最高。,输入,5 12,3 5,4 6,5 3,8 9,10 8,0 0,样例输出：,15,20,帮助小明,这是一个,0-1,背包问题。,对于每件物品，有两种选择：,1,）拿这件物品（条件是最大重量不超过,m,）,2,）不拿这件物品,下面程序给出,0-1,背包的,dfs,解法，效率无法忍受，但是理解简单。,下一次会介绍,动态规划,的,0-1,背包解法效率会提升很大（备注中给出,0-1,背包动态规划解法）。,21,22,POJ 1088,滑雪,Michael,喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。,Michael,想知道载一个 区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子,1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9,一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为,24-17-16-1,。当然,25-24-23-.-3-2-1,更长。事实上，这是最长的一条。,23,POJ 1088,滑雪,Input,输入的第一行表示区域的行数,R,和列数,C(1 = R,C = 100),。下面是,R,行，每行有,C,个整数，代表高度,h,，,0=h判断是否有值，除以k的余数为零。,计算中间值取余，不影响结果。,(a,+,b) % k = ( a % k,+,b % k) % k,因此只需记录对,k,的余数。,2=k=100,，每层结点最多,100,个，不是指数级增加。,37,4 7,17 5 -21 15,每层最多,7个结点 (定义数组)：,首先加入起点，,17,% 7 = 3,扩展第,2层结点,(3+,5,) % 7 = 1,(3 ,5,+ 7) % 7 =5,1,2,3,4,5,6,0,+,-,扩展第,3层结点,(1+,-21,) % 7 = 1,(1 ,-21,) % 7 = 1,(5+,-21,) % 7 = 5,(5,-21,) % 7 = 5,1,2,3,4,5,6,0,扩展第,4层结点,(1+,15,) % 7 = 2,(1 ,15,) % 7 = 0,(5 +,15,) % 7 = 6,(5,15,) % 7 = 4,1,2,3,4,5,6,0,1,2,3,4,5,6,0,38,例,3 Holedox Moving,一条长度为,L“,贪吃蛇”在,n*m,的迷宫中，求它走到出口（,1,，,1,）的最少步数。,(2L 8;1n,m 20),输入：,5 6 44 14 23 23 132 33 33 4,0 0 0,输出：,Case 1: 9,39,蛇头在上、下、左、右四方向上的探索过程,注意：,蛇不能出界，,不能撞自己，,不能撞石头。,40,例,4：Eight,八数码游戏,Input: 2 3 4 1 5 x 7 6 8,Output: ullddrurdllurdruldr,41,八数码问题的广度优先搜索,42,分析：所给输入为初始状态，终态是,1 2 3 4 5 6 7 8 x。,将x当作9，开一个数组a9！，存每种状态,采取双向BFS，前后搜同时进行。,初始时每种状态标记为0.,在数组,a里查找从前边搜到的状态，标记是0， 则置标记为1；标记是-1，则说明这是个前后搜重合状态，同时说明input有解。,在数组a里查找从后边搜到的状态，标记是0，则置为-1；标记是1，则也说明这是个前后搜重合状态，同时说明input有解。,43,谢谢观看,44,