搜索优化.pptx

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