动态电源管理算法总结5篇

第一篇：动态电源管理算法总结

动态电源管理经典算法总结

written by： zengyi 2008-12-4

操作系统级动态电源管理的提出者是Mark Weiser，在其1994年发表的一篇名为《Scheduling for Reduced CPU Energy》的文章中首次提出节能和操作系统级的电源管理思想。在其后的一些年中Kinshuk Govil在操作系统级电源管理方面也做出了比较大的贡献，在其发表的名为《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》一文中对Mark Weiser提出的算法进行了改进，创造出了一些自己的方法。

在国内，对操作系统级动态电源管理的研究开始地比较迟；从阅读文章来看：科学院、中科大、国防大学、复旦大学等在这方面有着比较前沿的研究。相对于国外的研究来说，中国的研究似乎更注重于用繁杂成型算法来优化功耗：如采用隐马模型、蚁群算法等。

一、动态电压调节算法：

1、OPT(unbounded-delay perfect-future)：提出者mark weiser，文献《scheduling for reduced cpu energy》，主要思想：是使用整个踪迹数据(意思也就是说要知道将来的所有时间里cpu使用情况)，将运行时间延伸以填补所有的空闲时间周期。该算法能达到的最大可能节省通常被最小速率所限制。这个算法既不实际也不合乎逻辑。不实际是因为它需要任务在将来周期内的一些完美数据，同时它也假设空闲能被运行时间所填补。不合乎逻辑是因为在各个进程运行的过程中产生了大量的延迟，而没有很好地管理好实时进程和交互进程的响应时间，如用户击键或网络包来临了都可能会无限制地等待下去。

2、FUTUR(Ebounded-delay limited-future)：提出者mark weiser，文献《scheduling for reduced cpu energy》，主要思想：是OPT算法的一个改进，只不过它所指的将来缩短为了一个小的时间窗口，在那个时间窗口内优化能耗，这样的话将不会拖延任务的响应时间；同样，它也假设下一间隔的所有空闲时间可以被消除，除非达到了cpu的最小工作频率。而且当时间窗口达到400秒的时候，该算法跟OPT几乎是一样的效果。该算法也是不实际的，原因也是因为它使用了将来的信息；但它却是合理的，因为没有一个实时响应的延迟会超过一个时间窗口。(意思是说只要时间窗口定义恰当，还是可以满足一些实时响应的要求，至少不会出现无限制地延迟)。

3、PAST(bounded-delay limited-past)：提出者mark weiser，文献《scheduling for reduced cpu energy》, 是一个能实现的FUTURE版本。与FUTURE算法往前看一个固定窗口相反，该算法是往后看一个固定大小的时间窗口，同时假设下一时间窗口的工作量跟上一窗口是相像的。主要思想是根据前一个时间片上遗留的工作和处理器使用率来设置下一个时间片上处理器的频率和电压。将时间划分为固定长度的时间片，在每个时间片开始的时候，计算前一个时间片上处理器使用率，预测在下一个时间片上处理器会同样忙。算法使用处理器使用率的两个门限值来决定在下一个时间片上是增加、减少、还是保持当前的处理器频率。如果预测的使用率低于下门限值，就降低处理器频率，高于上门限值就增加处理器频率，否则保持处理器的频率不变。具体调节多少频率一般是与使用的处理器相关，处理器可用的频率并不是连续变化的，而是几个分离的频率点，通常的调节是每次增加或减少一挡频率。

4、AVGn：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想是与Past 算法类似，只是在预测下一个时间片上的处理器的使用率时有所不同。采用了指数平均数的方法，预测下一个时间片上的使用率是以前所有时间片上的使用率的加权平均，每个时间片上的权随着时间的向前推移而几何减小。即令n是指数平均的衰退因子，Ut 是时间片 t 上的实际的使用率，Wt 是该区间上预测的使用率，则AVGn 算法预测时间片 t 上的使用率为。衰退因子n 权衡了负载响应的及时性与稳定性，当n 越小时，系统响应负载的变化越快，但系统的频率/电压变化波动越大；n 越大，系统响应负载的变化就越慢。跟我自己看的有些出入。不知道是不是另一算法。

5、LongShort：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，该算法更注重于预测方面，它试图在本地行为以及一个相当长时期里的平均值之间寻找到一个黄金平均值。它有一个非负的实参，本地行为的权重将随着该参数的增加而增加。通过给本地行为指定一个最优可能权值，来发现该算法的一个最优预测值。按预测设置模型来说就是：

一、查找最近12个运行百分比，最近的三个构成短期预测数，余下的9个构成长期预测数。对接下来的运行百分比预测为一个加权平均值，在这个加权平均值中短期数据需乘以一个权重，也即是前面所提及的参数；

二、设置一个尽可能快的速率来完成预测工作。例如：假设权重值为4，最近12次的运行百分比是0、0.3、0.5、1、1、1、0.8、0.5、0.3、0.1、0、0；于是我们可以设置速率为：(0+0.3+0.5+1+1+1+0.8+0.5+0.3+4*(0.1+0+0))/(9+4*3)=0.276

6、Flat：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，该算法在预测方面比较薄弱，它只是简单地将速率平滑到全局的平均使用率上。该算法需要一个输入参数，而且必须是0-1之间的常数。算法分为两步：

一、预测一个常数级的运行百分比；

二、设置一个速率使其能足够快完成预测出的新的及遗留的任务。该思想希望将运行百分比保持的尽量平滑，不至于出现突变。由于速率总是设置成足够快来完成预测的新任务和遗留任务，所以所有任务的延迟都不会超过一个时间间隔。这一思想也被应用到其他算法中。

7、AGED_AVERAGES：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，与LONG_SHORT方法不一样，该算法采用了一种指数级的平滑方式，试图通过加了权重的平均值来预测下一个时间间隔的运行百分比。例如：假设间隔长度为0.01秒，权重值为2/3，先前的运行百分比是P(t),P(t-1)，P(t-2)，...，预测的新运行百分比是1/3*P(t)+2/9*P(t-1)+4/27*P(t-2)+...。注：权重值定义的注意点是应与间隔长度基本保持独立。

8、CYCLE：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，应该说以前的一些算法都比较的久经世故。然而在对运行百分比图的观察中，我们发现这些运行百分比似乎都是周期性出现的，这一规律是否可以被我们所利用呢？我们是否能找到一个这样的x，使得在x开始处的长度上与2x开始处的一个x长度上两者图形几乎一样呢？为此我们定义了一个变量error-measure，该变量的计算是这样的，对于两个一样长的跟踪数据，对应位相减后取绝对值再相加的平均值。看起来有点拗口，让我们来举一个例子：假设最近的8个数据是0-0.4-0.8-0.1-0.3-0.5-0.7-0.x取为4，于是我们可以将这八个数据分成两组，0-0.4-0.8-0.1和0.3-0.5-0.7-0，最后error-measure计算如下：(|0-0.3|+|0.4-0.5|+|0.8-0.7|+|0.1-0|)/4=0.15。由此我们可以很容易看出，error-measure的值越小，两者的相似度越高。于是我们可以通过具有最小error-measure值的区间预测下一个周期内的运行百分比。但如果算出来的error-measure都大于0.2，则将运行百分比预测为一个常数。(在有些地方，该算法也叫着自相似性，应该说有着一定的道理，不过由于用户的参与，使得随机性很大，有时根本就没什么规律)

9、PATTERN：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想是将先前的运行百分比转变成一种样式，例如我们可以定义字母表中A代表0~0.25的运行百分比，B代表0.25~0.5，C代表0.5~0.75，D代表0.75~1；于是假设我们有这样一个跟踪序列0-0.13-0.28-0.33-0.52-0.79，那么我们可以转变成这样的一个样式AABBCD。往后查看如果发现跟在该样式后面的是一个A的话，那么我们可以猜测下一间隔的运行百分比为0.125(A的中间值)。

10、Peak：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想算法预测当前的负载将伴随一个窄峰值，即预测一个上升的运行百分比将对称地下降，而下降的运行百分比将继续下降。当运行百分比为100%时，它将下降;当它为0%时，将保持不变。假设Pt-1和Pt分别为最近两个间隔的运行百分比，Pt+1为下一间隔的运行百分比。该算法预测Pt+1的原则如下:(1)If Pt > Pt-1

then Pt+1 = max(P t-1，0.1)；(2)If Pt < Pt-1

then Pt+1=min{Pt, 0.1}；(3)If Pt = Pt-1

then if Pt = 1, Pt+1 = 0.4； otherwise, pt+1 = pt；

第二篇：动态管理

动态管理：排除发展阻碍，提高决策水平

企业发展的阻碍因素有哪些？

响应市场变化的最快途径，是能够预知变化，许多公司由于不能快速的，看到自己企业内部的“全貌”，（这其中包括订单制造进度、研发进度、库存的变化等等）而无法预知变化。当主要的业务信息被控制在不同的部门和系统中时，很难全面准确的掌握情况，更不用说预知能力了.高管经常竭尽全力在企业内部的各类数据流中寻找他们所需的信息，以便正确地进行决策。有潜在价值的资料常常受困于组织壁垒中，或在系统间的传输过程中遗失，或是由于数据统计方式的设计原因而被遗漏，或是不方便的形式呈现，令用户难以使用。企业仍很难做到将有用的数据提交给需要的人。例如，一家大型化工企业的高管发现，高管获取的数据只有一半与企业决策相关。高管需要关于每一个业务单元、产品和经营业务的精确数据，但不一致的数据，对收入与成本进行横向比较制造了难题。

另外，公司如果缺乏一致、简化的内部运营，就不能做好快速响应变化的准备，不连贯的功能，无法快速顺利的协作。尤其是制造过程中订单数量较多，种类多，且发生技术变更时，当工厂依赖于分类电子表格和手工流程时，订单量时高时低可能会造成物料短缺或库存过剩。因为不断变化的市场需求使企业无法以足够快的速度，对供应和安全库存进行相应调整。

这就需要信息系统的集成和综合应用，确保数据真实一致，将数据转化成为实用的洞察力，是创造价值的关键，且最终也是企业竞争优势的关键。

信息系统不能完全基于财务会计规则的ERP僵化设计结构，将系统的输出结果局限于，有限的若干报表格式。这会导致系统无法生成需要的分析，例如，按照产品与地区划分的存货周转率。

而看似规则有序的系统界面使问题变得更加复杂。一旦高管需要审核工厂内个部门的关键业绩指标（KPI），则不得不在屏幕上混乱的数据中进行搜索和归类。因此，IT经理每月都需要抽调IT分析人员，梳理数据，提交所需的各类分析。

问题的核心在于高管信息系统的不足，设计这一系统的初衷是帮助最高管理层轻松获得相关的内部和外部数据，以利于更好地管理企业。我们的研究发现了一系列长期困扰着这一系统的常见问题。因此，部分有远见的企业领导对系统进行重新设计，重树这些系统在企业决策中的重要性。

中小企业如何通过灵活响应避免这些阻碍，从而发挥出自己的优势？全面更新不连贯的、冗余的手工流程，将其替换成为灵活高效的集成业务流程。中渊科技有限公司的APS/MES精益制造管理系统可以为您提供进行精确预测所需的洞察力，并可以帮助您快速适应以响应变化!将数据转化成为管理层最实用的洞察力和最佳的改进机会，是创造价值的关键

“灵活和适应性强”不仅对企业至关重要，对企业流程和IT系统也是如此，缺乏灵活性的IT系统无法协助企业创建灵活的运营，IT系统必须可以轻松修改和配置才能满足企业不断变化的需求，例如：当企业业务时，现有IT系统要足够“智能化”才能即时满足新的业务需要，而中渊科技的APS/MES精益制造管理系统就是这样的系统。

第三篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第四篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广

第五篇：算法总结材料

源程序代码：

}

一、自然数拆分（递归）

} #include

二、快速排序（递归）int a[100];void spilt(int t)#include { int k,j,l,i;main()for(k=1;k<=t;k++){int i,a[11]={0,14,12,5,6,32,8,9,15,7,10};{ printf(“%d+”,a[k]);} for(i=0;i<11;printf(“%4d”,a[i]),++i);printf(“n”);printf(“n”);j=t;l=a[j];quicksort(a,10);for(i=a[j-1];i<=l/2;i++)for(i=0;i<11;printf(“%4d”,a[i]),++i);{ a[j]=i;a[j+1]=l-i;printf(“n”);}

spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i;

int value=a[from];printf(“please enter the number:”);

while(from

a[from]=a[to];

while(from

++from;

a[to]=a[from];

}

a[from]=value;

return from;

}

void qsort(int a[],int from,int to){ int pivottag;if(from

{pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to);

} scanf(“%d”,&n);

for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2);

三、删数字（贪心）

#include #include void main(){

int a[11]={3,0,0,0,9,8,1,4,7,5,1};

int k=0,i=0,j;

int m;

while(i<11)

{

printf(“%d ”,a[i]);

i++;}

printf(“n please input delete number:”);

四、全排列（递归）#include A(char a[],int k,int n){

int i;char temp;if(k==n)

for(i=0;i<=3;i++)

{printf(“%c ”,a[i]);} else {

for(i=k;i<=n;i++)

{ temp=a[i];

a[i]=a[k];

a[k]=temp;

A(a,k+1,n);

} } } main(){

int n;

char a[4]={'a','b','c','d'},temp;

A(a,0,3);

getch();

return 0;}

五、多段图（动态规划）#include “stdio.h”

#define n 12 //图的顶点数

{ while(from=value)--to;

scanf(“%d”,&m);for(k=0;k

{

for(i=0;i<=11-k;i++)

{

if(a[i]>a[i+1])

{

for(j=i;j<10;j++)

{a[j]=a[j+1];}

break;//满足条件就跳转

}

} }

int quicksort(int a[],int n){

qsort(a,0,n);}

}

printf(“the change numbers:”);

for(i=0;i<11-m;i++)

{

if(a[i]!=0)

{ printf(“%d ”,a[i]);}

}

}

#define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组

int path[k];//存储最短路径的数组

void creatgraph()//创建图的(成本)邻接矩阵 { int i,j;

for(i=0;i

for(j=0;j

scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 }

void printgraph()//输出图的成本矩阵 { int i,j;

printf(“成本矩阵:n”);

for(i=0;i

{ for(j=0;j

printf(“%d ”,cost[i][j]);

printf(“n”);

} }

//使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n];

for(i=0;i

v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++)

if(cost[i][j]>0 &&(cost[i][j])+v[j]

{length=cost[i][j]+v[j];temp=j;}

v[i]=length;

d[i]=temp;

}

path[0]=0;//起点

path[k-1]=n-1;//最后的目标

for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 }

//使用向后递推算法求多段图的最短路径

void BackPath(){ int i,j,length,temp,v[n],d[n];

for(i=0;i

for(i=1;i<=n-1;i++)

{ for(length=MAX,j=i-1;j>=0;j--)

if(cost[j][i]>0 &&(cost[j][i])+v[j]

{length=cost[j][i]+v[j];temp=j;}

v[i]=length;

d[i]=temp;

}

path[0]=0;

path[k-1]=n-1;

for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];}

//输出最短路径序列 void printpath(){ int i;

for(i=0;i

printf(“%d ”,path[i]);}

main(){ freopen(“E:1input.txt”,“r”,stdin);

creatgraph();

printgraph();

FrontPath();

printf(“输出使用向前递推算法所得的最短路径:n”);

printpath();

printf(“n输出使用向后递推算法所得的最短路径:n”);

BackPath();

printpath();printf(“n”);}

六、背包问题（递归）int knap(int m, int n){

int x;

x=m-mn;

if x>0

sign=1;

else if x==0

sign=0;

else

sign=-1;

switch(sign){

case 0: knap=1;break;

case 1: if(n>1)

if knap(m-mn,n-1)

knap=1;

else

knap= knap(m,n-1);

else

knap=0;

case-1: if(n>1)

knap= knap(m,n-1);

else

knap=0;

} }

七、8皇后（回溯）#include #include #define N 4 int place(int k, int X[N+1]){

int i;

i=1;

while(i

if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))

return 0;

i++;

}

return 1;}

void Nqueens(int X[N+1]){

int k, i;

X[1]=0;k=1;

while(k>0){

X[k]=X[k]+1;

while((X[k]<=N)&&(!place(k,X)))

X[k]=X[k]+1;

if(X[k]<=N)

if(k==N){ for(i=1;i<=N;i++)

printf(“%3d”,X[i]);printf(“n”);

}

else{ k=k+1;

X[k]=0;

}

else k=k-1;

} }

void main(){

int n, i;

int X[N+1]={0};

clrscr();

Nqueens(X);

printf(“The end!”);}

八、图着色（回溯）#include #define N 5 int X[N]={0,0,0,0,0};int GRAPH[N][N]={ {0,1,1,1,0}，{1,0,1,1,1}，{1,1,0,1,0}，{1,1,1,0,1}，{0,1,0,1,0} };int M=4;int count=0;int mcoloring(int k){

int j,t;

while(1){

nextValue(k);

if(X[k]==0)

return 0;

if(k==(N-1)){

for(t=0;t

printf(“%3d”,X[t]);

printf(“n”);

count++;

}

else

mcoloring(k+1);

} } int nextValue(int k){

int j;

while(1){

X[k]=(X[k]+1)%(M+1);

if(X[k]==0)

return 0;

for(j=0;j

if((GRAPH[k][j]==1)&&(X[k]==X[j]))

break;

}

if(j==N){

return 0;

}

} } void main(){

int k;

clrscr();

k=0;

mcoloring(k);

printf(“ncount=%dn”,count);}

矩阵链乘法（动态规划） 符号S[i, j]的意义：

符号S(i, j)表示，使得下列公式右边取最小值的那个k值

public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s)

{

int n=p.length-1;

for(int i = 1;i <= n;i++)m[i][i] = 0;

for(int r = 2;r <= n;r++)

for(int i = 1;i <= n-r+1;i++){

int j=i+r-1;

m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

s[i][j] = i;

for(int k = i+1;k < j;k++){

int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if(t < m[i][j]){

m[i][j] = t;

s[i][j] = k;}

}

}

}

O的定义：

如果存在两个正常数c和n0，对于所有的n≥n0时，有：

|f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为

f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义：

如果存在正常数c和n0，对于所有n≥n0时，有：

|f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为：

f(n)=Ω(g(n))。Θ的定义：

如果存在正常数c1，c2和n0，对于所有的n>n0，有：

c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法：

O(1)

(2)指数时间算法：

O(2n)

Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1)

贪心方法基本思想：

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择

所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

多段图：

COST[j]=c(j,r)+COST[r];

回溯法：

(假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件：

(1)显式约束：限定每一个xi只能从给定的集合Si上取值。

(2)解

空

间：对于问题的一个实例，解向量满足显式

约束条件的所有多元组，构成了该实例

的一个解空间。

(3)隐式约束：规定解空间中实际上满足规范函数的元

组，描述了xi必须彼此相关的情况。基本做法：

在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

8皇后问题

约束条件

限界函数：

子集和数问题：

约束条件

限界函数：

回溯法－－术语：

活结点：已生成一个结点而它的所有儿子结点还没有

全部生成的结点称为活结点。

E-结点：当前正在生成其儿子结点的活结点叫E-结点。

死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。

使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法

且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别：

分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。

回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解

分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解

一般如果只考虑时间复杂度二者都是指数级别的

可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){

int j;

X[k]=1;

if(s+W[k]==M){

for(j=1;j<=k;j++)

printf(“%d ”,X[j]);

printf(“n”);

}

else

if((s+W[k]+W[k+1])<=M){

sumofsub(s+W[k],k+1,r-W[k]);

}

if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){

X[k]=0;

sumofsub(s,k+1,r-W[k]);

} } void main(){

M=30;

W[1]=15;

W[2]=9;

W[3]=8;

W[4]=7;

W[5]=6;

W[6]=5;

W[7]=4;

W[8]=3;

W[9]=2;

W[10]=1;

sumofsub(0,1,60);}

P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的