第一篇:動(dòng)態(tài)電源管理算法總結(jié)
動(dòng)態(tài)電源管理經(jīng)典算法總結(jié)
written by: zengyi 2008-12-4
操作系統(tǒng)級(jí)動(dòng)態(tài)電源管理的提出者是Mark Weiser,在其1994年發(fā)表的一篇名為《Scheduling for Reduced CPU Energy》的文章中首次提出節(jié)能和操作系統(tǒng)級(jí)的電源管理思想。在其后的一些年中Kinshuk Govil在操作系統(tǒng)級(jí)電源管理方面也做出了比較大的貢獻(xiàn),在其發(fā)表的名為《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》一文中對(duì)Mark Weiser提出的算法進(jìn)行了改進(jìn),創(chuàng)造出了一些自己的方法。
在國(guó)內(nèi),對(duì)操作系統(tǒng)級(jí)動(dòng)態(tài)電源管理的研究開(kāi)始地比較遲;從閱讀文章來(lái)看:科學(xué)院、中科大、國(guó)防大學(xué)、復(fù)旦大學(xué)等在這方面有著比較前沿的研究。相對(duì)于國(guó)外的研究來(lái)說(shuō),中國(guó)的研究似乎更注重于用繁雜成型算法來(lái)優(yōu)化功耗:如采用隱馬模型、蟻群算法等。
一、動(dòng)態(tài)電壓調(diào)節(jié)算法:
1、OPT(unbounded-delay perfect-future):提出者mark weiser,文獻(xiàn)《scheduling for reduced cpu energy》,主要思想:是使用整個(gè)蹤跡數(shù)據(jù)(意思也就是說(shuō)要知道將來(lái)的所有時(shí)間里cpu使用情況),將運(yùn)行時(shí)間延伸以填補(bǔ)所有的空閑時(shí)間周期。該算法能達(dá)到的最大可能節(jié)省通常被最小速率所限制。這個(gè)算法既不實(shí)際也不合乎邏輯。不實(shí)際是因?yàn)樗枰蝿?wù)在將來(lái)周期內(nèi)的一些完美數(shù)據(jù),同時(shí)它也假設(shè)空閑能被運(yùn)行時(shí)間所填補(bǔ)。不合乎邏輯是因?yàn)樵诟鱾€(gè)進(jìn)程運(yùn)行的過(guò)程中產(chǎn)生了大量的延遲,而沒(méi)有很好地管理好實(shí)時(shí)進(jìn)程和交互進(jìn)程的響應(yīng)時(shí)間,如用戶(hù)擊鍵或網(wǎng)絡(luò)包來(lái)臨了都可能會(huì)無(wú)限制地等待下去。
2、FUTUR(Ebounded-delay limited-future):提出者mark weiser,文獻(xiàn)《scheduling for reduced cpu energy》,主要思想:是OPT算法的一個(gè)改進(jìn),只不過(guò)它所指的將來(lái)縮短為了一個(gè)小的時(shí)間窗口,在那個(gè)時(shí)間窗口內(nèi)優(yōu)化能耗,這樣的話(huà)將不會(huì)拖延任務(wù)的響應(yīng)時(shí)間;同樣,它也假設(shè)下一間隔的所有空閑時(shí)間可以被消除,除非達(dá)到了cpu的最小工作頻率。而且當(dāng)時(shí)間窗口達(dá)到400秒的時(shí)候,該算法跟OPT幾乎是一樣的效果。該算法也是不實(shí)際的,原因也是因?yàn)樗褂昧藢?lái)的信息;但它卻是合理的,因?yàn)闆](méi)有一個(gè)實(shí)時(shí)響應(yīng)的延遲會(huì)超過(guò)一個(gè)時(shí)間窗口。(意思是說(shuō)只要時(shí)間窗口定義恰當(dāng),還是可以滿(mǎn)足一些實(shí)時(shí)響應(yīng)的要求,至少不會(huì)出現(xiàn)無(wú)限制地延遲)。
3、PAST(bounded-delay limited-past):提出者mark weiser,文獻(xiàn)《scheduling for reduced cpu energy》, 是一個(gè)能實(shí)現(xiàn)的FUTURE版本。與FUTURE算法往前看一個(gè)固定窗口相反,該算法是往后看一個(gè)固定大小的時(shí)間窗口,同時(shí)假設(shè)下一時(shí)間窗口的工作量跟上一窗口是相像的。主要思想是根據(jù)前一個(gè)時(shí)間片上遺留的工作和處理器使用率來(lái)設(shè)置下一個(gè)時(shí)間片上處理器的頻率和電壓。將時(shí)間劃分為固定長(zhǎng)度的時(shí)間片,在每個(gè)時(shí)間片開(kāi)始的時(shí)候,計(jì)算前一個(gè)時(shí)間片上處理器使用率,預(yù)測(cè)在下一個(gè)時(shí)間片上處理器會(huì)同樣忙。算法使用處理器使用率的兩個(gè)門(mén)限值來(lái)決定在下一個(gè)時(shí)間片上是增加、減少、還是保持當(dāng)前的處理器頻率。如果預(yù)測(cè)的使用率低于下門(mén)限值,就降低處理器頻率,高于上門(mén)限值就增加處理器頻率,否則保持處理器的頻率不變。具體調(diào)節(jié)多少頻率一般是與使用的處理器相關(guān),處理器可用的頻率并不是連續(xù)變化的,而是幾個(gè)分離的頻率點(diǎn),通常的調(diào)節(jié)是每次增加或減少一擋頻率。
4、AVGn:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,主要思想是與Past 算法類(lèi)似,只是在預(yù)測(cè)下一個(gè)時(shí)間片上的處理器的使用率時(shí)有所不同。采用了指數(shù)平均數(shù)的方法,預(yù)測(cè)下一個(gè)時(shí)間片上的使用率是以前所有時(shí)間片上的使用率的加權(quán)平均,每個(gè)時(shí)間片上的權(quán)隨著時(shí)間的向前推移而幾何減小。即令n是指數(shù)平均的衰退因子,Ut 是時(shí)間片 t 上的實(shí)際的使用率,Wt 是該區(qū)間上預(yù)測(cè)的使用率,則AVGn 算法預(yù)測(cè)時(shí)間片 t 上的使用率為。衰退因子n 權(quán)衡了負(fù)載響應(yīng)的及時(shí)性與穩(wěn)定性,當(dāng)n 越小時(shí),系統(tǒng)響應(yīng)負(fù)載的變化越快,但系統(tǒng)的頻率/電壓變化波動(dòng)越大;n 越大,系統(tǒng)響應(yīng)負(fù)載的變化就越慢。跟我自己看的有些出入。不知道是不是另一算法。
5、LongShort:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,該算法更注重于預(yù)測(cè)方面,它試圖在本地行為以及一個(gè)相當(dāng)長(zhǎng)時(shí)期里的平均值之間尋找到一個(gè)黃金平均值。它有一個(gè)非負(fù)的實(shí)參,本地行為的權(quán)重將隨著該參數(shù)的增加而增加。通過(guò)給本地行為指定一個(gè)最優(yōu)可能權(quán)值,來(lái)發(fā)現(xiàn)該算法的一個(gè)最優(yōu)預(yù)測(cè)值。按預(yù)測(cè)設(shè)置模型來(lái)說(shuō)就是:
一、查找最近12個(gè)運(yùn)行百分比,最近的三個(gè)構(gòu)成短期預(yù)測(cè)數(shù),余下的9個(gè)構(gòu)成長(zhǎng)期預(yù)測(cè)數(shù)。對(duì)接下來(lái)的運(yùn)行百分比預(yù)測(cè)為一個(gè)加權(quán)平均值,在這個(gè)加權(quán)平均值中短期數(shù)據(jù)需乘以一個(gè)權(quán)重,也即是前面所提及的參數(shù);
二、設(shè)置一個(gè)盡可能快的速率來(lái)完成預(yù)測(cè)工作。例如:假設(shè)權(quán)重值為4,最近12次的運(yùn)行百分比是0、0.3、0.5、1、1、1、0.8、0.5、0.3、0.1、0、0;于是我們可以設(shè)置速率為:(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,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,該算法在預(yù)測(cè)方面比較薄弱,它只是簡(jiǎn)單地將速率平滑到全局的平均使用率上。該算法需要一個(gè)輸入?yún)?shù),而且必須是0-1之間的常數(shù)。算法分為兩步:
一、預(yù)測(cè)一個(gè)常數(shù)級(jí)的運(yùn)行百分比;
二、設(shè)置一個(gè)速率使其能足夠快完成預(yù)測(cè)出的新的及遺留的任務(wù)。該思想希望將運(yùn)行百分比保持的盡量平滑,不至于出現(xiàn)突變。由于速率總是設(shè)置成足夠快來(lái)完成預(yù)測(cè)的新任務(wù)和遺留任務(wù),所以所有任務(wù)的延遲都不會(huì)超過(guò)一個(gè)時(shí)間間隔。這一思想也被應(yīng)用到其他算法中。
7、AGED_AVERAGES:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,與LONG_SHORT方法不一樣,該算法采用了一種指數(shù)級(jí)的平滑方式,試圖通過(guò)加了權(quán)重的平均值來(lái)預(yù)測(cè)下一個(gè)時(shí)間間隔的運(yùn)行百分比。例如:假設(shè)間隔長(zhǎng)度為0.01秒,權(quán)重值為2/3,先前的運(yùn)行百分比是P(t),P(t-1),P(t-2),...,預(yù)測(cè)的新運(yùn)行百分比是1/3*P(t)+2/9*P(t-1)+4/27*P(t-2)+...。注:權(quán)重值定義的注意點(diǎn)是應(yīng)與間隔長(zhǎng)度基本保持獨(dú)立。
8、CYCLE:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,應(yīng)該說(shuō)以前的一些算法都比較的久經(jīng)世故。然而在對(duì)運(yùn)行百分比圖的觀察中,我們發(fā)現(xiàn)這些運(yùn)行百分比似乎都是周期性出現(xiàn)的,這一規(guī)律是否可以被我們所利用呢?我們是否能找到一個(gè)這樣的x,使得在x開(kāi)始處的長(zhǎng)度上與2x開(kāi)始處的一個(gè)x長(zhǎng)度上兩者圖形幾乎一樣呢?為此我們定義了一個(gè)變量error-measure,該變量的計(jì)算是這樣的,對(duì)于兩個(gè)一樣長(zhǎng)的跟蹤數(shù)據(jù),對(duì)應(yīng)位相減后取絕對(duì)值再相加的平均值??雌饋?lái)有點(diǎn)拗口,讓我們來(lái)舉一個(gè)例子:假設(shè)最近的8個(gè)數(shù)據(jù)是0-0.4-0.8-0.1-0.3-0.5-0.7-0.x取為4,于是我們可以將這八個(gè)數(shù)據(jù)分成兩組,0-0.4-0.8-0.1和0.3-0.5-0.7-0,最后error-measure計(jì)算如下:(|0-0.3|+|0.4-0.5|+|0.8-0.7|+|0.1-0|)/4=0.15。由此我們可以很容易看出,error-measure的值越小,兩者的相似度越高。于是我們可以通過(guò)具有最小error-measure值的區(qū)間預(yù)測(cè)下一個(gè)周期內(nèi)的運(yùn)行百分比。但如果算出來(lái)的error-measure都大于0.2,則將運(yùn)行百分比預(yù)測(cè)為一個(gè)常數(shù)。(在有些地方,該算法也叫著自相似性,應(yīng)該說(shuō)有著一定的道理,不過(guò)由于用戶(hù)的參與,使得隨機(jī)性很大,有時(shí)根本就沒(méi)什么規(guī)律)
9、PATTERN:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,主要思想是將先前的運(yùn)行百分比轉(zhuǎn)變成一種樣式,例如我們可以定義字母表中A代表0~0.25的運(yùn)行百分比,B代表0.25~0.5,C代表0.5~0.75,D代表0.75~1;于是假設(shè)我們有這樣一個(gè)跟蹤序列0-0.13-0.28-0.33-0.52-0.79,那么我們可以轉(zhuǎn)變成這樣的一個(gè)樣式AABBCD。往后查看如果發(fā)現(xiàn)跟在該樣式后面的是一個(gè)A的話(huà),那么我們可以猜測(cè)下一間隔的運(yùn)行百分比為0.125(A的中間值)。
10、Peak:提出者Kinshuk Govil,文獻(xiàn)《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》,主要思想算法預(yù)測(cè)當(dāng)前的負(fù)載將伴隨一個(gè)窄峰值,即預(yù)測(cè)一個(gè)上升的運(yùn)行百分比將對(duì)稱(chēng)地下降,而下降的運(yùn)行百分比將繼續(xù)下降。當(dāng)運(yùn)行百分比為100%時(shí),它將下降;當(dāng)它為0%時(shí),將保持不變。假設(shè)Pt-1和Pt分別為最近兩個(gè)間隔的運(yùn)行百分比,Pt+1為下一間隔的運(yùn)行百分比。該算法預(yù)測(cè)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;
第二篇:動(dòng)態(tài)管理
動(dòng)態(tài)管理:排除發(fā)展阻礙,提高決策水平
企業(yè)發(fā)展的阻礙因素有哪些?
響應(yīng)市場(chǎng)變化的最快途徑,是能夠預(yù)知變化,許多公司由于不能快速的,看到自己企業(yè)內(nèi)部的“全貌”,(這其中包括訂單制造進(jìn)度、研發(fā)進(jìn)度、庫(kù)存的變化等等)而無(wú)法預(yù)知變化。當(dāng)主要的業(yè)務(wù)信息被控制在不同的部門(mén)和系統(tǒng)中時(shí),很難全面準(zhǔn)確的掌握情況,更不用說(shuō)預(yù)知能力了.高管經(jīng)常竭盡全力在企業(yè)內(nèi)部的各類(lèi)數(shù)據(jù)流中尋找他們所需的信息,以便正確地進(jìn)行決策。有潛在價(jià)值的資料常常受困于組織壁壘中,或在系統(tǒng)間的傳輸過(guò)程中遺失,或是由于數(shù)據(jù)統(tǒng)計(jì)方式的設(shè)計(jì)原因而被遺漏,或是不方便的形式呈現(xiàn),令用戶(hù)難以使用。企業(yè)仍很難做到將有用的數(shù)據(jù)提交給需要的人。例如,一家大型化工企業(yè)的高管發(fā)現(xiàn),高管獲取的數(shù)據(jù)只有一半與企業(yè)決策相關(guān)。高管需要關(guān)于每一個(gè)業(yè)務(wù)單元、產(chǎn)品和經(jīng)營(yíng)業(yè)務(wù)的精確數(shù)據(jù),但不一致的數(shù)據(jù),對(duì)收入與成本進(jìn)行橫向比較制造了難題。
另外,公司如果缺乏一致、簡(jiǎn)化的內(nèi)部運(yùn)營(yíng),就不能做好快速響應(yīng)變化的準(zhǔn)備,不連貫的功能,無(wú)法快速順利的協(xié)作。尤其是制造過(guò)程中訂單數(shù)量較多,種類(lèi)多,且發(fā)生技術(shù)變更時(shí),當(dāng)工廠依賴(lài)于分類(lèi)電子表格和手工流程時(shí),訂單量時(shí)高時(shí)低可能會(huì)造成物料短缺或庫(kù)存過(guò)剩。因?yàn)椴粩嘧兓氖袌?chǎng)需求使企業(yè)無(wú)法以足夠快的速度,對(duì)供應(yīng)和安全庫(kù)存進(jìn)行相應(yīng)調(diào)整。
這就需要信息系統(tǒng)的集成和綜合應(yīng)用,確保數(shù)據(jù)真實(shí)一致,將數(shù)據(jù)轉(zhuǎn)化成為實(shí)用的洞察力,是創(chuàng)造價(jià)值的關(guān)鍵,且最終也是企業(yè)競(jìng)爭(zhēng)優(yōu)勢(shì)的關(guān)鍵。
信息系統(tǒng)不能完全基于財(cái)務(wù)會(huì)計(jì)規(guī)則的ERP僵化設(shè)計(jì)結(jié)構(gòu),將系統(tǒng)的輸出結(jié)果局限于,有限的若干報(bào)表格式。這會(huì)導(dǎo)致系統(tǒng)無(wú)法生成需要的分析,例如,按照產(chǎn)品與地區(qū)劃分的存貨周轉(zhuǎn)率。
而看似規(guī)則有序的系統(tǒng)界面使問(wèn)題變得更加復(fù)雜。一旦高管需要審核工廠內(nèi)個(gè)部門(mén)的關(guān)鍵業(yè)績(jī)指標(biāo)(KPI),則不得不在屏幕上混亂的數(shù)據(jù)中進(jìn)行搜索和歸類(lèi)。因此,IT經(jīng)理每月都需要抽調(diào)IT分析人員,梳理數(shù)據(jù),提交所需的各類(lèi)分析。
問(wèn)題的核心在于高管信息系統(tǒng)的不足,設(shè)計(jì)這一系統(tǒng)的初衷是幫助最高管理層輕松獲得相關(guān)的內(nèi)部和外部數(shù)據(jù),以利于更好地管理企業(yè)。我們的研究發(fā)現(xiàn)了一系列長(zhǎng)期困擾著這一系統(tǒng)的常見(jiàn)問(wèn)題。因此,部分有遠(yuǎn)見(jiàn)的企業(yè)領(lǐng)導(dǎo)對(duì)系統(tǒng)進(jìn)行重新設(shè)計(jì),重樹(shù)這些系統(tǒng)在企業(yè)決策中的重要性。
中小企業(yè)如何通過(guò)靈活響應(yīng)避免這些阻礙,從而發(fā)揮出自己的優(yōu)勢(shì)?全面更新不連貫的、冗余的手工流程,將其替換成為靈活高效的集成業(yè)務(wù)流程。中淵科技有限公司的APS/MES精益制造管理系統(tǒng)可以為您提供進(jìn)行精確預(yù)測(cè)所需的洞察力,并可以幫助您快速適應(yīng)以響應(yīng)變化!將數(shù)據(jù)轉(zhuǎn)化成為管理層最實(shí)用的洞察力和最佳的改進(jìn)機(jī)會(huì),是創(chuàng)造價(jià)值的關(guān)鍵
“靈活和適應(yīng)性強(qiáng)”不僅對(duì)企業(yè)至關(guān)重要,對(duì)企業(yè)流程和IT系統(tǒng)也是如此,缺乏靈活性的IT系統(tǒng)無(wú)法協(xié)助企業(yè)創(chuàng)建靈活的運(yùn)營(yíng),IT系統(tǒng)必須可以輕松修改和配置才能滿(mǎn)足企業(yè)不斷變化的需求,例如:當(dāng)企業(yè)業(yè)務(wù)時(shí),現(xiàn)有IT系統(tǒng)要足夠“智能化”才能即時(shí)滿(mǎn)足新的業(yè)務(wù)需要,而中淵科技的APS/MES精益制造管理系統(tǒng)就是這樣的系統(tǒng)。
第三篇:算法總結(jié)
算法分析與設(shè)計(jì)總結(jié)報(bào)告
71110415 錢(qián)玉明
在計(jì)算機(jī)軟件專(zhuān)業(yè)中,算法分析與設(shè)計(jì)是一門(mén)非常重要的課程,很多人為它如癡如醉。很多問(wèn)題的解決,程序的編寫(xiě)都要依賴(lài)它,在軟件還是面向過(guò)程的階段,就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的,它可以培養(yǎng)我們養(yǎng)成思考分析問(wèn)題,解決問(wèn)題的能力。作為IT行業(yè)學(xué)生,學(xué)習(xí)算法無(wú)疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力,修煉自己的“內(nèi)功”。
下面我將談?wù)勎覍?duì)這門(mén)課程的心得與體會(huì)。
一、數(shù)學(xué)是算法的基礎(chǔ)
經(jīng)過(guò)這門(mén)課的學(xué)習(xí),我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門(mén)課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥,但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來(lái)的,尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。
①主定理
本門(mén)課中它主要應(yīng)用在分治法性能分析上。例如:T(n)=a*T(n/b)+f(n),它可以看作一個(gè)大問(wèn)題分解為a個(gè)子問(wèn)題,其中子問(wèn)題的規(guī)模為b。而f(n)可看作這些子問(wèn)題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí),我們可以設(shè)法降低子問(wèn)題組合時(shí)的消耗來(lái)提高性能。反之我們可以降低nlogba的消耗,即可以擴(kuò)大問(wèn)題的規(guī)?;蛘邷p小子問(wèn)題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。
②隨機(jī)算法中的許多定理的運(yùn)用
在這門(mén)課中,我學(xué)到了以前從未遇見(jiàn)過(guò)的隨機(jī)算法,它給予我很大的啟示。隨機(jī)算法不隨機(jī),它可通過(guò)多次的嘗試來(lái)降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來(lái)風(fēng),它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用,才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù),也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理:指紋的運(yùn)用,理論出錯(cuò)率的計(jì)算,算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。
這些算法都給予了我很大啟發(fā),要想學(xué)好算法,學(xué)好數(shù)學(xué)是必不可少的。沒(méi)有深厚的數(shù)學(xué)功力作為地基,即使再漂亮的算法框架,代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學(xué)習(xí)這門(mén)課不是僅僅掌握那幾個(gè)經(jīng)典算法例子,更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢?舉個(gè)例子。有同學(xué)曾問(wèn)我這樣一個(gè)問(wèn)題:1000只瓶子裝滿(mǎn)水,但有一瓶有毒,且毒發(fā)期為1個(gè)星期?,F(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒,每只老鼠可以喝多個(gè)瓶子的水,每個(gè)瓶子可以只喝一點(diǎn)。問(wèn)如何解決?其實(shí)一開(kāi)始我也一頭霧水,但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān),我就立馬有了思路,運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說(shuō),我們不僅要學(xué)習(xí)算法,更得學(xué)習(xí)思想方法。
①算法最基本的設(shè)計(jì)方法包括分治法,動(dòng)態(tài)規(guī)劃法,貪心法,周游法,回溯法,分支定界法。我們可利用分治法做快速排序,降低找n個(gè)元素中最大元和最小元的量級(jí),降低n位二進(jìn)制x和y相乘的量級(jí),做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問(wèn)題分解為規(guī)模較小的獨(dú)立的子問(wèn)題,關(guān)鍵是子問(wèn)題要與原問(wèn)題同類(lèi),可以采取平衡法來(lái)提高性能。
動(dòng)態(tài)規(guī)劃法是把大問(wèn)題分解為子問(wèn)題,但是子問(wèn)題是重復(fù)的,后面的問(wèn)題可以利用前面解決過(guò)的問(wèn)題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹(shù),解決矩陣連乘時(shí)最小計(jì)算次數(shù)問(wèn)題,尋找最長(zhǎng)公共子序列等等。
貪心法就是局部最優(yōu)法,先使局部最優(yōu),再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹(shù)算法,求哈夫曼編碼問(wèn)題。
周游法就是簡(jiǎn)單理解就是采取一定的策略遍歷圖中所有的點(diǎn),典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。
回溯法就是就是在滿(mǎn)足一定的條件后就往前走,當(dāng)走到某步時(shí),發(fā)現(xiàn)不滿(mǎn)足條件就退回一步重新選擇新的路線(xiàn)。典型的應(yīng)用就是8皇后問(wèn)題,平面點(diǎn)集的凸包問(wèn)題和0-1背包問(wèn)題。
分支定界法:它是解決整數(shù)規(guī)劃問(wèn)題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問(wèn)題。
②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法,會(huì)計(jì)法和勢(shì)能法。聚集法就是把指令分為幾類(lèi),計(jì)算每一類(lèi)的消耗,再全部疊加起來(lái)。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去,以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢(shì)能法計(jì)算每一步的勢(shì)的變化以及執(zhí)行這步指令的消耗,再將每一步消耗全部累計(jì)。
這幾種方法都是平攤分析法,平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間,盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多,每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類(lèi),會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗,勢(shì)能法中如何選取勢(shì)能。因此掌握這些方法原理還不夠,還要學(xué)會(huì)去應(yīng)用,在具體的問(wèn)題中去判斷分析。
三、算法與應(yīng)用緊密相關(guān)
我認(rèn)為學(xué)習(xí)算法不能局限于書(shū)本上的理論運(yùn)算,局限于如何提高性能以降低復(fù)雜度,我們要將它與實(shí)際生活聯(lián)系起來(lái)。其實(shí)算法問(wèn)題的產(chǎn)生就來(lái)自于生活,設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長(zhǎng)公共子序列算法可以應(yīng)用在生物信息學(xué)中通過(guò)檢測(cè)相似DNA片段的相似成分來(lái)檢測(cè)生物特性的相似性,也可以用來(lái)判斷兩個(gè)字符串的相近性,這可應(yīng)用在數(shù)據(jù)挖掘中。快速傅立葉變換(FFT)可應(yīng)用在計(jì)算多項(xiàng)式相乘上來(lái)降低復(fù)雜度,脫線(xiàn)min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法,它對(duì)于解決網(wǎng)絡(luò)流量分配問(wèn)題起了很大的幫助,等等。
這些應(yīng)用給了我很大的啟發(fā):因?yàn)閱渭冎v一個(gè)Union-Find算法,即使了解了它的實(shí)現(xiàn)原理,遇到具體的實(shí)際問(wèn)題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問(wèn)題結(jié)合起來(lái),不能停留在思想方法階段,要學(xué)以致用,做到具體問(wèn)題具體分析。
四、對(duì)計(jì)算模型和NP問(wèn)題的理解
由于對(duì)這部分內(nèi)容不是很理解,所以就粗淺的談一下我的看法。
首先談到計(jì)算模型,就不得不提到圖靈計(jì)算,他將基本的計(jì)算抽象化,造出一個(gè)圖靈機(jī),得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問(wèn)題都是可以計(jì)算的,否則就是不可計(jì)算的。由此引申出一個(gè)著名論題:任何合理的計(jì)算模型都是相互等價(jià)的。它說(shuō)明了可計(jì)算性本身不依賴(lài)于任何具體的模型而客觀存在。
NP問(wèn)題比較復(fù)雜,我認(rèn)為它是制約算法發(fā)展的瓶頸,但這也是算法分析的魅力所在。NP問(wèn)題一般可分為3類(lèi),NP-C問(wèn)題,NP-hard問(wèn)題以及頑型問(wèn)題。NP-C它有個(gè)特殊的性質(zhì),如果存在一個(gè)NP-C問(wèn)題找到一個(gè)多項(xiàng)式時(shí)間的解法,則所有的NP-C問(wèn)題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問(wèn)題。NP-hard主要是解決最優(yōu)化問(wèn)題。它不一定是NP問(wèn)題。這些問(wèn)題在規(guī)模較小時(shí)可以找出精確解,但是規(guī)模大時(shí),就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問(wèn)題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法,如漢諾塔問(wèn)題。
最后談?wù)剬?duì)這門(mén)課程的建議
①對(duì)于這門(mén)算法課,我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問(wèn)題而不給出答案,講完一章,再發(fā)課件。讓我們先思考一會(huì)兒,或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制,誰(shuí)能解決這個(gè)問(wèn)題,平時(shí)成績(jī)加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問(wèn)題的能力。因?yàn)槲腋杏X(jué)到,一個(gè)問(wèn)題出來(lái),未經(jīng)過(guò)思考就已經(jīng)知曉它的答案,就沒(méi)什么意思,得不到提高,而且也不能加深對(duì)問(wèn)題的思考和理解。下次遇到類(lèi)似的問(wèn)題也就沒(méi)有什么印象。而且上課讓我們思考,點(diǎn)名回答問(wèn)題可以一定程度上有效的防止不認(rèn)真聽(tīng)課的現(xiàn)象。
②作業(yè)安排的不是很恰當(dāng)。本門(mén)課主要安排了三次作業(yè),個(gè)人感覺(jué)只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼,沒(méi)有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問(wèn)題的能力也沒(méi)有太多的幫助,因?yàn)檫@間接成為了程序設(shè)計(jì)題,不是算法設(shè)計(jì)題。
③本門(mén)課的時(shí)間安排的不太恰當(dāng),因?yàn)楸緦W(xué)期的課程太多,壓力太大。沒(méi)有太多的時(shí)間去學(xué)習(xí)這門(mén)課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣,比較重視,想花功夫,但苦于沒(méi)時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期,那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過(guò),且課程的壓力也不是很大。錯(cuò)開(kāi)時(shí)間的話(huà),我覺(jué)得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。
第四篇:算法總結(jié)
算法分塊總結(jié)
為備戰(zhàn)2005年11月4日成都一戰(zhàn),特將已經(jīng)做過(guò)的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié),主要突出算法思路,盡量選取有代表性的題目,盡量做到算法的全面性,不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中,時(shí)刻都要牢記要減少冗余,要以簡(jiǎn)潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問(wèn)題時(shí),要想方設(shè)法進(jìn)行模型簡(jiǎn)化,轉(zhuǎn)化,轉(zhuǎn)化成我們熟悉的東西。
圖論模型的應(yīng)用
分層圖思想的應(yīng)用:
用此思想可以建立起更簡(jiǎn)潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型,進(jìn)而很容易得到有效算法。重要的是,新建立的圖有一些很好的性質(zhì): 由于層是由復(fù)制得到的,所以所有層都非常相似,以至于我們只要在邏輯上分出層的概念即可,根本不用在程序中進(jìn)行新層的存儲(chǔ),甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性,很多計(jì)算結(jié)果都是相同的。所以我們只需對(duì)這些計(jì)算進(jìn)行一次,把結(jié)果存起來(lái),而不需要反復(fù)計(jì)算。如此看來(lái),雖然看起來(lái)圖變大了,但實(shí)際上問(wèn)題的規(guī)模并沒(méi)有變大。層之間是拓?fù)溆行虻摹_@也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理,為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。
這些特點(diǎn)說(shuō)明這個(gè)分層圖思想還是很有潛力的,尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn),有可能大大消除冗余計(jì)算,進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用: ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用:
最大網(wǎng)絡(luò)流算法的應(yīng)用:典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用:
容量有上下界的最大流的應(yīng)用:
歐拉路以及歐拉回路的應(yīng)用:主要利用求歐拉路的套圈算法。最小生成樹(shù):
求最小生成樹(shù),比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E),后者一般應(yīng)用于稀疏圖,其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹(shù):
抽象成數(shù)學(xué)模型就是:
設(shè)G=(V,E,ω)是連通的無(wú)向圖,v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問(wèn)題有解時(shí)k 的最小值:把v0點(diǎn)從圖中刪去后,圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量,而這m 個(gè)連通分量必須通過(guò)v0來(lái)連接,所以,在圖G 的所有生成樹(shù)中 dT(v0)≥m。也就是說(shuō),當(dāng)k 首先,將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去,此時(shí)的圖可能不再連通,對(duì)各個(gè)連通分量,分別求最小生成樹(shù)。接著,對(duì)于每個(gè)連通分量V’,求一點(diǎn)v1,v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’},則該連通分量通過(guò)邊(v1,v0)與v0相連。于是,我們就得到了一個(gè)m度限制生成樹(shù),不難證明,這就是最小m度限制生成樹(shù)。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹(shù)是無(wú)根樹(shù),為了解題的簡(jiǎn)便,把該樹(shù)轉(zhuǎn)化成以v0為根的有根樹(shù)。 假設(shè)已經(jīng)得到了最小p度限制生成樹(shù),如何求最小p+1 度限制生成樹(shù)呢?在原先的樹(shù)中加入一條與v0相關(guān)聯(lián)的邊后,必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹(shù),需刪去一條在環(huán)上的且與v0無(wú)關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大,則所得到的生成樹(shù)的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無(wú)關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn),動(dòng)態(tài)轉(zhuǎn)移方程:Best(v)=max(Best(father(v)),(father(v),v)),邊界條件為Best[v0]=-∞,Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個(gè),狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1),所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹(shù)得到最小p+1度限制生成樹(shù)的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹(shù); 2由最小m度限制生成樹(shù)得到最小m+1度限制生成樹(shù);3 當(dāng)dT(v0)=k時(shí)停止。 加邊和去邊過(guò)程,利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹(shù): 加邊和去邊很值得注意。 每加入一條不在樹(shù)上的邊,總能形成一個(gè)環(huán),只有刪去環(huán)上的一條邊,才能保證交換后仍然是生成樹(shù),而刪去邊的權(quán)值越大,新得到的生成樹(shù)的權(quán)值和越小。具體做法: 首先做一步預(yù)處理,求出樹(shù)上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊,然后,枚舉圖中不在樹(shù)上的邊,有了剛才的預(yù)處理,我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢?因?yàn)檫@是一棵樹(shù),所以并不需要什么高深的算法,只要簡(jiǎn)單的BFS 即可。 最短路徑的應(yīng)用: Dijkstra 算法應(yīng)用: Folyed 算法應(yīng)用: Bellman-Ford 算法的應(yīng)用: 差分約束系統(tǒng)的應(yīng)用: 搜索算法 搜索對(duì)象和搜索順序的選取最為重要。一些麻煩題,要注意利用數(shù)據(jù)有序化,要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn),凡是能用高效算法的地方盡量爭(zhēng)取用高效算法?;镜倪f歸回溯深搜,記憶化搜索,注意剪枝: 廣搜(BFS)的應(yīng)用: 枚舉思想的應(yīng)用: ZOJ 1252 island of logic A*算法的應(yīng)用: IDA*算法的應(yīng)用,以及跳躍式搜索探索: 限深搜索,限次: 迭代加深搜索: 部分搜索+高效算法(比如二分匹配,動(dòng)態(tài)規(guī)劃): ZOJ milk bottle data: 剪枝優(yōu)化探索: 可行性剪枝,最優(yōu)性剪枝,調(diào)整搜索順序是常用的優(yōu)化手段。 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取,以及狀態(tài)轉(zhuǎn)移方程,另外還要考慮高效的預(yù)處理(以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移)。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP,又叫帶集合的動(dòng)態(tài)規(guī)劃:題目特點(diǎn)是有一維的維數(shù)特別小。類(lèi)似TSP問(wèn)題的DP: 狀態(tài)劃分比較困難的題目: 樹(shù)形DP: 四邊形不等式的應(yīng)用探索:四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2) 高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 并查集的應(yīng)用: 巧用并查集中的路徑壓縮思想: 堆的利用: 線(xiàn)段樹(shù)的應(yīng)用: 總結(jié)用線(xiàn)段樹(shù)解題的方法 根據(jù)題目要求將一個(gè)區(qū)間建成線(xiàn)段樹(shù),一般的題目都需要對(duì)坐標(biāo)離散。建樹(shù)時(shí),不要拘泥于線(xiàn)段樹(shù)這個(gè)名字而只將線(xiàn)段建樹(shù),只要是表示區(qū)間,而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線(xiàn)段、或數(shù)組中一個(gè)值)組成的,都可以建線(xiàn)段樹(shù);不要拘泥于一維,根據(jù)題目要求可以建立面積樹(shù)、體積樹(shù)等等 樹(shù)的每個(gè)節(jié)點(diǎn)根據(jù)題目所需,設(shè)置變量記錄要求的值 用樹(shù)形結(jié)構(gòu)來(lái)維護(hù)這些變量:如果是求總數(shù),則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù),如果要求最值,則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí),都只對(duì)O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn),在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中,要靈活的運(yùn)用子樹(shù)的收縮與葉子節(jié)點(diǎn)的釋放,避免重復(fù)操作。 Trie的應(yīng)用:; Trie圖的應(yīng)用探索: 后綴數(shù)組的應(yīng)用研究: 在字符串處理當(dāng)中,后綴樹(shù)和后綴數(shù)組都是非常有力的工具,其中后綴樹(shù)了解得比較多,關(guān)于后綴數(shù)組則很少見(jiàn)于國(guó)內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹(shù)的一個(gè)非常精巧的替代品,它比后綴樹(shù)容易編程實(shí)現(xiàn),能夠?qū)崿F(xiàn)后綴樹(shù)的很多功能而時(shí)間復(fù)雜度也不太遜色,并且,它比后綴樹(shù)所占用的空間小很多。 樹(shù)狀數(shù)組的應(yīng)用探索:; 計(jì)算幾何 掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用:; 半平面交算法的應(yīng)用:; 幾何+模擬類(lèi)題目:幾何設(shè)計(jì)好算法,模擬控制好精度。掃描法:; 轉(zhuǎn)化法:ZOJ 1606 將求所圍的格子數(shù),巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用:; 經(jīng)典算法:找平面上的最近點(diǎn)對(duì)。 貪心 矩形切割 二分思想應(yīng)用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序?qū)?shù): 利用快速排序算法思想,查詢(xún)N個(gè)數(shù)中的第K小數(shù): 博弈問(wèn)題 博弈類(lèi)題目通常用三類(lèi)解法:第一類(lèi)推結(jié)論; 第二類(lèi)遞推,找N位置,P位置; 第三類(lèi)SG函數(shù)的應(yīng)用。第四類(lèi)極大極小法,甚至配合上αβ剪枝。最難掌握的就是第四類(lèi)極大極小法。 第一類(lèi):推結(jié)論。典型題目: 第二類(lèi):遞推。典型題目: 比如有向無(wú)環(huán)圖類(lèi)型的博弈。在一個(gè)有向圖中,我們把選手I有必勝策略的初始位置稱(chēng)為N位置(Next player winning),其余的位置被稱(chēng)為P位置(Previous player winning)。很顯然,P位置和N位置應(yīng)該具有如下性質(zhì): 1. 所有的結(jié)束位置都是P位置。 2. 對(duì)于每一個(gè)N位置,至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3. 對(duì)于每一個(gè)P位置,它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。 這樣,獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置,因?yàn)樵谝粋€(gè)P位置,你的對(duì)手只能將棋子移動(dòng)到一個(gè)N位置,然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng),最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置(結(jié)束位置是P位置),這時(shí)你的對(duì)手將無(wú)法在移動(dòng)棋子,你便贏得了勝利。 與此同時(shí),得到了這些性質(zhì),我們便很容易通過(guò)倒退的方法求出哪些位置是P位置,哪些位置是N位置,具體的算法為: 1. 將所有的結(jié)束位置標(biāo)為P位置。 2. 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。 3. 找出所有只能到達(dá)N位置的點(diǎn),將它們標(biāo)為P位置。 4. 如果在第三步中沒(méi)有找到新的被標(biāo)為P位置的點(diǎn),則算法結(jié)束,否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置,對(duì)于題目給出的任一初始位置,我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類(lèi):SG函數(shù)的應(yīng)用。 關(guān)于SG函數(shù)的基本知識(shí):對(duì)于一個(gè)有向圖(X, F)來(lái)說(shuō),SG函數(shù)g是一個(gè)在X上的函數(shù),并且它返回一個(gè)非負(fù)整數(shù)值,具體定義為 g(x)?min{n?0,n?g(y)對(duì)于所有y?F(x)} 1. 對(duì)于所有的結(jié)束位置x,g(x)= 0。 2. 對(duì)于每一個(gè)g(x)≠ 0的位置x,在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。 3.對(duì)于每一個(gè)g(x)= 0的位置x,所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。 定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值,i = 1,…,n,那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類(lèi):極大極小法。 典型題目:ZOJ 1155:Triangle War ZOJ 1993:A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O(logn)來(lái)求解遞推關(guān)系(最基本的就是求Fibonacci數(shù)列的某項(xiàng))和各種圖形變換,以及利用高斯消元法變成階梯矩陣。典型題目: 數(shù)學(xué)模型舉例 向量思想的應(yīng)用: UVA 10089:注意降維和向量的規(guī)范化 ; 利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。 UVA 10253: 遞推 數(shù)代集合 數(shù)代集合的思想: ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題:Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化,注意到題中有一句話(huà):“You may assume that the number H = |H| of elements of H?doesn't exceed 100”,這句話(huà)告訴我們H的元素個(gè)數(shù)不會(huì)超過(guò)100,因此可以考慮用一個(gè)數(shù)代替一個(gè)集合,首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來(lái),到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。 組合數(shù)學(xué) Polya定理則是解決同構(gòu)染色計(jì)數(shù)問(wèn)題的有力工具。 補(bǔ)集轉(zhuǎn)化思想 ZOJ 單色三角形: 字符串相關(guān) 擴(kuò)展的KMP算法應(yīng)用:;最長(zhǎng)回文串; 最長(zhǎng)公共子串; 最長(zhǎng)公共前綴; 填充問(wèn)題 高精度運(yùn)算 三維空間問(wèn)題專(zhuān)題 無(wú)論什么問(wèn)題,一旦擴(kuò)展到三難空間,就變得很有難度了。三維空間的問(wèn)題,很考代碼實(shí)現(xiàn)能力。 其它問(wèn)題的心得 解決一些判斷同構(gòu)問(wèn)題的方法:同構(gòu)的關(guān)鍵在于一一對(duì)應(yīng),而如果枚舉一一對(duì)應(yīng)的關(guān)系,時(shí)間復(fù)雜度相當(dāng)?shù)母撸米钚”硎?,就能把一個(gè)事物的本質(zhì)表示出來(lái)。求最小表示時(shí),我們一定要仔細(xì)分析,將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn),而且又不能主觀的加上其他條件。得到最小表示后,我們往往還要尋求適當(dāng)?shù)摹⒏咝У钠ヅ渌惴ǎɡ鏚MP字符匹配之類(lèi)的),來(lái)比較最小表示是否相同,這里常常要將我們熟悉的高效算法進(jìn)行推廣 源程序代碼: } 一、自然數(shù)拆分(遞歸) } #include 二、快速排序(遞歸)int a[100];void spilt(int t)#include 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); 三、刪數(shù)字(貪心) #include 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 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;} 五、多段圖(動(dòng)態(tài)規(guī)劃)#include “stdio.h” #define n 12 //圖的頂點(diǎn)數(shù) { while(from 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;//滿(mǎn)足條件就跳轉(zhuǎn) } } } 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 //圖的段數(shù) #define MAX 23767 int cost[n][n];//成本值數(shù)組 int path[k];//存儲(chǔ)最短路徑的數(shù)組 void creatgraph()//創(chuàng)建圖的(成本)鄰接矩陣 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//獲取成本矩陣數(shù)據(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;//起點(diǎn) path[k-1]=n-1;//最后的目標(biāo) for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//將最短路徑存入數(shù)組中 } //使用向后遞推算法求多段圖的最短路徑 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”);} 六、背包問(wè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 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 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);} 矩陣鏈乘法(動(dòng)態(tài)規(guī)劃)? 符號(hào)S[i, j]的意義: 符號(hào)S(i, j)表示,使得下列公式右邊取最小值的那個(gè)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的定義: 如果存在兩個(gè)正常數(shù)c和n0,對(duì)于所有的n≥n0時(shí),有: |f(n)|≤c|g(n)|,稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低,記為 f(n)=O(g(n))。計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù) Ω的定義: 如果存在正常數(shù)c和n0,對(duì)于所有n≥n0時(shí),有: |f(n)|≥c|g(n)|,則稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)下有界,且g(n)是它的一個(gè)下界,即f(n)的階不低于g(n)的階。記為: f(n)=Ω(g(n))。Θ的定義: 如果存在正常數(shù)c1,c2和n0,對(duì)于所有的n>n0,有: c1|g(n)|≤f(n)≤c2|g(n)|,則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。(1)多項(xiàng)式時(shí)間算法: O(1) (2)指數(shù)時(shí)間算法: O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 貪心方法基本思想: 貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮,它所作出的選擇只是在某種意義上的局部最優(yōu)選擇 所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇,即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 多段圖: COST[j]=c(j,r)+COST[r]; 回溯法: (假定集合Si的大小是mi)不斷地用修改過(guò)的規(guī)范函數(shù)Pi(x1,…,xi)去測(cè)試正在構(gòu)造中的n-元組的部分向量(x1,…,xi),看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1,…,xi)不可能導(dǎo)致最優(yōu)解,那么就將可能要測(cè)試的mi+1…mn個(gè)向量略去。約束條件: (1)顯式約束:限定每一個(gè)xi只能從給定的集合Si上取值。 (2)解 空 間:對(duì)于問(wèn)題的一個(gè)實(shí)例,解向量滿(mǎn)足顯式 約束條件的所有多元組,構(gòu)成了該實(shí)例 的一個(gè)解空間。 (3)隱式約束:規(guī)定解空間中實(shí)際上滿(mǎn)足規(guī)范函數(shù)的元 組,描述了xi必須彼此相關(guān)的情況?;咀龇ǎ?/p> 在問(wèn)題的解空間樹(shù)中,按深度優(yōu)先策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí),先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解:如果肯定不包含,則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索,逐層向其祖先結(jié)點(diǎn)回溯;否則,進(jìn)入該子樹(shù),繼續(xù)按深度優(yōu)先策略搜索。 8皇后問(wèn)題 約束條件 限界函數(shù): 子集和數(shù)問(wèn)題: 約束條件 限界函數(shù): 回溯法--術(shù)語(yǔ): 活結(jié)點(diǎn):已生成一個(gè)結(jié)點(diǎn)而它的所有兒子結(jié)點(diǎn)還沒(méi)有 全部生成的結(jié)點(diǎn)稱(chēng)為活結(jié)點(diǎn)。 E-結(jié)點(diǎn):當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫E-結(jié)點(diǎn)。 死結(jié)點(diǎn):不再進(jìn)一步擴(kuò)展或其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)稱(chēng)為死結(jié)點(diǎn)。 使用限界函數(shù)的深度優(yōu)先節(jié)點(diǎn)生成的方法成為回溯法;E-結(jié)點(diǎn)一直保持到死為止的狀態(tài)生成的方法 稱(chēng)之為分支限界方法 且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹(shù)的狀態(tài)空間的檢索方法。區(qū)別: 分支限界法本質(zhì)上就是含有剪枝的回溯法,根據(jù)遞歸的條件不同,是有不同的時(shí)間復(fù)雜度的。 回溯法深度優(yōu)先搜索堆棧或節(jié)點(diǎn)的所有子節(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿(mǎn)足約束條件的所有解 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列,優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿(mǎn)足約束條件下的一個(gè)解或特定意義下的最優(yōu)解 一般如果只考慮時(shí)間復(fù)雜度二者都是指數(shù)級(jí)別的 可是因?yàn)榉种藿绶ù嬖谥鞣N剪枝,用起來(lái)時(shí)間還是很快的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是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題的集合 如果可滿(mǎn)足星月化為一個(gè)問(wèn)題L,則此問(wèn)題L是NP-難度的。如果L是NP難度的且L NP,則此問(wèn)題是NP-完全的第五篇:算法總結(jié)材料