第一篇：分類算法總結

分類算法

數(shù)據(jù)挖掘中有很多領域，分類就是其中之一，什么是分類，分類就是把一些新得數(shù)據(jù)項映射到給定類別的中的某一個類別，比如說當我們發(fā)表一篇文章的時候，就可以自動的把這篇文章劃分到某一個文章類別，一般的過程是根據(jù)樣本數(shù)據(jù)利用一定的分類算法得到分類規(guī)則，新的數(shù)據(jù)過來就依據(jù)該規(guī)則進行類別的劃分。

分類在數(shù)據(jù)挖掘中是一項非常重要的任務，有很多用途，比如說預測，即從歷史的樣本數(shù)據(jù)推算出未來數(shù)據(jù)的趨向，有一個比較著名的預測的例子就是大豆學習。再比如說分析用戶行為，我們常稱之為受眾分析，通過這種分類，我們可以得知某一商品的用戶群，對銷售來說有很大的幫助。

分類器的構造方法有統(tǒng)計方法，機器學習方法，神經(jīng)網(wǎng)絡方法等等。常見的統(tǒng)計方法有knn算法，基于事例的學習方法。機器學習方法包括決策樹法和歸納法，上面講到的受眾分析可以使用決策樹方法來實現(xiàn)。神經(jīng)網(wǎng)絡方法主要是bp算法，這個俺也不太了解。文本分類，所謂的文本分類就是把文本進行歸類，不同的文章根據(jù)文章的內容應該屬于不同的類別，文本分類離不開分詞，要將一個文本進行分類，首先需要對該文本進行分詞，利用分詞之后的的項向量作為計算因子，再使用一定的算法和樣本中的詞匯進行計算，從而可以得出正確的分類結果。在這個例子中，我將使用庖丁分詞器對文本進行分詞。目前看到的比較全面的分類算法,總結的還不錯.2.4.1 主要分類方法介紹解決分類問題的方法很多[40-42]，單一的分類方法主要包括：決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡、K-近鄰、支持向量機和基于關聯(lián)規(guī)則的分類等；另外還有用于組合單一分類方法的集成學習算法，如Bagging和Boosting等。（1）決策樹

決策樹是用于分類和預測的主要技術之一，決策樹學習是以實例為基礎的歸納學習算法，它著眼于從一組無次序、無規(guī)則的實例中推理出以決策樹表示的分類規(guī)則。構造決策樹的目的是找出屬性和類別間的關系，用它來預測將來未知類別的記錄的類別。它采用自頂向下的遞歸方式，在決策樹的內部節(jié)點進行屬性的比較，并根據(jù)不同屬性值判斷從該節(jié)點向下的分支，在決策樹的葉節(jié)點得到結論。

主要的決策樹算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它們在選擇測試屬性采用的技術、生成的決策樹的結構、剪枝的方法以及時刻，能否處理大數(shù)據(jù)集等方面都有各自的不同之處。（2）貝葉斯 貝葉斯（Bayes）分類算法是一類利用概率統(tǒng)計知識進行分類的算法，如樸素貝葉斯（Naive Bayes）算法。這些算法主要利用Bayes定理來預測一個未知類別的樣本屬于各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。由于貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經(jīng)常是不成立的，因而其分類準確性就會下降。為此就出現(xiàn)了許多降低獨立性假設的貝葉斯分類算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在貝葉斯網(wǎng)絡結構的基礎上增加屬性對之間的關聯(lián)來實現(xiàn)的。

（3）人工神經(jīng)網(wǎng)絡

人工神經(jīng)網(wǎng)絡（Artificial Neural Networks，ANN）是一種應用類似于大腦神經(jīng)突觸聯(lián)接的結構進行信息處理的數(shù)學模型。在這種模型中，大量的節(jié)點（或稱”神經(jīng)元”，或”單元”）之間相互聯(lián)接構成網(wǎng)絡，即”神經(jīng)網(wǎng)絡”，以達到處理信息的目的。神經(jīng)網(wǎng)絡通常需要進行訓練，訓練的過程就是網(wǎng)絡進行學習的過程。訓練改變了網(wǎng)絡節(jié)點的連接權的值使其具有分類的功能，經(jīng)過訓練的網(wǎng)絡就可用于對象的識別。目前，神經(jīng)網(wǎng)絡已有上百種不同的模型，常見的有BP網(wǎng)絡、徑向基RBF網(wǎng)絡、Hopfield網(wǎng)絡、隨機神經(jīng)網(wǎng)絡（Boltzmann機）、競爭神經(jīng)網(wǎng)絡（Hamming網(wǎng)絡，自組織映射網(wǎng)絡）等。但是當前的神經(jīng)網(wǎng)絡仍普遍存在收斂速度慢、計算量大、訓練時間長和不可解釋等缺點。（4）k-近鄰

k-近鄰(kNN，k-Nearest Neighbors)算法是一種基于實例的分類方法。該方法就是找出與未知樣本x距離最近的k個訓練樣本，看這k個樣本中多數(shù)屬于哪一類，就把x歸為那一類。k-近鄰方法是一種懶惰學習方法，它存放樣本，直到需要分類時才進行分類，如果樣本集比較復雜，可能會導致很大的計算開銷，因此無法應用到實時性很強的場合。（5）支持向量機

支持向量機（SVM，Support Vector Machine）是Vapnik根據(jù)統(tǒng)計學習理論提出的一種新的學習方法[43]，它的最大特點是根據(jù)結構風險最小化準則，以最大化分類間隔構造最優(yōu)分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數(shù)、局部極小點等問題。對于分類問題，支持向量機算法根據(jù)區(qū)域中的樣本計算該區(qū)域的決策曲面，由此確定該區(qū)域中未知樣本的類別。

（6）基于關聯(lián)規(guī)則的分類

關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個重要的研究領域。近年來，對于如何將關聯(lián)規(guī)則挖掘用于分類問題，學者們進行了廣泛的研究。關聯(lián)分類方法挖掘形如condset→C的規(guī)則，其中condset是項(或屬性-值對)的集合，而C是類標號，這種形式的規(guī)則稱為類關聯(lián)規(guī)則（class association rules，CARS）。關聯(lián)分類方法一般由兩步組成：第一步用關聯(lián)規(guī)則挖掘算法從訓練數(shù)據(jù)集中挖掘出所有滿足指定支持度和置信度的類關聯(lián)規(guī)則；第二步使用啟發(fā)式方法從挖掘出的類關聯(lián)規(guī)則中挑選出一組高質量的規(guī)則用于分類。屬于關聯(lián)分類的算法主要包括CBA[44]，ADT[45]，CMAR[46] 等。（7）集成學習（Ensemble Learning）

實際應用的復雜性和數(shù)據(jù)的多樣性往往使得單一的分類方法不夠有效。因此，學者們對多種分類方法的融合即集成學習進行了廣泛的研究。集成學習已成為國際機器學習界的研究熱點，并被稱為當前機器學習四個主要研究方向之一。集成學習是一種機器學習范式，它試圖通過連續(xù)調用單個的學習算法，獲得不同的基學習器，然后根據(jù)規(guī)則組合這些學習器來解決同一個問題，可以顯著的提高學習系統(tǒng)的泛化能力。組合多個基學習器主要采用（加權）投票的方法，常見的算法有裝袋[47]（Bagging），提升/推進[48, 49]（Boosting）等。

有關分類器的集成學習見圖2-5。集成學習由于采用了投票平均的方法組合多個分類器，所以有可能減少單個分類器的誤差，獲得對問題空間模型更加準確的表示，從而提高分類器的分類準確度。

圖2-5：分類器的集成學習

以上簡單介紹了各種主要的分類方法，應該說其都有各自不同的特點及優(yōu)缺點。對于數(shù)據(jù)庫負載的自動識別，應該選擇哪種方法呢？用來比較和評估分類方法的標準[50] 主要有：（1）預測的準確率。模型正確地預測新樣本的類標號的能力；（2）計算速度。包括構造模型以及使用模型進行分類的時間；（3）強壯性。模型對噪聲數(shù)據(jù)或空缺值數(shù)據(jù)正確預測的能力；（4）可伸縮性。對于數(shù)據(jù)量很大的數(shù)據(jù)集，有效構造模型的能力；（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易理解，則愈受歡迎。

最初的數(shù)據(jù)挖掘分類應用大多都是在這些方法及基于內存基礎上所構造的算法。目前數(shù)據(jù)挖掘方法都要求具有基于外存以處理大規(guī)模數(shù)據(jù)集合能力且具有可擴展能力。下面對幾種主要的分類方法做個簡要介紹：

（1）決策樹

決策樹歸納是經(jīng)典的分類算法。它采用自頂向下遞歸的各個擊破方式構造決策樹。樹的每一個結點上使用信息增益度量選擇測試屬性?？梢詮纳傻臎Q策樹中提取規(guī)則。

(2)KNN法(K-Nearest Neighbor)

KNN法即K最近鄰法，最初由Cover和Hart于1968年提出的，是一個理論上比較成熟的方法。該方法的思路非常簡單直觀：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計算復雜度，提高分類的效率。

該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

(3)SVM法

SVM法即支持向量機(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相對優(yōu)良的性能指標。該方法是建立在統(tǒng)計學習理論基礎上的機器學習方法。通過學習算法，SVM可以自動尋找出那些對分類有較好區(qū)分能力的支持向量，由此構造出的分類器可以最大化類與類的間隔，因而有較好的適應能力和較高的分準率。該方法只需要由各類域的邊界樣本的類別來決定最后的分類結果。

支持向量機算法的目的在于尋找一個超平面H(d),該超平面可以將訓練集中的數(shù)據(jù)分開，且與類域邊界的沿垂直于該超平面方向的距離最大，故SVM法亦被稱為最大邊緣(maximum margin)算法。待分樣本集中的大部分樣本不是支持向量，移去或者減少這些樣本對分類結果沒有影響，SVM法對小樣本情況下的自動分類有著較好的分類結果。

(4)VSM法

VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數(shù)學模型。其基本思想是將文檔表示為加權的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通過計算文本相似度的方法來確定待分樣本的類別。當文本被表示為空間向量模型的時候，文本的相似度就可以借助特征向量之間的內積來表示。

在實際應用中，VSM法一般事先依據(jù)語料庫中的訓練樣本和分類體系建立類別向量空間。當需要對一篇待分樣本進行分類的時候，只需要計算待分樣本和每一個類別向量的相似度即內積，然后選取相似度最大的類別作為該待分樣本所對應的類別。

由于VSM法中需要事先計算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項。根據(jù)研究發(fā)現(xiàn)，類別中所包含的非零特征項越多，其包含的每個特征項對于類別的表達能力越弱。因此，VSM法相對其他分類方法而言，更適合于專業(yè)文獻的分類。

(5)Bayes法

Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法，待分樣本的分類結果取決于各類域中樣本的全體。

設訓練樣本集分為M類，記為C=｛c1，…，ci，…cM}，每類的先驗概率為P(ci)，i=1，2，…，M。當樣本集非常大時，可以認為P(ci)=ci類樣本數(shù)/總樣本數(shù)。對于一個待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類的后驗概率P(ci/X)：

P(ci/x)=P(x/ci)?P(ci)/P(x)(1)若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，則有x∈ci(2)式(2)是最大后驗概率判決準則，將式(1)代入式(2)，則有：

若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，則x∈ci 這就是常用到的Bayes分類判決準則。經(jīng)過長期的研究，Bayes分類方法在理論上論證得比較充分，在應用上也是非常廣泛的。

Bayes方法的薄弱環(huán)節(jié)在于實際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)(或密度函數(shù))常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達文本的主題詞相互獨立，這樣的條件在實際文本中一般很難滿足，因此該方法往往在效果上難以達到理論上的最大值。

（6）神經(jīng)網(wǎng)絡

神經(jīng)網(wǎng)絡分類算法的重點是構造閾值邏輯單元，一個值邏輯單元是一個對象，它可以輸入一組加權系數(shù)的量，對它們進行求和，如果這個和達到或者超過了某個閾值，輸出一個量。如有輸入值X1, X2,..., Xn和它們的權系數(shù)：W1, W2,...,Wn，求和計算出的 Xi*Wi，產(chǎn)生了激發(fā)層 a =(X1 * W1)+(X2 * W2)+...+(Xi * Wi)+...+(Xn * Wn)，其中Xi 是各條記錄出現(xiàn)頻率或其他參數(shù)，Wi是實時特征評估模型中得到的權系數(shù)。神經(jīng)網(wǎng)絡是基于經(jīng)驗風險最小化原則的學習算法，有一些固有的缺陷，比如層數(shù)和神經(jīng)元個數(shù)難以確定，容易陷入局部極小，還有過學習現(xiàn)象，這些本身的缺陷在SVM算法中可以得到很好的解決。

第二篇：音頻分類總結(算法綜述)

總結音頻分類的算法

剛開始對音頻分割還有特征提取有些自己的想法，感覺應該能夠分清楚，但是當開始查閱文獻的時候，發(fā)現(xiàn)對他們兩個的概念越來越模糊。很多時候他們是重疊的。后來我在一篇文獻里找到這句話。覺得應該是這個道理：

音頻數(shù)據(jù)的分類是一個模式識別的問題，它包括兩個基本方面：特征選擇和分類。

音頻分割是在音頻分類的基礎上從音頻流中提取出不同的音頻類別，也就是說在時間軸上對音頻流按類別進行劃分。分類是分割的前提和基礎。對音頻流的準確分割是最終的目的。

于是我找了一下比較典型的分類算法

比較典型的音頻分類算法包括最小距離方法、支持向量機、神經(jīng)網(wǎng)絡、決策樹方法和隱馬爾可夫模型方法等。

1．最小距離法。(典型的音頻分類算法)最小距離分類法的優(yōu)點是概念直觀，方法簡單，有利于建立多維空間分類方法的幾何概念。在音頻分類中應用的最小距離分類法有k近鄰(k—Nearest Neighbor，簡稱K—NN)方法和最近特征線方法(Nearest Feature，簡稱NFL))等。

k近鄰方法的思想是根據(jù)未知樣本X最近鄰的k個樣本點的類別來確定X的類別。為此，需要計算X與所有樣本x。的距離d(x，x。)，并且從中選出最小的k個樣本作為近鄰樣本集合KNN，計算其中所有屬于類別Wj的距離之和，并且按照以下判別規(guī)則進行分類：?C(x)?argminC?{W1,...,Wn}

?d(x,xi),其中，C為類別集合由于k近鄰方法利用了更多的樣本信息確定它的類別，k取大一些有利于減少噪聲的影響。但是由于k近鄰方法中需要計算所有樣本的距離，因此當樣本數(shù)目非常大的時候，計算量就相當可觀。取k=l時，k近鄰方法就退化為最近鄰方法。

最近特征線方法是從每一類的樣本子空間中選取一些原型(Prototype)特征點，這些特征點的兩兩連線稱為特征線(Feature Line)，這些特征線的集合用來表示原先每一類的樣本子空間。

設類C的原型特征點集合:,其中Nc為類C的原型特征點數(shù)目，則對應的特征線的數(shù)目為Sc，而類C的特征線集合

{|XicXjc|1?i,j?Nc，i?j} i≠jl構成類C的特征線空間，它是類C的特征子空間。—般所選取的原型特征點的數(shù)目比較少，因此特征線的數(shù)目也比較少。未知樣本X與特征線XicXjc的距離定義為x在XicXjc上的投影距離，如圖4所示，而X與類別C的距離為X與類C的特征線空間中的所有特征線的最短距離。

2．神經(jīng)網(wǎng)絡(Neural Network)。

在使用神經(jīng)網(wǎng)絡進行音頻分類時，可以令輸入層的節(jié)點與音頻的特征向量相對應，而輸出層的節(jié)點對應于類別Ci。，如圖5所示。在訓練時，通過對訓練樣本集中的樣本進行反復學習來調節(jié)網(wǎng)絡，從而使全局誤差函數(shù)取得最小值。這樣，就可以期望該網(wǎng)絡能夠對新輸入的待分類樣本T輸出正確的分類Ci。

3．支持向量機(support Vector Machine，簡稱為SVM)。

支持向量機是Vapnik等人提出的以結構風險最小化原理(Stuctural Risk Minimization Principle)為基礎的分類方法。該方法最初來自于對二值分類問題的處理，其機理是在樣本空間中尋找—個將訓練集中的正例和反例兩類樣本點分割開來的分類超平面，并取得最大邊緣(正樣本與負樣本到超平面的最小距離)，如圖6所示。該方法根據(jù)核空間理論將低維的輸入空間數(shù)據(jù)通過某種非線性函數(shù)(即核函數(shù))映射到—個高維空間中，并且線性判決只需要在高維空間中進行內積運算，從而解決了線性不可分的分類問題。

根據(jù)不同的分類問題，可以選用不同的核函數(shù)，常用的核函數(shù)有三種：

① 項式核函數(shù):

② 徑向基核函數(shù):

③ Sigmoid核函數(shù)：

SVM訓練算法主要有三類：二次規(guī)劃算法，分解算法，增量算法。

4．決策樹方法

決策樹是一種結構簡單、搜索效率高的分類器。這類方法以信息論為基礎，對大量的實例選擇重要的特征建立決策樹，如圖7所示。

最優(yōu)決策樹的構造是一個NP完全(NPComepleteness)問題，其設計原則可以形式化地表示為

其中T為特定的決策樹結構，F(xiàn)和d分別為分枝結,為在數(shù)據(jù)集合點的特征子集和決策規(guī)則，D為所有的訓練數(shù)據(jù)，D上選取特征集合F和決策規(guī)則d訓練得到的結構為T的決策樹的分類錯誤?的條件概率。因此，決策樹的構造過程可以分為三個問題：選取合適的結構，為分枝結點選取合適的特征子集和決策規(guī)則。常用的決策樹構造方法有非回溯的貪心(Greedy)算法和梯度上升算法。

5.隱馬爾可夫模型(Hidden Markov Model，簡HMM)方法。

隱馬爾可夫模型(HMM)的音頻分類性能較好，它的分類對象是語音(speech)、音樂(music)以及語音和音樂的混合(speech+music)共3類數(shù)據(jù)，根據(jù)極大似然準則判定它們的類別，最優(yōu)分類精度可達90.28％。

HMM本質上是一種雙重隨機過程的有限狀態(tài)自動機(stochastic finite-state automata)，它具有刻畫信號的時間統(tǒng)計特性的能力。雙重隨機過程是指滿足Markov分布的狀態(tài)轉換Markov鏈以及每一狀態(tài)的觀察輸出概率密度函數(shù)，共兩個隨機過程。HMM可以用3元組來表示：入；(A，B，?)，其中A是狀態(tài)Si到Sj的轉換概率矩陣，B是狀態(tài)的觀察輸出概率密度，?是狀態(tài)的初始分布概率。

第三篇：2018高考分類-算法

（2018北京3）.執(zhí)行如圖所示的程序框圖，輸出的s值為 A.B.C.D.，設計了下面的程序框圖，則在空白框中應填入

D.（2018全國2）7.為計算A.B.C.（2018北京3）

（2018全國2）

（2018天津3）.閱讀右邊的程序框圖，運行相應的程序，若輸入N的值為20，則輸出T的值為

A.1

B.2

C.3

D.4

（2018江蘇）4.一個算法的偽代碼如圖所示，執(zhí)行此算法，最后輸出的S的值為________．

（2018江蘇）

（2018天津3）

第四篇：算法總結

算法分析與設計總結報告

71110415 錢玉明

在計算機軟件專業(yè)中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結構這個公式。算法的學習對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學生，學習算法無疑會增強自己的競爭力，修煉自己的“內功”。

下面我將談談我對這門課程的心得與體會。

一、數(shù)學是算法的基礎

經(jīng)過這門課的學習，我深刻的領悟到數(shù)學是一切算法分析與設計的基礎。這門課的很多時間多花在了數(shù)學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學息息相關。其中有幾個定理令我印象深刻。

①主定理

本門課中它主要應用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關結論進行分析處理。當f(n)量級高于nlogba時，我們可以設法降低子問題組合時的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴大問題的規(guī)?；蛘邷p小子問題的個數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。

②隨機算法中的許多定理的運用

在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數(shù)判定定理是個很明顯的例子。它運用了包括費馬小定理在內的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數(shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進的依據(jù)，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數(shù)學定理的運用上。

這些算法都給予了我很大啟發(fā)，要想學好算法，學好數(shù)學是必不可少的。沒有深厚的數(shù)學功力作為地基，即使再漂亮的算法框架，代碼實現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學習這門課不是僅僅掌握那幾個經(jīng)典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個星期?，F(xiàn)在用10只老鼠在一個星期內判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。

①算法最基本的設計方法包括分治法，動態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨立的子問題，關鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結果。如構造最優(yōu)二叉查找樹，解決矩陣連乘時最小計算次數(shù)問題，尋找最長公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應用就是解決整數(shù)規(guī)劃問題。

②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計。

這幾種方法都是平攤分析法，平攤分析的實質就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。

三、算法與應用緊密相關

我認為學習算法不能局限于書本上的理論運算，局限于如何提高性能以降低復雜度，我們要將它與實際生活聯(lián)系起來。其實算法問題的產(chǎn)生就來自于生活，設計出高效的算法就是為了更好的應用。如尋找最長公共子序列算法可以應用在生物信息學中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個字符串的相近性，這可應用在數(shù)據(jù)挖掘中?？焖俑盗⑷~變換（FFT）可應用在計算多項式相乘上來降低復雜度，脫線min算法就是利用了Union-Find這種結構。還有圖中相關算法，它對于解決網(wǎng)絡流量分配問題起了很大的幫助，等等。

這些應用給了我很大的啟發(fā)：因為單純講一個Union-Find算法，即使了解了它的實現(xiàn)原理，遇到具體的實際問題也不知去如何應用。這就要求我們要將自己學到的算法要和實際問題結合起來，不能停留在思想方法階段，要學以致用，做到具體問題具體分析。

四、對計算模型和NP問題的理解

由于對這部分內容不是很理解，所以就粗淺的談一下我的看法。

首先談到計算模型，就不得不提到圖靈計算，他將基本的計算抽象化，造出一個圖靈機，得出了計算的本質。并提出圖靈機可以計算的問題都是可以計算的，否則就是不可計算的。由此引申出一個著名論題：任何合理的計算模型都是相互等價的。它說明了可計算性本身不依賴于任何具體的模型而客觀存在。

NP問題比較復雜，我認為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個特殊的性質，如果存在一個NP-C問題找到一個多項式時間的解法，則所有的NP-C問題都能找到多項式時間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時可以找出精確解，但是規(guī)模大時，就因時間太復雜而找不到最優(yōu)解。此時一般會采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項式時間的算法，如漢諾塔問題。

最后談談對這門課程的建議

①對于這門算法課，我認為應該加強對算法思想方法的學習。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會兒，或者給出個獎勵機制，誰能解決這個問題，平時成績加分。這在一定程度上會將強我們思考分析問題的能力。因為我感覺到，一個問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點名回答問題可以一定程度上有效的防止不認真聽課的現(xiàn)象。

②作業(yè)安排的不是很恰當。本門課主要安排了三次作業(yè)，個人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實現(xiàn)一下偽代碼，沒有太多的技術含量。而且對于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因為這間接成為了程序設計題，不是算法設計題。

③本門課的時間安排的不太恰當，因為本學期的課程太多，壓力太大。沒有太多的時間去學習這門課程。因為我相信大家都對它感興趣，比較重視，想花功夫，但苦于沒時間。所以可不可以將課程提前一個學期，那時候離散數(shù)學也已經(jīng)學過，且課程的壓力也不是很大。錯開時間的話，我覺得應該能夠更好提高大家算法分析設計的能力。

第五篇：算法總結

算法分塊總結

為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個全面詳細的總結，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設法進行模型簡化，轉化，轉化成我們熟悉的東西。

圖論模型的應用

分層圖思想的應用：

用此思想可以建立起更簡潔、嚴謹?shù)臄?shù)學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結果都是相同的。所以我們只需對這些計算進行一次，把結果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規(guī)模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎。

這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優(yōu)匹配的應用：

最大網(wǎng)絡流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用：

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

歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹：

求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹：

抽象成數(shù)學模型就是：

設G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數(shù)。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現(xiàn)m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k

首先，將 v0和與之關聯(lián)的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉化成以v0為根的有根樹。

假設已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關聯(lián)的邊后，必定形成一個環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關聯(lián)的邊。刪去的邊的權值越大，則所得到的生成樹的權值和就越小。動態(tài)規(guī)劃就有了用武之地。設Best(v)為路徑v0—v上與v0無關聯(lián)且權值最大的邊。定義father(v)為v的父結點，動態(tài)轉移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

狀態(tài)共|V|個，狀態(tài)轉移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹；

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

加邊和去邊過程，利用動態(tài)規(guī)劃優(yōu)化特別值得注意。

次小生成樹：

加邊和去邊很值得注意。

每加入一條不在樹上的邊，總能形成一個環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。具體做法：

首先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環(huán)上的權值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。

最短路徑的應用：

Dijkstra 算法應用： Folyed 算法應用：

Bellman-Ford 算法的應用：

差分約束系統(tǒng)的應用：

搜索算法

搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個較優(yōu)的搜索出發(fā)點，凡是能用高效算法的地方盡量爭取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用：

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

部分搜索+高效算法（比如二分匹配，動態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索：

可行性剪枝，最優(yōu)性剪枝，調整搜索順序是常用的優(yōu)化手段。

動態(tài)規(guī)劃

動態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉移方程，另外還要考慮高效的預處理（以便更好更快的實現(xiàn)狀態(tài)轉移）。最常用的思想就是用枚舉最后一次操作。

狀態(tài)壓縮DP，又叫帶集合的動態(tài)規(guī)劃：題目特點是有一維的維數(shù)特別小。類似TSP問題的DP：

狀態(tài)劃分比較困難的題目： 樹形DP：

四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2)

高檔數(shù)據(jù)結構的應用

并查集的應用：

巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用：

總結用線段樹解題的方法

根據(jù)題目要求將一個區(qū)間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個點、線段、或數(shù)組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等

樹的每個節(jié)點根據(jù)題目所需，設置變量記錄要求的值

用樹形結構來維護這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時，都只對O(logL)個節(jié)點修改這個特點，在O(logL)的時間內維護修改后相關節(jié)點的變量。

在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運用子樹的收縮與葉子節(jié)點的釋放，避免重復操作。

Trie的應用：；

Trie圖的應用探索： 后綴數(shù)組的應用研究：

在字符串處理當中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關于后綴數(shù)組則很少見于國內的資料。其實后綴數(shù)組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現(xiàn)，能夠實現(xiàn)后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。

樹狀數(shù)組的應用探索：；

計算幾何

掌握基本算法的實現(xiàn)。凸包的應用：；

半平面交算法的應用：；

幾何+模擬類題目：幾何設計好算法，模擬控制好精度。掃描法：；

轉化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉化為求多邊形的面積。離散法思想的應用：；

經(jīng)典算法：找平面上的最近點對。

貪心

矩形切割

二分思想應用

活用經(jīng)典算法

利用歸并排序算法思想求數(shù)列的逆序對數(shù)：

利用快速排序算法思想，查詢N個數(shù)中的第K小數(shù)：

博弈問題

博弈類題目通常用三類解法：第一類推結論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。

第一類：推結論。典型題目： 第二類：遞推。典型題目：

比如有向無環(huán)圖類型的博弈。在一個有向圖中，我們把選手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函數(shù)的應用。

關于SG函數(shù)的基本知識：對于一個有向圖(X, F)來說，SG函數(shù)g是一個在X上的函數(shù)，并且它返回一個非負整數(shù)值，具體定義為

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函數(shù)值，i = 1,…,n，那么在由這n個有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四類：極大極小法。

典型題目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩陣妙用

矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關系（最基本的就是求Fibonacci數(shù)列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

數(shù)學模型舉例

向量思想的應用：

UVA 10089：注意降維和向量的規(guī)范化 ；

利用復數(shù)思想進行向量旋轉。

UVA 10253：

遞推

數(shù)代集合

數(shù)代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個數(shù)不會超過100，因此可以考慮用一個數(shù)代替一個集合，首先把所有的運算結果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。

組合數(shù)學

Polya定理則是解決同構染色計數(shù)問題的有力工具。

補集轉化思想

ZOJ 單色三角形：

字符串相關

擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴；

填充問題

高精度運算

三維空間問題專題

無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現(xiàn)能力。

其它問題的心得

解決一些判斷同構問題的方法：同構的關鍵在于一一對應，而如果枚舉一一對應的關系，時間復雜度相當?shù)母撸米钚”硎?，就能把一個事物的本質表示出來。求最小表示時，我們一定要仔細分析，將一切能區(qū)分兩個元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當?shù)?、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣