算法九：動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃（Dynamicprogramming）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。

動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量：一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表。這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。

關(guān)于動(dòng)態(tài)規(guī)劃最經(jīng)典的問(wèn)題當(dāng)屬背包問(wèn)題。

算法步驟：

1. 最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問(wèn)題提供了重要線索。

2. 子問(wèn)題重疊性質(zhì)。子問(wèn)題重疊性質(zhì)是指在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過(guò)的子問(wèn)題時(shí)，只是在表格中簡(jiǎn)單地查看一下結(jié)果，從而獲得較高的效率.

算法十：樸素貝葉斯分類(lèi)算法

樸素貝葉斯分類(lèi)算法是一種基于貝葉斯定理的簡(jiǎn)單概率分類(lèi)算法。貝葉斯分類(lèi)的基礎(chǔ)是概率推理，就是在各種條件的存在不確定，僅知其出現(xiàn)概率的情況下，如何完成推理和決策任務(wù)。概率推理是與確定性推理相對(duì)應(yīng)的。而樸素貝葉斯分類(lèi)器是基于獨(dú)立假設(shè)的，即假設(shè)樣本每個(gè)特征與其他特征都不相關(guān)。

樸素貝葉斯分類(lèi)器依靠精確的自然概率模型，在有監(jiān)督學(xué)習(xí)的樣本集中能獲取得非常好的分類(lèi)效果。在許多實(shí)際應(yīng)用中，樸素貝葉斯模型參數(shù)估計(jì)使用最大似然估計(jì)方法，換言之樸素貝葉斯模型能工作并沒(méi)有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過(guò)于簡(jiǎn)單化的假設(shè)，但樸素貝葉斯分類(lèi)器在很多復(fù)雜的現(xiàn)實(shí)情形中仍能夠取得相當(dāng)好的效果。

?