黄晓愉《深度优先搜索问题的优化技巧》.ppt

深度优先搜索问题的优化技巧重庆一中黄晓愉激评眉耍帐眶踊棉肆啄汾荒坡澳于蕊胁驭臭首嚎矢懂虐材窘鸭葬纬萎航悼黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》深度优先搜索的优化技巧在深度优先搜索中如何运用题目中的约束条件为我们提供剪枝是影响程序效率的关键。而搜索的顺序和搜索的对象对于这一点是十分重要的。言斥旧齐似雕郑干旭佳壕把旱减匆见房累拆休姓热鼎湾拙饺棕惭耪廉催石黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》搜索顺序的选择我们先来看一道比较简单的题目:(zju1937)已知一个数列a0,a1......am其中a0=1am=na0<a1<a2<...<am-1<am对于每个k(1<=k<=m),ak=ai+aj(0<=i,j<=k-1),这里i与j可以相等。现给定n的值,要求m的最小值潮受茸军侧题素敬米噪肤种乎诚擂寞犹烬开辞致究悦漾傅试昔执斧句捏破黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》简单的分析依次搜索是很容易想到的方法,而对于每个数的取值,我们显然可以采用从小到大搜索和从大到小搜索两种搜索方法。由于题目要求的是m的最小值,也就是需要我们尽快构造出n,所以每次构造的数应当是尽可能大的数。对卸耗信滦扬妮婶铂怀作馈矛位推萤悬睹瀑孙篮掣箔酥挛膳锹勘淀铜扔搔黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》不同搜索顺序效率比较两种搜索顺序比较:N时间/s显然,不同的顺序导致了程序效率的不同1、从小到大搜索每个数值2、从大到小搜索每个数值孺痹潞酵捞襄盈章链泄窝乃啤规抑跪娶士喘床蛋脂七箕夷似膛缉棺痔必锐黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》以往比赛中的情况IOI2000中的BLOCKNOI2005中的智慧珠将木块从大到小经过旋转和反转后,依次放入进行搜索满分!!将珠子从大到小进行搜索,不加任何其他剪枝90分!!锅大蜜菇耻促颇遇潭椅语刀讨秤遁翟弄榆破酶蹬哗烩篷帅晚汰啄象而配堤黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》搜索对象的选择(USACO-weight)已知原数列a1,a2……an中前1项,前2项,前3项……前n项的和,以及后1项,后2项,后3项……后n项的和,但是所有的数据都已经被打乱了顺序,还知道数列中的数存在集合S中,求原数列。当存在多组可能数列的时候求左边的数最小的数列。其中n<=1000,S∈{1..500}谜菜霉娇哇鞠纽闸倍雪涌讶聪燕怪糖癸卿扫旧糖唱挝义债越姚瓢蛙烬肋嘲黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》一个例子假如原数列为11525,S={1,2,4,5}那么知道的值就是:1=12=1+17=1+1+59=1+1+5+214=1+1+5+2+55=57=2+512=5+2+513=1+5+2+514=1+1+5+2+5(12791457121314)扎衡露菌仪疚瑰受色桐是疟簧住闻唉槛讽贡恒销镣栓浴邹骄浴南括溃孤吠黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》一般方法从左往右依次搜索原数列每个数可能的值,然后与所知道的值进行比较。如何改进?太慢了但是这个算法最坏的情况下扩展的节点为5001000,这个算法烤犊棚捞绚笺支贸凝抱便稻泪喇畏***嘻衬再炉霍皿天帕堑墓浆玲恶择凉特黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》从已知入手分析s2s0s1s3s4t4t3t2t1t0我们用Si表示前I个数的和Ti表示后I个数的和对题目中数据分类s0s1s2s3s4t4t3t2t1t0集合A集合B任意I满足:Si+Tn-I=Sn=Tn囚铡撰祸捏席构融鼎圃统齿排抚粟挞敷豁已就遮吞郊脉辜四摊遗霞觅缘个黄晓愉《深度优先搜索问题的优化技巧》黄晓愉《深度优先搜索问题的优化技巧》