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

1、河北唐山一中是信息学中最重要的思想之一。计算机的高速使它具备了穷举的条件。然而，随着图论、数论、动态规划等方法的发展，以及搜索算法的不断改进，穷举性似乎越来越不受重视，已经成为低效率的代名词。让我们看看这个详尽的列表。穷尽式思维，穷尽式，完全穷尽式，部分穷尽式，参数法，准确理解问题的含义，确定穷尽式思维的用途，并阐明穷尽式的对象。让我们来看看完全详尽的例子，例如一个聪明的打字员，标题描述(NOI2001)，只使用一个加号或减号(向上/向下)，左右移动光标(向左)。例如，初始状态是123456，所需状态是633451，所以最简单的转换方法是：123456，623451，623451，633451

2、，交换1，向上，向右，思考1搜索。思路很简单：通过广度优先搜索确定键序列和最小键数并输出，节点解决方案：HASH A*或双向广度优先。缺点：实现复杂度太高，效率不高。想法2使用详尽的思考来抓住问题的难度：Swap0/Swap1！如果您没有这两个键，您可以直接处理它们，并且先处理它们，而不影响结果！穷举使用这两个键，只有6个！=720例，思路2使用穷举思想，因此我们通过完全穷举得到一个算法：将按键过程分成两步，通过Swap0/1得到一个排列，并计算这个排列之后的剩余步骤。一个问题是：不是所有的立场都可以改变。解决方法：用尽所有可以再次改变的位置！时间复杂度：0(6！*10)=O(1)，出色的算法

3、！逻辑岛上有三种居民：总是说真话的上帝、总是撒谎的魔鬼和白天说真话晚上撒谎的人。一位社会学家参观了这个岛，但是他不能通过外表来区分这三种居民，所以他只能通过分析居民所说的来判断他们的种类。岛上只有五个居民，a、b、c、d和e。他们只说三种话：1。我没有跳水/邪恶/人类/死亡。2.x不是跳水/邪恶/人类/死亡。3.现在是白天/晚上。居民说的话总数不超过50个。你的任务是根据居民所说的来判断他们是什么样的人，是白天还是晚上。让我们用人脑分析，a:b是人。b:a是邪恶的。A:b是邪恶的。一个简单的例子：甲的话是矛盾的，乙是上帝！a是个魔鬼，计算机怎么能完成这个推理呢？失败了！应用穷尽的思想，主题特征

4、：人数少，所以我们得到一个完全穷尽的算法：案例数：35*2=486，判断每个句子的时间复杂度：O(35*2*s)=O(s)。总之，首先比较示例1中的两种算法。疲惫可能是盲目的，但我们是灵活的！有时，问题离有效算法只有一步之遥。我们不知道参数k，所以我们不能解决这个问题。部分穷举思想、问题的参数(其不能是穷举的)、重要参数k和部分穷举思想作为参数是可行的，并且通过有效的算法获得答案，并且使用部分穷举思想的一般步骤。部分穷举的思想特别适用于最大最小问题和最大最小问题。定义：在这类问题中定义了一个权重，它需要一个分区(或其他类似的结构)来最小化分区每个部分的权重的最大值。这里，最大值是权重的最大值，

5、最小值是除法产生的“最大值”的最小值。一个重要的问题，知道一个最大的重量，如何快速判断是否有一个部门符合要求？如果我们能找到这个问题的答案，那么我们就可以把最大重量作为一个参数，并通过部分穷尽和判断得出一个结论。一个常见的优化，如果参数的范围很大，我们需要利用题目的条件进行优化。这个话题最重要的特性是单调性。单调性意味着，如果参数为x1，则参数大于(小于)x1是可行的，并且主题要求参数的最小(较大)值。此时，我们有两个选择：我们仍然使用线性穷举方法，但是当我们得到一个可行的解决方案时，我们将停止使用二元穷举方法。当然，二分法通常可以降低时间复杂度。草莓，这是NOI2003的主题，相信大家都已经

6、很熟悉了。在这里，我们将讨论树数据。初步想法：因为它是寻求最好的价值，很容易想到树木的动态规划。然而，我们很难列出有效的状态转移方程，而且这个问题的数据量很大，所以动态规划的效率太低。进一步考虑：这是一个最小和最大的问题，我们可以使用部分耗尽吗？首先，问题是：如果我们知道一个分割方案对应的x，我们怎么才能找到解决方案或者证明这个分割不存在？一个问题的解决方案，可以通过贪婪来解决。10，5，7，8，9，x=17，从下到上处理，并把那些可以分成一组的分开。7，8，20，9，19，请看我的论文来证明这个算法的正确性。在解决示例3中，我们找到了问题的解决方案，因此我们可以通过部分耗尽和二分法来耗尽x的

7、值，然后构建解决方案。问题：相应的最大值和最小值问题无法解决。这个问题的参数(不可能是详尽的)是部分详尽的。作为参数变量，它们是可行的。草莓的分割方案，即重要参数k和x的值，用二分法穷举，用贪婪算法得到答案。我们将用部分穷举的思想来解决一个经典的图论问题。加权二部图的最大最小匹配问题给定一个加权二部图，找到满足以下条件的匹配：这个匹配是完全匹配，这个匹配满足第一个条件，其中匹配边的最大权重是最小的。最大最小匹配的现实意义这种匹配计算在日常生活中经常遇到。例如，一个公司有n个仓库和n个销售点。众所周知，将产品从第I个仓库运输到第j个销售点所需的时间是T(i，j)，每个仓库的存储容量正好等于每个销

8、售点的需求。如何在最短的时间内将货物送到所有销售点？max-min匹配，然后看max-min匹配问题的一个例子：1，2，3，1，2，3，6，4，8，10，1，5。为了清楚起见，只有6条边，其他边是无限的，这是不考虑的。我们可以看到这个图的最小权重匹配不是最大最小匹配。最大最小匹配：为了解决和应用一些详尽的想法，我们需要回答这个问题：如果我们知道权重的最大值，如何产生符合主题要求的匹配？1，2，3，1，2，3，6，4，8，10，1，5，最大重量值：7，找不到完全匹配！最大重量值：8，找到完全匹配！这是最大最小匹配。最大最小匹配：解决，所以我们得到一个最大最小匹配问题的有效算法：最大权重的部分耗尽，最大匹配算法，寻找完全匹配的时间复杂度：O(n5)线性耗尽，但效果很好，O(n3logn)二进制耗尽。我们可以对这个问题做一些扩展：相同的算法作为最小和最大匹配；加权图的最大最小匹配和加权二部图的最大最小匹配：总结；通过分析，我们可以看出，穷尽性是低效的；结