第一篇：人工智能十大算法總結(jié)

5-1 簡述機器學(xué)習(xí)十大算法的每個算法的核心思想、工作原理、適用 情況及優(yōu)缺點等。1）C4.5 算法：

ID3 算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實現(xiàn)對數(shù)據(jù)的歸納分類。ID3 算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定的測試屬性。C4.5 算法核心思想是ID3 算法，是ID3 算法的改進，改進方面有： 1）用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足； 2）在樹構(gòu)造過程中進行剪枝 3）能處理非離散的數(shù)據(jù) 4）能處理不完整的數(shù)據(jù)

C4.5 算法優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。缺點：

1)在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。2)C4.5 只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。2）K means 算法：

是一個簡單的聚類算法，把n 的對象根據(jù)他們的屬性分為k 個分割，k < n。算法的核心就是要優(yōu)化失真函數(shù)J,使其收斂到局部最小值但不是全局最小值。

其中N 為樣本數(shù)，K 是簇數(shù)，rnk b 表示n 屬于第k 個簇，uk 是第k 個中心點的值。然后求出最優(yōu)的uk

優(yōu)點：算法速度很快

缺點是，分組的數(shù)目k 是一個輸入?yún)?shù)，不合適的k 可能返回較差的結(jié)果。

3）樸素貝葉斯算法：

樸素貝葉斯法是基于貝葉斯定理與特征條件獨立假設(shè)的分類方法。算法的基礎(chǔ)是概率問題，分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。樸素貝葉斯假設(shè)是約束 性很強的假設(shè)，假設(shè)特征條件獨立，但樸素貝葉斯算法簡單，快速，具有較小的出錯率。在樸素貝葉斯的應(yīng)用中，主要研究了電子郵件過濾以及文本分類研究。

4)K 最近鄰分類算法（KNN）

分類思想比較簡單，從訓(xùn)練樣本中找出K個與其最相近的樣本，然后看這k個樣本中哪個類別的樣本多，則待判定的值（或說抽樣）就屬于這個類別。缺點：

1）K 值需要預(yù)先設(shè)定，而不能自適應(yīng)

2）當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K 個鄰居中大容量類的樣本占多數(shù)。

該算法適用于對樣本容量比較大的類域進行自動分類。

5)EM 最大期望算法

EM 算法是基于模型的聚類方法，是在概率模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量。E步估計隱含變量，M步估計其他參數(shù)，交替將極值推向最大。EM 算法比K-means 算法計算復(fù)雜，收斂也較慢，不適于大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)，但比K-means 算法計算結(jié)果穩(wěn)定、準(zhǔn)確。EM 經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)集聚（Data Clustering）領(lǐng)域。

6）PageRank 算法

是google 的頁面排序算法，是基于從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁的回歸關(guān)系，來判定所有網(wǎng)頁的重要性。（也就是說，一個人有著越多牛X 朋友的人，他是牛X 的概率就越大。）優(yōu)點：完全獨立于查詢，只依賴于網(wǎng)頁鏈接結(jié)構(gòu)，可以離線計算。缺點：1）PageRank 算法忽略了網(wǎng)頁搜索的時效性。

2）舊網(wǎng)頁排序很高，存在時間長，積累了大量的in-links，擁有最新資訊的新網(wǎng)頁排名卻很低，因為它們幾乎沒有in-links。

7)AdaBoost Adaboost 是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。整個過程如下所示：

1.先通過對N 個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器；

2.將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N 個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器； 3.將和都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器； 4.如此反復(fù)，最終得到經(jīng)過提升的強分類器。

目前AdaBoost 算法廣泛的應(yīng)用于人臉檢測、目標(biāo)識別等領(lǐng)域。

8）Apriori 算法

Apriori 算法是一種挖掘關(guān)聯(lián)規(guī)則的算法，用于挖掘其內(nèi)含的、未知的卻又實際存在的數(shù)據(jù)關(guān)系，其核心是基于兩階段頻集思想的遞推算法。Apriori 算法分為兩個階段：1）尋找頻繁項集

2）由頻繁項集找關(guān)聯(lián)規(guī)則

算法缺點：

1）在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；

2）每次計算項集的支持度時，都對數(shù)據(jù)庫中的全部記錄進行了一遍掃描比較，需要很大的I/O 負(fù)載。9）SVM 支持向量機

支持向量機是一種基于分類邊界的方法。其基本原理是（以二維數(shù)據(jù)為例）：如果訓(xùn)練數(shù)據(jù)分布在二維平面上的點，它們按照其分類聚集在不同的區(qū)域。基于分類邊界的分類算法的目標(biāo)是，通過訓(xùn)練，找到這些分類之間的邊界（直線的――稱為線性劃分，曲線的――稱

為非線性劃分）。對于多維數(shù)據(jù)（如N 維），可以將它們視為N 維空間中的點，而分類邊界就是N 維空間中的面，稱為超面（超面比N維空間少一維）。線性分類器使用超平面類型的邊界，非線性分類器使用超曲面。

支持向量機的原理是將低維空間的點映射到高維空間，使它們成為線性可分，再使用線性劃分的原理來判斷分類邊界。在高維空間中是一種線性劃分，而在原有的數(shù)據(jù)空間中，是一種非線性劃分。SVM 在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習(xí)問題中。10）CART 分類與回歸樹

是一種決策樹分類方法，采用基于最小距離的基尼指數(shù)估計函數(shù)，用來決定由該子數(shù)據(jù)集生成的決策樹的拓展形。如果目標(biāo)變量是標(biāo)稱的，稱為分類樹；如果目標(biāo)變量是連續(xù)的，稱為回歸樹。分類樹是使用樹結(jié)構(gòu)算法將數(shù)據(jù)分成離散類的方法。優(yōu)點

1）非常靈活，可以允許有部分錯分成本，還可指定先驗概率分布，可使用自動的成本復(fù)雜性剪枝來得到歸納性更強的樹。2）在面對諸如存在缺失值、變量數(shù)多等問題時CART 顯得非常穩(wěn)健。

第二篇：算法總結(jié)

算法分析與設(shè)計總結(jié)報告

71110415 錢玉明

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

下面我將談?wù)勎覍@門課程的心得與體會。

一、數(shù)學(xué)是算法的基礎(chǔ)

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

①主定理

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

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

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

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

二、算法的核心是思想

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

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

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

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

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

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

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

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

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

三、算法與應(yīng)用緊密相關(guān)

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

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

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

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

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

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

最后談?wù)剬@門課程的建議

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

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

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

第三篇：算法總結(jié)

算法分塊總結(jié)

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

圖論模型的應(yīng)用

分層圖思想的應(yīng)用：

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

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

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

容量有上下界的最大流的應(yīng)用：

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

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

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

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

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

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

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

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

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

次小生成樹：

加邊和去邊很值得注意。

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

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

最短路徑的應(yīng)用：

Dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用：

Bellman-Ford 算法的應(yīng)用：

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

搜索算法

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

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

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

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

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

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

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

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

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

高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

并查集的應(yīng)用：

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

總結(jié)用線段樹解題的方法

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

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

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

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

Trie的應(yīng)用：；

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

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

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

計算幾何

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

半平面交算法的應(yīng)用：；

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

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

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

貪心

矩形切割

二分思想應(yīng)用

活用經(jīng)典算法

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

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

博弈問題

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

第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目：

比如有向無環(huán)圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)：

1． 所有的結(jié)束位置都是P位置。

2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。

這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結(jié)束位置（結(jié)束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。

與此同時，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為：

1． 將所有的結(jié)束位置標(biāo)為P位置。

2． 將所有能一步到達P位置的點標(biāo)為N位置。

3． 找出所有只能到達N位置的點，將它們標(biāo)為P位置。

4． 如果在第三步中沒有找到新的被標(biāo)為P位置的點，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應(yīng)用。

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

g(x)?min{n?0,n?g(y)對于所有y?F(x)}

1． 對于所有的結(jié)束位置x，g(x)= 0。

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

3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(shù)(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）來求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

數(shù)學(xué)模型舉例

向量思想的應(yīng)用：

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

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

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ù)代替一個集合，首先把所有的運算結(jié)果都用預(yù)處理算出來，到計算的時候只要用O(1)的復(fù)雜度就可以完成一次運算。

組合數(shù)學(xué)

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

補集轉(zhuǎn)化思想

ZOJ 單色三角形：

字符串相關(guān)

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

填充問題

高精度運算

三維空間問題專題

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

其它問題的心得

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

第四篇：算法總結(jié)材料

源程序代碼：

}

一、自然數(shù)拆分（遞歸）

} #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);

三、刪數(shù)字（貪心）

#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;}

五、多段圖（動態(tài)規(guī)劃）#include “stdio.h”

#define n 12 //圖的頂點數(shù)

{ 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;//滿足條件就跳轉(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];//存儲最短路徑的數(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;//起點

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”);}

六、背包問題（遞歸）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);}

矩陣鏈乘法（動態(tài)規(guī)劃）? 符號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的定義：

如果存在兩個正常數(shù)c和n0，對于所有的n≥n0時，有：

|f(n)|≤c|g(n)|，稱函數(shù)f(n)當(dāng)n充分大時的階比g(n)低，記為

f(n)=O(g(n))。計算時間f(n)的一個上界函數(shù) Ω的定義：

如果存在正常數(shù)c和n0，對于所有n≥n0時，有：

|f(n)|≥c|g(n)|，則稱函數(shù)f(n)當(dāng)n充分大時下有界，且g(n)是它的一個下界，即f(n)的階不低于g(n)的階。記為：

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

如果存在正常數(shù)c1，c2和n0，對于所有的n>n0，有：

c1|g(n)|≤f(n)≤c2|g(n)|，則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計算時間就一個常因子范圍內(nèi)而言是相同的。(1)多項式時間算法：

O(1)

(2)指數(shù)時間算法：

O(2n)

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

貪心方法基本思想：

貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇

所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。

多段圖：

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

回溯法：

(假定集合Si的大小是mi)不斷地用修改過的規(guī)范函數(shù)Pi(x1,…,xi)去測試正在構(gòu)造中的n-元組的部分向量(x1,…,xi)，看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1,…,xi)不可能導(dǎo)致最優(yōu)解，那么就將可能要測試的mi+1…mn個向量略去。約束條件：

(1)顯式約束：限定每一個xi只能從給定的集合Si上取值。

(2)解

空

間：對于問題的一個實例，解向量滿足顯式

約束條件的所有多元組，構(gòu)成了該實例

的一個解空間。

(3)隱式約束：規(guī)定解空間中實際上滿足規(guī)范函數(shù)的元

組，描述了xi必須彼此相關(guān)的情況?；咀龇ǎ?/p>

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

8皇后問題

約束條件

限界函數(shù)：

子集和數(shù)問題：

約束條件

限界函數(shù)：

回溯法－－術(shù)語：

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

全部生成的結(jié)點稱為活結(jié)點。

E-結(jié)點：當(dāng)前正在生成其兒子結(jié)點的活結(jié)點叫E-結(jié)點。

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

使用限界函數(shù)的深度優(yōu)先節(jié)點生成的方法成為回溯法；E-結(jié)點一直保持到死為止的狀態(tài)生成的方法 稱之為分支限界方法

且用限界函數(shù)幫助避免生成不包含答案結(jié)點子樹的狀態(tài)空間的檢索方法。區(qū)別：

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

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

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

一般如果只考慮時間復(fù)雜度二者都是指數(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是所有可在多項式時間內(nèi)用確定算法求解的判定問題的集合。NP是所有可在多項式時間內(nèi)用不確定算法求解的判定問題的集合 如果可滿足星月化為一個問題L，則此問題L是NP-難度的。如果L是NP難度的且L NP，則此問題是NP-完全的

第五篇：人工智能總結(jié)(精華版)

1、PROLOG程序一般由一組事實、規(guī)則和問題組成。事實一般表示對象的性質(zhì)或關(guān)系；規(guī)則一般表示對象間的因果關(guān)系、蘊含關(guān)系或?qū)?yīng)關(guān)系； 問題表示用戶的詢問是程序運行的目標(biāo)。問題是程序執(zhí)行的起點，稱為程序的目標(biāo)。PROLOG就是一種基于Horn子句的邏輯程序。

PROLOG程序的運行是從目標(biāo)出發(fā)，并不斷進行匹配、合一、歸結(jié)，有時還要回溯，直到目標(biāo)別完全滿足或不能滿足時為止。

PROLOG程序的執(zhí)行過程是一個(歸結(jié))演繹推理過程。其特點是：推理方式為反向推理, 控制策略是深度優(yōu)先, 且有回溯機制。

3、簡述用A*算法求解問題時為什么會出現(xiàn)重復(fù)擴展節(jié)點問題，解決的方法有哪些？

答：當(dāng)問題有解時，A*算法總是找到問題的最優(yōu)解結(jié)束。如果h函數(shù)定義的不合理，則當(dāng)擴展一個節(jié)點時，不一定就找到了從初始節(jié)點到該節(jié)點的最優(yōu)路徑，對于這樣的節(jié)點，就有可能被多次擴展。特別是如果這樣的節(jié)點處于問題的最優(yōu)解路徑上時，則一定會被多次擴展。解決的方法一是對h函數(shù)的定義給出限制，使得h滿足單調(diào)性。對于滿足單調(diào)性條件的h，則一定不會出現(xiàn)重復(fù)擴展節(jié)點問題。二是對A*算法加以改進，使用修正的A*算法進行搜索，這樣，隨著經(jīng)驗的豐富，系統(tǒng)的性能自然就會不斷改善和提高。

24、機器學(xué)習(xí)的三個要素：信息，發(fā)展和知識。對應(yīng)于機器學(xué)習(xí)的對象、方法和目標(biāo)。

25、基于學(xué)習(xí)策略的分類：符號學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。

26、決策樹：也稱判斷樹，它由對象的若干屬性、屬性值和有關(guān)決策組成的一棵樹。其中的節(jié)點為屬性，分支為屬性值，從同一節(jié)點出發(fā)的各個分支之間是邏輯或關(guān)系，根節(jié)點為對象的一個屬性；從根節(jié)點出發(fā)到每一個葉子節(jié)點的所有節(jié)點和邊，按順序串聯(lián)成一條分支路徑，位于同一分支路徑上的各個屬性-值對之間是邏輯與關(guān)系，葉子節(jié)點是這個與關(guān)系的對應(yīng)結(jié)果，即決策。

27、決策樹學(xué)習(xí)首先要有一個實例集，基本方法和步驟：（1）選取一個屬性，按這個屬性的不同取值對實例集進行分類；并以該屬性作為根節(jié)點，以這個屬性的諸取值作為根節(jié)點的分支，進行畫樹；（2）考察所得的每一個子類，看其中的實例的結(jié)論是否完全相同。如果相同，則以這個相同的結(jié)論作為相應(yīng)分支路徑末端的葉子節(jié)點；否則，選取一個非父節(jié)點的屬性，按這個屬性的不同取值對孩子集進行分類，并以該屬性作為節(jié)點，以這個屬性的諸取值作為節(jié)點的分支，繼續(xù)進行畫樹。如此繼續(xù)，直到所分的子集全都滿足：實則可以減少重復(fù)擴展節(jié)點問題。

4、簡述回溯策略與深度優(yōu)先策略的不同點。

答：回溯搜索策略與深度有限搜索策略最大的不同是深度有限搜索策略屬于圖搜索，而回溯搜索則不是圖搜索。在回溯搜索中，只保留了從初始節(jié)點到當(dāng)前節(jié)點的搜索路徑。而深度優(yōu)先搜索，則保留了所有的已經(jīng)搜索過的路徑。

5、不確定性類型按性質(zhì)分：隨機性，模糊性，不完全性，不一致性

6、在刪除策略歸結(jié)的過程中刪除以下子句：含有純文字的子句;含 有永真式的子句;子句集中被別的子句類含的子句。

7、圖：指由節(jié)點和有向邊組成的網(wǎng)絡(luò)。按連接同一節(jié)點的各邊的邏輯關(guān)系又可分為或圖和與或圖。

8、合一算法：求非空有限具有相同謂詞名的原子公式集的最一般合一（MGU）。

9、人工智能的遠(yuǎn)期目標(biāo)是制造智能機器，近期目標(biāo)是實現(xiàn)機器智能。

10、什么是產(chǎn)生式？產(chǎn)生式規(guī)則的語義是什么？

產(chǎn)生式規(guī)則基本形式：P→Q 或者 IF P THEN Q P 是產(chǎn)生式的前提（前件），用于指出該產(chǎn)生式是否可用的條件 Q 是一組結(jié)論或操作（后件），用于指出當(dāng)前提 P 所指示的條件滿足時，應(yīng)該得出的結(jié)論或應(yīng)該執(zhí)行的操作

產(chǎn)生式規(guī)則的語義：如果前提P被滿足，則可推出結(jié)論 Q 或執(zhí)行 Q 所規(guī)定的操作

11、謂詞公式G通過８個步驟所得的子句集合S，稱為G的子句集。請寫出這些步驟：1）消去蘊含式和等價式→，<-> ；2）縮小否定詞的作用范圍，直到其作用于原子公式: ；3）適當(dāng)改名，使量詞間不含同名指導(dǎo)變元和約束變元。；4.）消去存在量詞（形成Skolem標(biāo)準(zhǔn)型）；5）消去所有全稱量詞 ；6)化成合取范式；7).適當(dāng)改名，使子句間無同名變元；8).消去合取詞∧，用逗號代替，以子句為元素組成一個集合S

12、人工智能的基本技術(shù)包括搜索技術(shù) 推理技術(shù) 知識表示和知識庫技術(shù)、歸納技術(shù)、聯(lián)、想技術(shù)

13、產(chǎn)生式系統(tǒng)有三部分組成綜合數(shù)據(jù)庫，知識庫和推理機。其中推理可分為正向推理和反向推理。

14、在歸結(jié)原理中，幾種常見的歸結(jié)策略并且具有完備性的是刪除策略 支持集策略 線性歸結(jié)策略、輸入歸結(jié)策略、單元歸結(jié)策略

15、歸結(jié)法中，可以通過修改證明樹的方法得到問題的解答

16、開發(fā)專家系統(tǒng)所要解決的基本問題有三個，那就是知識的獲取、知識的表示和知識的運用，在語義網(wǎng)絡(luò)表示知識時，所使用的推理方法有AKO 和ISA。

17、α－β剪枝的條件是：α剪枝：若任一極小值層節(jié)點的β值小于或等于它任一先輩極大值節(jié)點的α值，即α（先輩層）≥β（后繼層），則可中止該極小值層中這個MIN節(jié)點以下的搜索過程。這個MIN節(jié)點最終的倒推值就確定為這個β值。

β剪枝：若任一極大值層節(jié)點的α值大于或等于它任一先輩極小值層節(jié)點的β值，即α（后繼層）≥β（先輩層），則可以中止該極大值層中這個MAX節(jié)點以下的搜索過程。這個MAX節(jié)點的最終倒推值就確定為這個α值。

18、知識表示的方法主要有邏輯表示法（謂詞表示法）框架 產(chǎn)生式和語義網(wǎng)絡(luò)，類和對象，模糊集合，因果網(wǎng)絡(luò)，腳本，過程等

19、知識的分類：（1）就形式而言：顯示和隱式。顯示知識是指可用語言文字符號形象聲音及其他人能直接識別和處理的形式，明確的在其載體上表示出來的知識。隱式知識只可用神經(jīng)網(wǎng)絡(luò)存儲和表示（2）就嚴(yán)密性和可靠性而言：理論知識和經(jīng)驗知識（3）就確定性而言：確定性知識和不確定知識（4）就確切性而言：確切描述的知識和非確切描述的知識。

20、知識表示是指面向計算機的知識描述或表達形式和方法。具體的講就是要用某種約定的形式結(jié)構(gòu)來描述知識，而且這種形式結(jié)構(gòu)還要能夠轉(zhuǎn)換為機器的內(nèi)部形式，使的計算機能方便的存儲、處理和應(yīng)用。------知識表示是建立專家系統(tǒng)級各種知識系統(tǒng)的重要環(huán)節(jié)，也是知識工程的一個重要方面。

21、基于謂詞邏輯的推理主要是演繹方式的推理；基于框架、語義網(wǎng)絡(luò)和對象知識表示的推理是一種稱為繼承的推理。

22、機器學(xué)習(xí)：主要指機器對自身行為的修正或性能的改善和機器對客觀規(guī)律的發(fā)現(xiàn)。（讓計算機模擬人的學(xué)習(xí)行為，或者說讓計算機也具有學(xué)習(xí)的能力）

23、機器學(xué)習(xí)的流程：（1）對于輸入的信息，系統(tǒng)根據(jù)目標(biāo)和經(jīng)驗做出決策予以響應(yīng)，即執(zhí)行相應(yīng)的動作；（2）對目標(biāo)的實現(xiàn)或任務(wù)的完成情況進行評估；（3）將本次的輸入、響應(yīng)和評價作為經(jīng)驗予以存儲記錄?？梢钥闯?，第一次決策時系統(tǒng)中還無任何經(jīng)驗，但從第二此決策開始，經(jīng)驗便開始積累。

例結(jié)論完全相同，而得到所有的葉子節(jié)點為止。這樣一棵決策樹就被生成。

28、神經(jīng)網(wǎng)絡(luò)分為四大類：分層前向網(wǎng)絡(luò)、反饋前向網(wǎng)絡(luò)、互聯(lián)前向網(wǎng)絡(luò)、廣泛互聯(lián)網(wǎng)絡(luò)。

29、網(wǎng)絡(luò)學(xué)習(xí)一般是利用一組稱為樣本的數(shù)據(jù)，作為網(wǎng)絡(luò)的輸入（和輸出），網(wǎng)絡(luò)按照一定的規(guī)則自動調(diào)節(jié)神經(jīng)元之間的連接強度或拓?fù)浣Y(jié)構(gòu)，當(dāng)網(wǎng)絡(luò)的實際輸出滿足期望的要求，或者趨于穩(wěn)定是，則認(rèn)為學(xué)習(xí)成功。

30、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的規(guī)則是權(quán)值修正規(guī)則：相關(guān)規(guī)則和誤差修正規(guī)則。

31、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方法分類：（外部影響）有導(dǎo)師學(xué)習(xí)，強化學(xué)習(xí)，無導(dǎo)師學(xué)習(xí)；（內(nèi)部變化）權(quán)值修正，拓?fù)渥兓?，?quán)值與拓?fù)湫拚?；（算法性質(zhì)）確定性學(xué)習(xí)，隨機性學(xué)習(xí)；（輸入要求）基于相似性學(xué)習(xí)，基于命令學(xué)習(xí)。

32、專家系統(tǒng)：應(yīng)用于某一專門領(lǐng)域，擁有該領(lǐng)域相當(dāng)數(shù)量的專家級知識，能模擬專家的思維，能達到專家級水平，像專家一樣解決困難、復(fù)雜的實際問題的計算機（軟件）系統(tǒng)。

33、專家系統(tǒng)的基本要素：專家擁有豐富的專業(yè)知識和實踐經(jīng)驗或者說擁有豐富的理論知識和經(jīng)驗知識，特別是經(jīng)驗知識。

34、專家系統(tǒng)與一般的軟件系統(tǒng)開發(fā)無異，其開發(fā)過程同樣要遵循軟件工程的步驟和原則，即也要進行系統(tǒng)分析、系統(tǒng)設(shè)計等幾個階段的工作。

但由于它是專家系統(tǒng)，而不是一般的軟件系統(tǒng)，所以，又有其獨特的地方，主要包括以下幾個步驟：

系統(tǒng)總體分析與設(shè)計；知識獲取；知識表示與知識描述語言設(shè)計；知識庫設(shè)計、知識庫管理系統(tǒng)設(shè)計；推理機與解釋模塊設(shè)計；總控與界面設(shè)計；編程與調(diào)試；測試與評價；運行與維護?？梢钥闯鏊腥缦绿攸c：知識獲取和知識表示設(shè)計是一切工作的起點；知識表示與知識描述語言確定后，其他設(shè)計可同時進行；

35、對涉及人工智能的一些問題的認(rèn)識：首先人工智能把人腦更有效的擴大和延伸是人類智能擴大的延伸，人工智能的應(yīng)用十分廣泛：機器翻譯、智能控制、模式識別、機器博弈等，運用智能技術(shù)解決很多的實際問題從而使現(xiàn)有的計算機更有效更靈活成為人類智能化信息處理的工具。人工智能用計算機模擬人的思維活動包含理解能力、學(xué)習(xí)能力、推理能力，主要是腦功能的結(jié)構(gòu)模擬和功能模擬。然而人類不能賦予機器同等的情感，無法確保責(zé)任問題，此外生物物種滅絕新型細(xì)菌的出現(xiàn)，人類的未來難以預(yù)料

37、能解節(jié)點定義如下： ①（終節(jié)點）是能解節(jié)點； ②若非終節(jié)點有（“或”）子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點至少有一能解，該非終節(jié)點才能解； ③若非終節(jié)點有（“與”）子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點均能解，該非終節(jié)點才能解。

18、局部圖的耗散值定義如下： ①若n是局部圖的一個葉節(jié)點，則k（n，N）=（h(n)），其中（h(n)）表示節(jié)點n到目標(biāo)節(jié)點集的最佳解圖耗散值的估計； ②若n由一個外向連接符指向后繼節(jié)點{n1，…，ni}，并設(shè)該連接符的耗散值為Cn，則k（n，N）=（Cn+ k（n1，N）+ … + k（ni，N））。

19、耗散值最小的解圖稱為（最佳）解圖

20、AO*算法是一種用于對（與或圖）進行搜索的啟發(fā)式搜索算法，該算法對目前找到的局部圖進行評價，選擇（耗散值最?。┑木植繄D進行優(yōu)先搜索，直到找到一個解圖為止。當(dāng)啟發(fā)函數(shù)h滿足（單調(diào)）條件時，在問題有解的情況下，AO*算法一定能找到最佳解圖結(jié)束。

21、所謂“圖靈實驗”，是為了判斷一臺機器是否具備智能的實驗。實驗由三個封閉的房間組成，分別放置主持人、參與人和機器。主持人向參與人和機器提問，通過提問的結(jié)果來判斷誰是人，誰是機器。如果主持人無法判斷誰是人，誰是機器，則這臺機器具備智能，即所謂的“智能機器”。

22/深度優(yōu)先方法的特點是什么？屬于圖搜索；是一個通用的搜索方法；如果深度限制不合適，有可能找不到問題的解；不能保證找到最優(yōu)解。

23/什么是置換？置換是可交換的嗎？通常用有序?qū)Φ募蟬＝{t1/v1，t2/v2，?，tn/vn}來表示任一置換，置換集的元素ti/vi的含義是表達式中的變量vi處處以項ti來替換，用s對表達式E作置換后的例簡記為Es。一般來說，置換是不可交換的，即兩個置換合成的結(jié)果與置換使用的次序有關(guān)。