搜索优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,Page,#,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,Page,#,搜索及优化,状态：每一时刻的进展；,转移：状态切换的操作；,智能体：,单智能体：目的单一：起始状态-目标状态（1或多）,多智能体：朝不同（对立）状态转移-博弈问题,显式图,隐式图,只有初始状态和变化规则，在搜索的过程中产生出新状态,1.深度优先搜索,1.搜索对象*,2.搜索顺序*,3.状态转移,4.剪枝优化,汽车问题,有一个人在一个公共汽车站上，从,12:00,到,12:59,观察公共汽车到达本站的情况，该站被多条公共汽车线路所公用，他记下了公共汽车到达本站的时刻。,在,12:0012:59,这个期间内，同一条线路上的公共汽车以相同的时间间隔到站。,时间单位用“分”表示，从,0,到,59,。,每条公共汽车线路上的车至少到达本站两次。,在本例的公共汽线路数一定,17,。,来自不同线路的公共汽车可能在同一时刻到达本站。,不同公共汽车线路的车首次到站时间和（或）（,and,or,）时间间隔（到站的）可能相同。如果两条公共汽车线路的车有相同的开始时间和相同的时间间隔，它们必须分开表示出来。,请为公共汽车线路编一个调度表，目标是：公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。对于每一公共汽车线路，输出其起始时刻（第一次到达本站）和到达本站的时间间隔。,输入数据：,输入文件INPUT.TXT首先给出观察者所看到的驶进本站的公共汽车数n（n300），下面以递增顺序给出各公共汽车到达本站的时刻。我们的例子是：,17,0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53,输出数据：,在输出文件OUTPUT.TXT中列一个表，每一行表示一条公共汽车线路。行中第一个数字表示该线路上的公共汽车的首次到达本站的时刻；第二个数字表示该线路上的公共汽车两次到达本站的时间间隔。时间的单位是分。各公共汽车线路在表中出现的先后顺序没有重要性（次序可任意）。若有多个等价解，仅需输出其中一个。我们例子的输出文件的内容为：,0 13,3 12,5 8,题中的对象：,时间，车辆，线路，,时间只起到限定与约束作用（换句话说，为了能做题.）,可以搜索得对象就只有车辆与路线；,想一想：哪个更加有潜力？,思考两种搜索树的形态,车辆：枚举每辆车是否在已有的路线中，如果不存在，则新增一条路线，已有路线越多，即向后枝条越来越密；,路线：需要枚举线路的第一辆车与第二辆车，向后覆盖，可用车越来越少，向后枝条越来越稀；,对于车辆，同样的剪枝可剪掉大片枝叶，而后者只能剪去少部分（剪枝往往在深度达到一定程度后才能发挥作用),对于前者2s可以跑完的数据，后者需要100s时间,方法：,openi以i为开始出发的线路数，每新增一条线路，openi+；,closei以i为开始出发的确定时间间隔的线路数，每多确定一条，close,i+;,对于每个时刻t，从0-t-1扫，如果有openiclosei且在t时刻之后都存在每t-i的间隔就有车进站的情况，closei+,该线路时间间隔为t-i；,并撤掉这些时刻；,若无上述情况，则在该时刻新增一条open的线路，向下搜索；,如果当前解小于最优解，立即返回；,回溯搜索，直到搜完所有结果,程序框架：,Procedure search(t);,begin,求,t,时刻后第一辆车经由本站的时刻,t;,if t,时刻后无车辆到达,then begin,if(,当前线路数,best),且,(,求出每条线路的时间间隔,),then begin,best,当前线路数,;,打印各线路首次到达本站的时间和时间间隔,;,end;then,end then,else begin,在,0.t-1,间,搜索所有,t,时刻经由本站的线路的开始时间,i:,if(i,为未匹配时刻,)and(t,时刻后每隔,t-i,都有汽车到站,),then begin,从,t,时刻开始撤去以,t-i,为间隔的线路,;,确定由,i,时刻出发的第,closedi,线路的时间间隔为,t-i;,closediclosedi+1;,search(t);,递归搜索,t,时刻后经由本站的线路,恢复调用前的,closedi;,由,i,时刻出发的第,closedi,线路的时间间隔恢复为,0;,恢复,t,时刻开始的、以,t-i,为间隔的线路,;,end;,else,if(,当前线路数,+1)best,then begin,线路数,+1;,由,t,出发的未确定时间间隔的线路数,opent+1;,由,t,出发的第,opent,条线路的序号定义为当前线路数,;,在时刻表中撤去,t,时刻,;,search(t);,递归搜索,t,时刻后经由本站的线路,恢复调用前的时刻表、,opent,和线路数,;,end;then,end;else,end;search,搜索顺序,1.可行方案少的优先搜索,2.对后面搜索制约力强的优先搜索,问题简述：,在,9,格宽,9,格高的大九宫格中有,9,个,3,格宽,3,格高的小九宫格（用粗黑色线隔开的）。填入,1,到,9,的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。,定义一个靶形数独的得分为填满数字后,每个格子的数字与这个格子的分值的乘积之和,.,每个格子的分值如图,:,问对于一个数独的初始局面,它的最高得分是多少,.,别误会，讲不了舞蹈链那种高深的东西,想一想朴素的搜索,搜索顺序的优化：,1.一行一行的朴素搜索；,2.从中心开始，向外层搜索(这样我们就可以从最里面贪心,较大的数，较早搜出结果）,想一想,哪个更好？,第一种：75分,第二种：35分,第一种方法枚举：每枚举到一个点，该点会被它上面的点,与左面的点限制，也会被九宫格限制；,第二种方法枚举：只有九宫格的限制较强，其他限制十分微弱，解答树在初始就会极度扩张；,进一步：,如果搜索时将分支少的尽量靠于根部，所得到解答树的宽度将大幅减少；,搜索时每搜一行，将该行每个格中可填数字的个数算出来,选个数最时少的扩展,可行性：显然,最优性：显然,Bestsy的旅行,一个正方形的镇区分为,N,2,个小方块（,1=N=7,）。农场位于方格的左上角，集市位于右下角。贝茜穿过小镇，从左上角走到右下角，刚好经过每个方格一次。,写一个程序，对于给出的,N,值，计算贝茜从农场走到集市有多少种唯一的路径,剪枝1：一个未被经过的点，至少与两个未被经过的点相连；,剪枝2：不能有孤立区域存在，否则1成立也没有,剪枝3：在倒数第二行，第二列的特殊情况,对于剪枝一，设一个标志数组，牛每走一步只有相邻的四个格子变化，判着四个格子即可；,对于剪枝二：,无用扩展：n=8时为30%，n=7时为20%，可谓是剪枝的极限,期望得分：40/70,正解：状压（基于连通性的状压）,2.广度优先搜索,双向广搜,1.初始目标已知；,2.变化规则可逆；,3.可快速判断相遇；,快速查找能否相遇的方法一般有以下几种：,数组下标法（编码）,哈希（散列）法,二分查找法,归并排序法,黑白棋游戏的棋盘由,44,方格阵列构成。棋盘的每一方格中放有,1,枚棋子，共有,8,枚白棋子和,8,枚黑棋子。这,16,枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有,1,条公共边的,2,个方格称为相邻方格。一个方格最多可有,4,个相邻方格。在玩黑白棋游戏时，每一步可将任何,2,个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。,hash判重(二进制数),双向广搜(其实宽搜也可以过。）,例题,1,：,(,最短编号序列,),表,A,和表,B,各含,k(k=20),个元素，元素编号从,1,到,k,。两个表中的每个元素都是由,0,和,1,组成的字符串。（不是空串）字符串的长度,=20,。例如下表的,A,和,B,两个表，每个表都含,3,个元素（,k=3,）。,表,A,元素编号,字符串,1,111,2,10,3,0,元素编号,字符串,1,1,2,10111,3,10,表,B,对于表,A,和表,B,，存在一个元素编号的序列,2113,，分别用表,A,中的字符串和表,B,中的字符串去置换相应的元素编号，可得相同的字符串序列,101111110,，见下表。,具有上述性质的元素编号序列称之为,S(AB),。对于上例,S(AB)=2113,。,编写程序：从文件中读入表,A,和表,B,的各个元素，寻找一个长度最短的元素编号序列,S(AB),。（若找不到长度,=100,的编号序列，则输出,“,No Answer,”,。,元素编号序列,2,1,1,3,用表,A,的字符串替换,10111,1,1,10,用表,B,的字符串替换,10,111,111,0,询问最优解：dfs报废；,从A表开始广搜，怎么判断该状态是否能由B表换过来？,那就A,B一起搜.（其实不a，b一起搜基本没法做了.),保证两个方向扩展结点的速度相对平衡,每次扩展结点数较少的方向,状态可能很多，有必要将所有扩展出来的串都记下来吗？,如果符合条件，我们发现；,用A和B两张表去置换相同的数字序列，得到的ai与bi字符串，要么ai是bi的子串，要么bi是ai的字串,只要记录他们不相同的字符即可,节点信息：,fa：从哪个节点扩展来（要打印）,pos：该节点数字,lena，lenb：A，B串扩展之后的长度；,char lev:记录剩余串,k：记录哪个串剩余字符,按数字序列长度进行广搜,pku 1729：宽搜+HASH+二分,动态搜索顺序选择；,迭代加深，加宽；,各种剪枝深化（尤其是数学剪枝）,A*,IDA*，双向启发搜索；,柱型搜索；,博弈搜索，,搜索与其它算法结合*,