2010搜索算法深入.ppt

《2010搜索算法深入.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索优化南京师大附中王静搜索算法回顾优化的必要性和基本方法总结及拓展讨论线索什么是搜索树、图结构基础上给出初始节点，要求寻找到符合约束条件的目标节点给出初始节点和目标节点，要求找到从初始节点到目标节点的一条路径。最优解？较优解？全部解？搜索的分类深搜宽搜适用范围深搜模型深搜模式特征初始化；循环当前解是合理解是最终解当前解输出；输出后再构造下一个可能解（穷举Y、回溯X）不是最终解构造下一个可能解（扩展X）当前解不是合理解重新构造下一个可能解（穷举Y、回溯X）检查当前解迷宫代码示例----非递归Top:=1;j:=0;Whiletop>0doj:=j+1;x1:=…;y

2、1:=…;ifj>8thentop:=top-1;j:=stick[top];use[stick[top].x,stick[top].y]:=0;elseif(top<=8)anduse[x1,y1]thenstick[top]:=……;use[x1,y1]:=-1;top:=top+1;j:=0;if(x1,y1)=目标thenprint;迷宫代码示例----递归Try(I)Forj:=1to8dox1:=stick[i-1].x+dx[j];y1:=stick[i-1].y+dy[j];ifuse[x1,y1]=0thenstick[i].direction:=

3、j;stick[i].x:=x1;stick[i].y:=y1;use[x1,y1]:=-1;if(x1,y1)<>目标thentry(I+1)elseprint;use[x1,y1]:=0;宽搜框架初始化循环队首f<=队尾r取队首元素；fori=1to可能方案数生成可能解；判重，是新解是最终解，打印不是最终解，入队f++;搜索算法回顾优化的必要性和基本方法总结及拓展讨论线索2.1邮票面值设计给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k<=40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max，使得1－max之间的每一个

4、邮资值都能得到。N=3K=213MAX=7算法基本框架（1）面额为1的邮票是必需的，可以固定。（2）增加一种面额并把当前所能取到的金额记录下来（3）通过k-1次（2）的操作（4）穷举所有的方案得到最优解为什么要优化减少搜索量，提高搜索效率，尽可能快地找到问题的解。竞赛的特点(时间空间限制)优化策略1在搜索的过程中，对数据的记录方式很关键。如果仅仅记录一个金额能否得到，当下一次添加邮票时并不能明确是否能从这个金额出发添加邮票额，所有的金额必须重新计算，浪费了大量的时间。记录最少要用几张邮票达到一个面值是比较重要的，这样有利于添加新邮票时迅速判断可行性。优化策略2当添

5、加一张新邮票时，对邮票面额的搜索可适当缩小范围。直接从上一个面额加1直到当前连续取得的最大金额加1就行了。其他范围内的搜索都是无效的：过大导致不连续；如果小于前一面额的值，就会导致产生面额大小的无序性，造成大量的重复搜索，因此，保证邮票面额递增是基本原则。数据结构设计conti[0..maxs]:记录得到各面额最小需要的邮票数量temp[1..40]：工作数组，记录当前邮票面额设计max1[1..40]：记录采用当前方案能连续取得的最大面额project[1..40]：记录最优解stack[1..40]:栈，用于邮票面额数组temp的维护proceduremaxco

6、nt(top,j:integer);{统计本次方案能得到的最大连续数}fori:=1tondofort:=0tomax2doifcontinue[t+j*i]>continue[t]+ithencontinue[t+j*i]:=continue[t]+i;t:=1;whilecontinue[t]<=ndot:=t+1;ift-1>max2thenbeginmax2:=t-1;if(top=k)and(max2>max)thenbeginmax:=max2;project:=temp;end;end;initread(n,k);fori:=0tomaxsdocon

7、tinue[i]:=n+1;temp[1]:=1;fori:=0tondocontinue[i]:=i;top:=2;max:=n;j:=temp[1];max1[1]:=max;stack[1]:=continue;max2:=0;whiletop>1dobeginj:=j+1;if(j>max1[top-1]+1)or(top>k)then{？}begintop:=top-1;j:=temp[top];continue:=stack[top];max2:=max1[top];endelsebeginstack[top]:=continue;temp[top]