算法合集之《搜索顺序的选择》.ppt

搜索顺序的选择福州三中王知昆徒元遗甸邻过啤言粳腔沸姓孝乡卖迄富锤查乍俗峙问柯爸咕击炼妹伙瞧徽算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》例:【间隔排列】问题题意简述:有2N个木块,每个木块标上1到N的自然数中的一个,每个数字会出现在两个木块上。把这些木块排成一排,要求是:标号为i的两个木块之间要间隔i个其它木块。比如说N=3的情况,下面就是一个可行的排列:3,1,2,1,3,2。编程实现,对给定的N(n<=40),求出一个可行排列。本渭幼秘费秦派心墒王晒始阳吴毛禄黄绞施率齿佃斤甩器腐势躁侍痢嘘揣算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》《搜索顺序的选择》算法合集之《搜索顺序的选择》选择搜索顺序的基本原则1、取值范围小的搜索元素先搜索。2、一个搜索元素确定以后对其它搜索元素取值范围的影响称为制约力。制约力较大的搜索元素先搜索。3、先搜索对解影响较大的元素可以使剪枝时的估价函数更准确,使剪枝更加有效。讼娄氟眠网痉倒钾豫痰裳盛育浆铀射限拴沦圃汁俱恩侨揣妊线影焉洞嚷匣算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》例:【算符破译】(NOI2000)题意简述:古梅算符由小写字母a到m组成,分别对应于现代算符中的0,1,2,3,4,5,6,7,8,9,+,*,=中的一个。给出一组古梅算符表示的等式,若存在满足等式的对应关系,则输出所有能够确定的古梅算符和现代算符的对应关系;否则输出‘noway’。惠孪谴到茂盒蝶腰丽绊熏斋窝海谅召僵酪漏氧战避烂膀遣香军帘塘苔斋耶算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》三个最特殊的元素本题中有三个算符最特殊:‘=’、‘*’、‘+’,它们要满足以下条件:1、这三个算符不能出现在等式的最左端和最右端。2、这三个算符两两不能相邻。3、‘=’,这是最特殊的算符,它在任何一个等式中必须出现且仅出现一次。罐顶啪木勃釉臣唐闷梁频鼓史鞋娟诸留犁更己宋筛臭橙煽圃守恰狸烤哪蘸算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》确定搜索顺序从取值范围方面考虑,‘=’,‘+’,‘*’的取值范围在所有算符中是最小的;从制约力方面考虑,‘=’和‘+’,‘*’的制约力无疑都强于‘0’到‘9’这十个数字;从对剪枝有利的角度考虑,这三个算符对解的影响最大,因此‘=’,‘+’,‘*’这三个算符应当放在搜索序列的前面。对于这三个算符,由于‘=’受到的限制更多,取值范围更小,所以应当优先搜索。由此得出的最优搜索顺序:先搜索‘=’,其次是‘+’,‘*’,最后是10个数字。郸创欲芬舶千掐婚镀盲钙娥寂饺啤渭拍矗象培单眯把燎密东遇茬怨孕辱咋算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》减小搜索树规模的具体实现方法1、静态优化搜索顺序例【质数方阵】(IOI94),【修建栅栏】(USACOTRAINING)2、动态调整搜索顺序例【棋盘遍历】,【篮球锦标赛】(BOI98)兰懦庸坠翼颖赞央著赠艳累悸笛祝材橙炽址姆婶恭棒懈阔柒选哥遇佑低火算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》静态优化搜索顺序在一些问题中,搜索元素的制约力和取值范围在搜索过程中变化不大,或变化对搜索效率影响不大。如果要动态判断元素的取值范围和制约力需要花费较大的代价,而且优化效果不好。在这种情况下只需在搜索开始前确定搜索顺序,而不必在搜索过程中再改变搜索顺序。窝承飘秀泪见览壬朋打侣农噶笑君窗瞧枷锌毯火化烁秸妓案旧厩坐汲借缴算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》动态调整搜索顺序有时在搜索过程中元素的取值范围和制约力会有较大的变化,而且这些变化直接影响到搜索树的规模,因此需要动态的调整搜索顺序,也就是启发式搜索。启发式搜索继承了回溯法占用空间少,编程简单的优点,而启发式搜索的最大优点是可以在较短的时间内找到一组可行解,这最适合解决一类只需要求出一组可行解的搜索问题。钱荆鲍鹊讹欺材窥案析嘴席磅念靶沼民窃泳懦须秤溢劫锹珐吧落镜碍褥粪算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》