搜索
基础算法策略长沙市第一中学曹利国第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举策略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法枚举算法的应用例题1：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。枚举算法的应用例题2：01统计例题4：圆桌骑士（IOI试题）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举算法的应用【分析】此题可从3个方面考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。枚举算法的应用国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。这样我们估算一下时间为O（8*8*8*8*63）=O（36*10^4），完全可以承受。另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。枚举算法的应用算法流程：dis[x1，y1，x2，y2]--（x1，y1）（x2，y2）之间的距离。ForI：=1to8do{枚举汇合点}Forj：=1to8dobeginAll：=所有骑士到这一点的和；Best:=min(best,all+国王到汇聚点的步数)Forx：=1to8do{枚举武士国王的相会点}Fory：=1to8dobeginForkk：=1tokdo{枚举与国王结合的武士}Ifdis[knight[kk].x,knight[kk].y,x,y]minthenbeginMin:=dis[knight[kk].x,knight[kk].y,x,y];Mink:=k;End;End；Now:=all-mink武士走到汇合点的距离+mink武士走到汇聚点的距离+国王走到汇聚点的距离+从汇聚点到汇合点的距离；Best：=min（best，now）End；局部枚举例题5：求第一、第二、第三最短路问题局部枚举例题6：新年好重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？分析这一题中的边数远小于n2，所以复杂度也只有nlogn+m算法框架是：（1）用5次最短路，计算出6个点两两之间的距离（2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。最大子矩阵的求解方法第二部分贪心方法贪心方法的基本思想贪心是一种解题策略，也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解适用于贪心策略求解的问题的特点适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）贪心方法的应用例题1：节点网络。现有一个N！个节点的网络，每个节点的编号都是编号（A1A2A3…AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3…AN）所需经过的最少边数。其中，n≤100。贪心方法的应用例如n=3的情况：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)贪心方法的应用【分析】从题意表面上看，本题是一个求最短路径的问题，但题设中的N≤100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。贪心方法的应用采用贪心策略：每次让一个节点归位或为下一步工作做准备。其具体步骤为：若序列中第一个点为Ax(x≠1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。贪心方法的应用(A3A4A1A2)(A1A4A3A2)第一个点A1已归位，但第二个点为A4≠A2，将第2个点A4与A1交换第一个点为A3≠A1，将第3个点A1与A3交换(A4A1A3A2)第一个点为A4≠A1，将第4个点A2与A4交换(A2A1A3A4)第一个点为A2≠A1，将第2个点A1与A2交换(A1A2A3A4)已经符合要求了一共经过4步完成。下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：贪心方法的应用例题2：d-规则问题。对任意给定的m(m∈N+)和n(n∈N+)，满足mn，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)现定义一种d规则如下：若存在a∈P，且存在K∈N+,K1，使得Ka∈P，则修改P为：P=P-{y|y=sa,s∈N+}，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。贪心方法的应用【分析】初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P＝{3,…,10}，运用上述“贪心标准”可以得到这一问题的正确的最优解d=5＋4＋3＝12，即其d-规则过程如下：1.a=5P={3,4,6,7,8,9}d=52.a=4P={3,6,7,9}d=5+4=93.a=3p={7}d=5+4+3=12贪心方法的应用但是，如果再仔细地分析一个例子，当m=3，n＝18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d＝38，其对应的d-规则序列为（9,8,7,6,3,5）。为什么会出现这样的反例呢？这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。因此，本题不能采用纯粹的贪心策略求解。贪心方法的应用【改进】将原算法基础上进行改进。下面给出新的算法：1.建立集合P={m..n}2.从ndiv2到m每数构造一个集合c[i]，包含该数在P中的所有倍数（不包括i本身）3.从ndiv2起找到第一个元素个数最少但又不为空的集合c[i]4.在d分值中加上i5.把i及c[i]集合从P集中删除，更新所有构造集合的元素6.检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束贪心方法的应用下面看m=3,n=18时的推演过程：1.初始P={3..18}2.找到i=9,c[i]={18},P={3..8,10..17}3.找到i=8,c[i]={16},P={3..7,10..15,17}4.找到i=7,c[i]={14},P={3..6,10..13,15,17}5.找到i=6,c[i]={12},P={3..5,10,11,13,15,17}6.找到i=3,c[i]={15},P={4,5,10,11,13,17}7.找到i=5,c[i]={10},P={4,11,13,17}到此所有构造集合全部为空，d=9+8+7+6+3+5=38贪心方法的应用讨论：能否证明此贪心策略是正确的？能否找到其他更好的算法？贪心方法的应用例题3：射击竞赛射击的目标是一个由RC(2≤R≤C≤1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1~R，列从左至右编号为1~C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。贪心方法的应用射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。贪心方法的应用【方法一】网络流算法我们将表示列的点编号为1到C，表示行的点编号为C+1到C+R，如果一个白色方格处在第i行第j列，那么从点j向点C+i连一条弧，弧的容量为1。再增设一个源点S，从点S往点1到C间各连一条弧，弧的容量为1，又设一个汇点T，从点C+1到点C+R向汇点T连一条弧，弧的容量为1，那么从源点S到汇点T求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。可以看出，如果用网络流求出的最大流量比R小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。贪心方法的应用红色的连线流量为1蓝色的连线流量为0选择的射击格即为：(1,3),(2,1),(3,2),(4,4)S21432143T列:行:源:汇:贪心方法的应用网络流算法经过优化，时间复杂度可以达到O(C(n+4C+4R))上述网络流算法虽然可以通过全部数