第一篇：動態電源管理算法總結

動態電源管理經典算法總結

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個星期?，F在用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 算法的應用：

差分約束系統的應用：

搜索算法

搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數據有序化，要找一個較優的搜索出發點，凡是能用高效算法的地方盡量爭取用高效算法?；镜倪f歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（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必須彼此相關的情況?；咀龇ǎ?/p>

在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。

8皇后問題

約束條件

限界函數：

子集和數問題：

約束條件

限界函數：

回溯法－－術語：

活結點：已生成一個結點而它的所有兒子結點還沒有

全部生成的結點稱為活結點。

E-結點：當前正在生成其兒子結點的活結點叫E-結點。

死結點：不再進一步擴展或其兒子結點已全部生成的結點稱為死結點。

使用限界函數的深度優先節點生成的方法成為回溯法；E-結點一直保持到死為止的狀態生成的方法 稱之為分支限界方法

且用限界函數幫助避免生成不包含答案結點子樹的狀態空間的檢索方法。區別：

分支限界法本質上就是含有剪枝的回溯法，根據遞歸的條件不同，是有不同的時間復雜度的。

回溯法深度優先搜索堆?；蚬濣c的所有子節點被遍歷后才被從棧中彈出找出滿足約束條件的所有解

分支限界法廣度優先或最小消耗優先搜索隊列，優先隊列每個結點只有一次成為活結點的機會找出滿足約束條件下的一個解或特定意義下的最優解

一般如果只考慮時間復雜度二者都是指數級別的

可是因為分支限界法存在著各種剪枝，用起來時間還是很快的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-完全的