算法合集之《浅谈特殊穷举思想的应用》

《算法合集之《浅谈特殊穷举思想的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈特殊穷举思想的应用河北唐山一中鬲融穷举的思想穷举思想是信息学中最重要的思想之一，计算机的高速度使其具备了进行穷举的条件。然而，随着图论、数论、动态规划等方法的发展，以及搜索算法的不断改进，穷举似乎越来越不受重视，成为了‘低效’的代名词。穷举低效？让我们先来了解一下穷举。穷举的思想穷举完全穷举部分穷举参变量法准确理解题意确定使用穷举思想明确穷举对象下面先来看一下完全穷举的例子例一聪明的打字员题目描述(NOI2001)使用一个只有加减1（Up/Down），左右移动光标（Left/Right），与1，6交换（Swap0/Swap1）六个键的键盘，用最少的步数把一个6

2、位数转化成另外一个。例如，初始状态是123456，要求的状态是633451，那么最简单的转化方法是：123456623451623451633451Swap1UpRight思路1搜索思路很简单：通过广度优先搜索确定按键顺序和最小按键次数并输出节点数：6,000,000过大解决：HASH+A*或双向广度优先缺点：实现复杂度太高，而且效率也不高思路2使用穷举思想抓住问题的难点：Swap0/Swap1!要是没有这两个键……直接处理就可以把这两个键先处理，不影响结果！穷举这两个键的使用，只有6！=720种情况思路2使用穷举思想这样我们通过完全穷举得到了一个算法：把按键

3、过程分为两步通过Swap0/1得到一个排列计算这个排列后剩余的步数一个问题：并不是所有的位置都可以改变解决方法：再次穷举哪些位置可以改变！时间复杂度：O(6!*10)=O(1)优秀的算法！例二逻辑岛题目描述：在逻辑岛上有3种居民：永远说真话的神，永远说假话的恶魔和在白天说真话，在夜里说假话的人。一个社会学家访问了这个岛，但他无法通过外表区分这3种居民，所以他只能靠分析居民们说的话来判断他们的种类。岛上只有五个居民A，B，C，D，E。他们说的话只有3种1.Iam[not]divine/evil/human/lying.2.Xis[not]divine/evil/hu

4、man/lying.3.Itisday/night.居民们说话的总数不超过50。你的任务就是通过居民们说的话来判断他们的种类以及现在是白天还是黑夜让我们用人脑分析A:Bishuman.B:Aisevil.A:Bisevil.一个简单的例子：A的话有矛盾B是神！A是恶魔计算机怎样完成这种推理？失败！应用穷举思想题目特点：人数少于是得到了完全穷举的算法：情况数：35*2=486对每句话进行判断时间复杂度：O(35*2*s)=O(s)小结先来比较一下例一的两种算法算法时空复杂度评价搜索高,指数级未充分利用题目条件穷举思想低,常数级巧妙选择了穷举对象穷举或许具有很大的盲

5、目性，但我们自身是灵活的！部分穷举思想有时候，问题离高效算法只有一步之遥。问题高效算法参数K我们不知道参数K，所以我们不能解决问题。部分穷举思想问题的参数（无法穷举）重要参数K部分穷举，作为参变量可行通过高效算法得到答案使用部分穷举思想的一般步骤。部分穷举思想特别适用于最大最小问题最大最小问题定义：这类问题中定义一种权值，要求产生一种划分（或其他类似的结构），使划分的每一部分权值的最大值达到最小。这里最大是权的最大值，最小是划分产生的“最大”的最小。一个重要的问题已知一个最大权值，如何快速判断是否有满足要求的划分？如果我们能找到这个问题的答案,那么我们就可以把最大

6、权值作为参变量，通过对它进行部分穷举和判断，得到结论。一种常用优化如果参变量的范围很大，我们就需要利用题目的条件进行优化。题目最重要的性质是单调性。单调性是指如果参变量为x1时可行，那么参变量大（小）于x1时也可行，而且题目要求的是参变量的最小（大）值。这时，我们有两种选择：仍然用线形的穷举方法，但是当得到一个可行的解时，就停止改用二分形式的穷举方法。当然，二分往往可以使时间复杂度减小。例三草莓这是NOI2003的题目，相信大家都已经很熟悉。这里我们要讨论的是树形数据。初步想法：既然是求最值，容易想到树的动态规划。可是，我们很难列出有效的状态转移方程，而且该题数据

7、较大，用动态规划效率太低。进一步考虑：这是一个最小最大问题，能否使用部分穷举？首先面临的问题：如果已知一个分割方案所对应的x，我们如何去寻找一个解答，或者证明这种分割是不存在的？（问题★）问题★的解决这个问题可以用贪心来解决。105789x=17从下向上处理，遇到可以分成一组的就分出来。7820919对于这个算法的正确性证明请见我的论文。例三的解决我们找到了问题★的解法，于是我们就可以通过部分穷举，用二分法穷举x的值，然后构造解法。问题：相应的最大最小问题无法解决。问题的参数（无法穷举）部分穷举，作为参变量可行通过高效算法得到答案草莓的分割方案重要参数KX的值使用

8、二分法穷举