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

1、检索顺序的选择，福州三中王知昆，例如【间隔排列】问题，题意简单：有2N个木片，每个木片附有1到n的自然数中的一个，每个数字出现在两个木片上。 为了将这些木片排成一列，要求在符号I的2个木片之间隔开I个其他木片。 例如，在N=3的情况下，下面是可执行的列： 3、1、2、1、3、2。 程序设计实现确定对于给定的N(n=40 )的可执行数组。 执行效果比较，选择检索顺序的基本原则，1，先检索值范围小的检索要素。 2 .将一个检索要素确定后其他检索要素对取值范围的影响称为制约力。 先搜索约束力大的搜索元素。 3 .首先探索对解有较大影响的要素，可以使修剪枝叶时的评价函数更正确，使修剪枝叶更有效。 例如

2、【算子解读】(NOI2000 )，题意简单：古梅算子由小写字母a到m组成，分别给出与现代算子中的0、1、2、3、4、5、6、7、8、对应的一组古梅算子所表示的等式，如果有满足等式的对应关系，则能够确定的古梅算子中的组合图层性质变更选项。 三个最特殊的元素，这个问题有三个运算符最特殊。=*、必须满足以下条件： 1、这三个运算符不出现在方程式的左端和右端。 2、这三个运算符不能相邻两个。 3、这是最特殊的算子，每个方程都必须出现，只出现一次。确定搜索顺序，从可取值范围的角度考虑，*的可取值范围是所有运算符中最小的约束力的角度考虑，从有利于0到9的10个数字的强删截的角度考虑，*这3个运算符对解影响

3、最大这三个运算符应当优先搜索，因为它们具有更多的限制并且可能的值的范围较小。 由此得出的最佳搜索次序是首先搜索、接下来是*，最后是10个数字。 减小搜索树规模的具体实现方法有： 1、动态判断静态优化搜索顺序示例【素数正方阵】(IOI94 )、【栅栏建设】(USACO TRAINING )、2、动态调整搜索顺序示例【棋盘扫描】、【篮球锦标赛】要素的取值范围和制约力需要很大成本在这种情况下，只需在开始搜索之前确定搜索顺序即可，而无需在搜索过程中更改搜索顺序。 另外，如果动态地调整搜索顺序，则在搜索中要素能够取得的值的范围和制约力有时会发生较大的变化，由于这些变化直接影响搜索树的规模，因此需要动态地

4、调整搜索顺序、即启发式搜索。 启发式搜索继承了回溯法占有空间小、编程简单的优点，例如【素数方阵】(IOI94 )，题意简单：在一个5*5的方阵中填写数字，沿行，沿列和两个对角线的5个数字为一个5位素数。 所有素数的各位数字之和必须一定。 这个常数和方阵左上角的数字是预先给出的。 存在多个解的情况下，必须得到一切。 中的组合图层性质变更选项。 搜索元素属性，1，最后一行，最后一列：只能输入1、3、7、9的数字。 2.2条对角线：与方阵中所有5位素数有关。 3、其他矩阵：特殊性取决于矩阵中已确定的格子个数。 然后根据元素的可能值范围和约束力确定搜索顺序。 1、最后一行和最后一列是可取值范围最小的检

5、索要素，它们对其他所有要素都有一定的约束力，所以放在检索顺序的开头。2.2条对角线也影响其他所有搜索要素，约束力在剩馀格子中最大，应优先搜索。 3 .剩馀矩阵根据它们取值的范围的大小来确定搜索顺序。 例：【篮球锦标赛】(BOI98 )，题意简单： 5队参加篮球锦标赛。 比赛采用单循环，每两队比赛一次。 知道每个队伍的最终得分、失败次数、总得分和总得分，可以列出所有得分并要求可能的比赛。 (由各队每场比赛的得分组成的战绩表)。 动态调整搜索顺序的根据、搜索要素(即每个场的得分)之间的制约力的大小难以确定。 在本问题中，元素的可能值的范围被定义为在给定的字段中一个团队分数是多个可能的值。 得分取值

6、的范围在搜索中变化很大，而且该变化直接影响搜索树的规模，因此改变搜索顺序的主要依据是各得分取值的范围的大小。 动态判断要素取值范围的方法，首先进行1次前处理，求出所有n次得分的总和等于m的情况(通过存储在散列表中，能够提高检索效率)。 在搜索步骤中，根据已经填写的分数，能够判断剩馀成绩中的哪个不能填写到某个位置。 另外，如果知道I和j的比赛的失败情况和I在这场比赛中得到的分数，那么在这场比赛中j对I的胜分也受到限制。 这使得能够指定各要素可能具有的值的范围。 运行状况比较、搜索顺序和剪枝优化、剪枝优化始终是搜索优化中最重要的一步，但剪枝优化的效果依赖于搜索顺序，只要正确选择对剪枝效果有益的搜索

7、顺序，就能够使剪枝充分发挥作用。 例如，【生日蛋糕】(NOI99 )，题意简单：问题是要求设计m层的蛋糕，蛋糕的体积是n，蛋糕的各层是圆柱，而且各层的高度h和半径r比下一层小。 对于给出的n和m，求出蛋糕的最小可能表面积(最下层的下底面除外)的大小。 搜索顺序对剪枝的影响，因为r和h从下向上减少，体积也从下向上减少，所以选择从下向上的搜索顺序在判断现状是否可能是有利的。 另外，要注意表面积包括各层蛋糕的侧面积和裸露的顶面积。 如果确定了最下层的蛋糕，则确定了每层蛋糕露出的顶面积之和，应该考虑的只是每层蛋糕的侧面积。 因此，这种搜索次序有利于确定是否可能出现比已知最佳解更好的解。 中的组合图层性质变更选项。 在实际的问题解决和应用程序中，搜索问题并非始终优化，但优化的第一步是选择正