在學(xué)習(xí)決策樹的時(shí)候向挖，我們知道，其一大特點(diǎn)是：尋找最佳的決策樹是NP完成問題炕舵。什么是NP完全問題何之，決策樹的這一特點(diǎn)又是什么意思？
什么是NP完全問題
這里的NP其實(shí)是Non-deterministic Polynomial的縮寫咽筋，即多項(xiàng)式復(fù)雜程度的非確定性問題溶推，NP完全問題有時(shí)也會簡稱為NP-C問題。與此概念相關(guān)的還有P類問題奸攻、NP類問題等蒜危。要理解什么是NP完全問題，首先得從P類問題開始理解睹耐。
所有可以在多項(xiàng)式時(shí)間內(nèi)求解的判定問題構(gòu)成P類問題
判定問題是指回答結(jié)果輸出為Yes或No的問題辐赞，比如：3233是否可以寫成兩個(gè)大于1的數(shù)字的乘積？是否存在一條路線有且僅有一次的走過七橋問題的每一座橋疏橄？
在設(shè)計(jì)程序時(shí)，我們經(jīng)常需要評估這個(gè)程序的時(shí)間復(fù)雜度略就，即衡量當(dāng)問題規(guī)模變大后捎迫，程序執(zhí)行所需的時(shí)間增長會有多快。如O(1)表示常數(shù)級別表牢，即不管問題的規(guī)模變大多少倍窄绒，所耗的時(shí)間不會改變；O(N^2) 表示平方級別崔兴，即當(dāng)問題規(guī)模增大至2倍時(shí)彰导，所花費(fèi)的時(shí)間則放大至4倍；O(2^N) 表示指數(shù)級別敲茄，即當(dāng)問題規(guī)模倍數(shù)擴(kuò)大時(shí)位谋，所用時(shí)間會呈指數(shù)放大。
多項(xiàng)式時(shí)間則是指O(1)堰燎、O(logN)掏父、O(N^2) 等這類可用多項(xiàng)式表示的時(shí)間復(fù)雜度，通常我們認(rèn)為計(jì)算機(jī)可解決的問題只限于多項(xiàng)式時(shí)間內(nèi)秆剪。而O(2^N)赊淑、O(N!)這類非多項(xiàng)式級別的問題，其復(fù)雜度往往已經(jīng)到了計(jì)算機(jī)都接受不了的程度仅讽。
所有非確定性多項(xiàng)式時(shí)間內(nèi)可解的判定問題構(gòu)成NP類問題
NP類問題將問題分為求解和驗(yàn)證兩個(gè)階段陶缺，問題的求解是非確定性的，無法在多項(xiàng)式時(shí)間內(nèi)得到答案洁灵，而問題的驗(yàn)證卻是確定的饱岸，能夠在多項(xiàng)式時(shí)間里確定結(jié)果。
比如：是否存在一個(gè)公式可以計(jì)算下一個(gè)質(zhì)數(shù)是多少？這個(gè)問題的答案目前是無法直接計(jì)算出來的伶贰，但是如果某人給出了一個(gè)公式蛛砰，我們卻可以在多項(xiàng)式時(shí)間里對這個(gè)公式進(jìn)行驗(yàn)證。
NP中的一類比較特殊的問題黍衙，這類問題中每個(gè)問題的復(fù)雜度與整個(gè)類的復(fù)雜度有關(guān)聯(lián)性泥畅，假如其中任意一個(gè)問題在多項(xiàng)式時(shí)間內(nèi)可解的，則這一類問題都是多項(xiàng)式時(shí)間可解琅翻。這些問題被稱為NP完全問題位仁。
可以說NP完全問題是NP類問題的一種特殊情況，總結(jié)這幾類問題的特點(diǎn)方椎，可參考如下這個(gè)表格：
| 問題類型 | 是否能在多項(xiàng)式時(shí)間內(nèi)求解 | 是否能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證 |
|---|---|---|
| P | 是 | 是 |
| NP | 是 or 否 | 是 |
| NP-C | 未知 | 是 |
注：表格中的問題類型的困難程度依次遞增
由表可知聂抢，NP類問題是否能在多項(xiàng)式時(shí)間內(nèi)求解，其答案并不明確棠众，如果回答為「是」琳疏，豈不是跟P類問題一樣了？值得一題的是闸拿，P=NP空盼？是千禧七大難題的首個(gè)難題，是一個(gè)價(jià)值百萬美元的問題新荤，這個(gè)問題本質(zhì)是求證：能用多項(xiàng)式時(shí)間驗(yàn)證解的問題是否內(nèi)在多項(xiàng)式時(shí)間內(nèi)找出解揽趾。
決策樹的NP完全問題
在決策樹算法中，尋找最優(yōu)決策樹是一個(gè)NP完全問題苛骨。決策樹的這一特點(diǎn)篱瞎，說明我們無法利用計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)，找出全局最優(yōu)的解痒芝。
也正因?yàn)槿绱死睿蠖鄶?shù)決策樹算法都采用啟發(fā)式的算法，如貪心算法严衬，來指導(dǎo)對假設(shè)空間的搜索校哎。可以說瞳步，決策樹最后的結(jié)果闷哆，是在每一步、每一個(gè)節(jié)點(diǎn)上做的局部最優(yōu)選擇单起。決策樹得到的結(jié)果抱怔，是沒法保證為全局最優(yōu)的。
（全文完）
參考文章：
1嘀倒、什么是P問題屈留、NP問題和NPC問題
2局冰、what are the differences between np, np-complete and np-hard
