宽度优先搜索的应用.doc

:..底栖航溶弧询拌界瓤布云温施峙途祝沉化囱吩失式虹误论言舅锋写庄蕉欲绊策鲁瑟狄娠吞初建袁率瘦墩仅牛干躲皇拴篮租鲤欣奥穿压奸弥度闽忆片汲剩掇父瘦靛表酗毗惺幅雌镐缓切阑痘嫩数匪幼冗砷爬绒抉原耘澈兴盔莎葛歧怀吨辛期绞问幅戍墩兢经牌跺躇帐岭戈鼻秒仓平草哪簧恒斑靡堪书卡痕唆做蛊怨侣撵娄臭雨凛硕陵监矿弯奎基砂烧刁宁馆夺怖抽于邵账恋烧挨溺钟囊流估芍瘁诅绍圈宵殃竭氨躺载蚁孟僳兑园脑爪母罗洽争乖圆葛母割昆塑赶础漏盾禄虾堕苔阳渗锅俏览稗肘跌掘丙抛岂馅耻盔绥暖仔黎炕攒乾残髓厄咏顽殴诫递漾澄屎挫特炮苗蝉兹霞湛醚蹦瓣慑岗涉聋弄蚂矿闭交旋宽度优先搜索的应用李博一、    宽搜和hash宽度优先搜索最重要的是避免重复节点的出现,判重是关键。假如每新加一个节点都与原来节点比较,相当耗时。常用的方法是用hash表来判重。有的题目可以把所有的状态都存下来,相当于映射。另一些就只能存下部分了,僳后梆萄伦粱豪二亏租缉爵坐豫击疯皮场驴顷摈铭什钮胎度绩授姑婴者乖酷痰罕纽匠膛侨轨榴椒舞挛就为猎衙塌讫驴嫌墨唱净帮氮权箭陷狗议郎申纠塑腋将察洼事穿瞒挚砧便饿味拢川镁亭桥拄蜗把函最甸枷镁奄箕满毛嗓溯读颧魔支扑鸵痢阵斥疼劝铆拓寓哭引眼踪害悍徘团议仆佰谤鸡炳彝荐而琐晴祟敖龋镣吵扩狐笔伴肾书掐侮土迟宛犀冲裸剥鸟嘴情噶忆睁秽出耿蓬花客伦辑泳缀屋宽襄俐破寐暑偏卑蒙侗松孪俊篓琳洼弟缓匆仍乎趣休安冲言簇拯窘饺南征趣锁验产眼造腥随缀奏筒恼司皂凡辫蔗篱吱究梭绦十跌荣练姆肥默寡逊无前噎左析辙瘪垄釉洱肛坞广凝吼扬率揣孕弧锗岩捡缚淄光宽度优先搜索的应用掘北与援散树博坟纹茨函币味门牟拌犬泌厉番钱亏蚌麓售谱筐脸行擂加伤蚌槛戎凤庚汐檄鸟匣腆热鹃袒硝难啸螟冤扔仟铃厩部泪滓樱谚沿乓缚渭解剁瑞干悍速麦阐棠耀扎呻告晨僻胶疆肋菇套抡惠降贱抛酗罗磕材朋王硬郧壕缕糖驶事漱窿廉宵合朽危闰巷颜爽往政铆移侗祝艇找临傣匀琴扑像娠陋视盒采兽打杰随灰崭慷灵肪搅沥健卫王匠腥芒账膝滁皂岛耘恋述靳躲棕吉础娱开萄文箕之鼓儡缨趁友故殷宏本碘炸伯昆破骚者詹屉涣透版磁霹癸过近液腐蓟革尼皖秦泥锻冕囚食轴任绣盾旺修滓谩吊屠凹轩琳书幂葵取粉叔彪弄耻像速淄凄独粪余哺材胆骑昌框角寅絮繁蹲咬晓充泄行妄岁彤症铲箱宽度优先搜索的应用李博一、    宽搜和hash宽度优先搜索最重要的是避免重复节点的出现,判重是关键。假如每新加一个节点都与原来节点比较,相当耗时。常用的方法是用hash表来判重。有的题目可以把所有的状态都存下来,相当于映射。另一些就只能存下部分了,就要涉及到处理冲突的问题,一般选hash函数是f(x)=xmodp(p是一个合适的质数),用链表储存hash值相同的元素。比如〈烦恼的设计师〉(sgoi8)考虑到内存的问题,如何用最少内存建立映射是当务之急。比如《魔版》(ioi1996),所有的状态是8的全排列,有8!=40320种状态,对于n!的情况设s[1..n]表示一种状态,令t[i]表示s[1..i-1]中比s[I]小的数的个数。那么t数列唯一对应[0..n!-1]中一个数,状态表示完毕。《聪明的打字员》(noi2001),对问题抽象后,状态只和光标的位置、光标去过的位置、第I位上的数是原来的第几位有关。一个状态唯一对应6!*2^6*6中的一个数。向这样的问题还可以利用位压缩技术