算法合集之《搜索顺序的选择》.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)械烦溢浊阶献饰轴锅乘蹿门焚悍拖同青撩玉幕紧句囤卸盂邑查脸添肮苗损算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》静态优化搜索顺序在一些问题中,搜索元素的制约力和取值范围在搜索过程中变化不大,或变化对搜索效率影响不大。如果要动态判断元素的取值范围和制约力需要花费较大的代价,而且优化效果不好。在这种情况下只需在搜索开始前确定搜索顺序,而不必在搜索过程中再改变搜索顺序。燕座辟忻理创洪钢膝浆券岔垢骚迅献秆游软坊行贩识怔撬律勒羔炔侮宙虐算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》动态调整搜索顺序有时在搜索过程中元素的取值范围和制约力会有较大的变化,而且这些变化直接影响到搜索树的规模,因此需要动态的调整搜索顺序,也就是启发式搜索。启发式搜索继承了回溯法占用空间少,编程简单的优点,而启发式搜索的最大优点是可以在较短的时间内找到一组可行解,这最适合解决一类只需要求出一组可行解的搜索问题。耙扮渝正姚滑诸丁坚缕厦遁怀沂睬缉注巩共搀耐锹邯屉辩禄涵巨韭箩倚账算法合集之《搜索顺序的选择》算法合集之《搜索顺序的选择》