部分贪心在信息学竞赛中的应用.ppt

1、有些贪婪算法在情报学竞赛中的应用，北京清华附中高逸涵，引言，众所周知，贪婪算法是在情报学竞赛中广泛应用的高效算法。 然而，由于小目标数据的存在，贪婪算法可能得不到正确的结果。 怎么解决这个问题？ 有些贪婪如其名，是对问题的一部分采用贪婪算法，对其他部分采用其他算法。 部分贪婪，引言，为什么“部分”贪婪？ 当问题的特殊情况普遍较小时，用其他算法处理边界数据可以有效地避免特殊情况的讨论。 一些常用的算法对整体时间复杂度影响不大。 有些贪婪可以大大提高算法的时间效率。 引言，举个例子吧。 我们可以优化目标函数，求目标函数的最小值，先贪婪地求趋势函数的最小值，然后在其左右寻找目标函数的最小值。 例题，

2、例题1骆驼例题2Cow Relays，例题1骆驼，一个p人拿着x个包可以背对着1头穿越沙漠的骆驼的物体只有以下4种组合之一： 3个以下的包2个以下的包1人和2个以下的包裹1人和1个包。 你最少需要几辆骆驼？ 数据范围：1=p、x、y=1000000000、例题1骆驼，首先，当决定了所有人拥有的包的种类后，可以直接修正剩馀的必要的骆驼的数量。 所以我们要求的只有几个人拿包，几个人拿包。 (p、x、y分别为人、包裹、包包数)但由于数据规模大，直接列举显然不顺利，需要另外下工夫。 例题1骆驼由于整数算子的存在，直接数学修正运算变得困难。 但从总体趋势来看，I的增加显然有利于ans的减少。 那么按照贪

3、婪的想法，我们需要尽量带包裹。 例题1骆驼，我们可以轻易地得到贪婪算法：如果现在的包裹个数=2，还有空的人，请这个人拿包裹，否则请这个人拿包裹。 很遗憾，这个算法是错误的(x=3，y=3，p=1)。 怎样改善？ 对吗？部分贪婪！ 例题1骆驼在人数和包裹的数量足够多的时候，显然有包裹。 经过验证，人数和包裹数=20时，必定存在最佳解，骆驼有人和包裹。 算法的正确性可以通过采用调整法容易地证明。 另一方面，如果人数和数据包数目小于20，则可以使用列举方法解决问题。 例题1骆驼、已知、朴素算法、贪婪算法、解答、大规模数据、小规模特例、部分贪婪算法、x、x、例题2Cow Relays，在一个无向图上有

4、t边，在各个点和至少有两边的数据大小：1=n=100000 并且，这个点连接的最小的边往返。 最后从这个点直接移动到终点。 对于这一思想，我们设定了贪婪算法，列举一边进行往返运动，很容易从起点和终点分别向这一边以增量最短的路径到达。 例题2Cow Relays、增量最短路径是指从所有边减去基准边后的新图内的最短路径。 s，t，5，5，5，5，4，7，N=20，基准边，3例题2Cow Relays，回顾我们求最短增量路径的过程，我们求的最短增量路径必定是边缘数确定时的最短路径因此，用动态校正图像预处理在从源点到每个点的边缘数恒定时得到的最短路径的长度，在贪婪时列举最短递增路径的长度即可。 部分贪

5、婪思想！ 例题2Cow Relays，基准边，3，2，3，例题2Cow Relays，例题2Cow Relays，贪欲算法：朴素动态修订画：部分贪欲：快，快， 慢，结果，例题1骆驼，结果，例题2Cow Relays，总结，朴素的算法构想简单，算法低效，难以错误的贪婪算法构想复杂，算法高效，难以错误的部分贪婪构想简单，算法高效，难以错误至少有六只骆驼有包裹，二十只骆驼有包和人。 那么，把4个包裹的骆驼和6个包包和6个人的骆驼再分配，我们有12个包，6个包，6个人，我们有6个骆驼有人和包，3个骆驼有包，这只有9个骆驼就可以了。 也就是说，我们得到了比最佳解更好的解、矛盾，所以假设不成立。 关于与以前论文的关系，楼天城前辈在2004年有论文，介绍了关于搜索算法与其他算法结合的具体实践，形成了新的算法部分搜索。 两篇论文介绍的算法不同，但本质相同，结合特征算法和其他算法，平衡算法的优势和劣势，达到主题期望。 可以说是情报学竞赛中平衡思想的具体实践。 一些贪婪算法的