算法合集之《非最優化算法初探》.docVIP

非最优化算法初探 北京四中 杨培 【】【】  年份 比赛 题目 较好的算法 题目类型 1997 IOI 火星探测车 贪心 最大流问题 地图标签 贪心/随机化 NPC问题 集装箱 概率+贪心 随机规划 千足虫 构造近似算法 HEX游戏 构造近似算法 博弈 1998 NOI 并行计算 贪心+随机化 大规模有哪些信誉好的足球投注网站 1999 冬令营 迷宫改造 贪心+随机化 动态规划 NOI 01串 随机化 最长路径 国家队作业 保卫地球——邵铮 随机化 NPC问题 IOI 地下城市 贪心 均分纸牌 贪心/随机化 表格 1应用非最优算法效果较好的题目 二．基本概念 可行性问题和最优性问题的关系 应用非最优化算法的题目可简单的分为两类：可行性问题和最优性问题。虽然在选择具体算法时，要对这两种问题加以区分、分别对待，但这两种问题在本质上是统一的，都可以划归为如下的判定问题。 定义1.2.1：如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题。 可行性问题可直接转化为“是否存在解”的判定问题。而对于最优性问题，可转化为若干个“是否存在比当前解更优的解”的判定问题。从这种意义上讲，可行性问题最优性问题，我们只需重点研究后者。 临域概念 定义1.2.2：对于一个最优性问题，它的所有可行解的集合D上的一个映射： N：S∈D → N(S)∈2^D 称为一个临域映射，其中2^D表示D的所有子集组成的集合，N(S)称为S的临域，S’∈N(S)称为S的一个邻居。 事实上，传统的简单算法如爬山法、贪心法都是建立在对临域的有哪些信誉好的足球投注网站基础上的。显然，上面的方法只能得到问题局部最优解，不能保证得到全局最优解。而非最优算法的目的之一就是用较小的代价跳出局部最优点，从而尽可能接近全局最优点。 三．非最优化算法分类 非最优化算法可简单的分为两类：一步算法和改进算法。 一步算法 该算法的特点是：不在两个可行解之间选择，在未终止的迭代中，又可能不是一个可行解，算法结束时得到一个可行解。这种算法的时间复杂度是容易接受的。 该算法的典型例子是火星探测器问题的贪心算法，每一辆车选一条可装矿石最多的路线，直到分配完所有车的路线。该算法没有在两个可行解之间比较选择，算法结束时得到一可行解。应当注意的是：在解决可行性问题的时候，在算法运行中可能发现无法得到最终的一可行解，这就需要进行简单的回溯或者干脆推翻了重来（如果使用了随机化方法）。例子是NOI’99的“01串”问题。 改进算法 改进算法的迭代过程是从一个可行解到另一个可行解，通常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直到满足一定的要求为止。该算法一般应用于最优性问题。例如局部有哪些信誉好的足球投注网站算法或爬山法，都是改进算法的一种。另外，在使用随机化方法时，例如迷宫改造，需要反复随机求得可行解，最后选出其中最优的。这也可以说是一种改进算法。 四．非最优化算法的性能分析 虽然非最优化算法由许多优点，但最大的缺陷是不能保证得到全局最优解，所以对算法的评价就显得十分重要。评价一个非最优化算法需要两条标准：一是看它的解与最优解的接近性，这是根本条件。如果算法得出的解与最优解的差距较大，按目前已有的计分方法，得分会相当低，更不要说应用在求最优解的题目上了。其二是考察算法的稳定性，这也是十分必要的。下面介绍了几种测试算法的简单方法。 最坏情况分析 对于任何算法，都要考察它在最坏情况的时间复杂度和空间复杂度，但对于非最优化算法，还需要考察它的最坏情况解的效果。通过最坏情况分析来评价算法的效果，其指标是计算解的值同最优解的值之间的差距，差距越小说明算法越好。 但是，最坏情况分析不能全面地评价算法的好坏，某些算法在小规模时效果很差，但不能说这个算法一定很差。（例如，集装箱问题中钱文杰的算法）另外，找到一个算法的最坏情况并不容易，它需要很多数学技巧，这也限制了这种分析方法的应用。 概率分析 概率统计分析的方法是从理论上考虑的，它假设实例的数据服从一定的概率分布。在这个数据概率分布的假设下，研究其算法或解的平均效果。这种分析方法对于估计随机化算法的可行性是十分重要的。例如，对于随机化的素数判定算法，概率分析为算法的稳定性提供了理论基础。但是概率分析是一种理论分析方法，它需要对问题本身有较深入的理解，并且掌握概率模型的建立和概率理论，要求有较强的数学基础。对于一些较复杂的问题，在考场上无法完成分析，因此，它有较大的局限性。 大规模计算分析 大规模计算分析就是常说的用测试数据测试的方法。它可对多个算法进行评价，比较分析不同算法的效果。可根据各个算法的计算结果，采用简单或统计的方法比较不同算法的性能，而不需要预先得到每个实例的最优解。用这种方法分析算法时，需要产生一些具有代表性的测试数据。关于如何