第9章怎樣研究算法遺傳算法示例練習(xí)題答案解析

1、第9章怎樣研究算法怎樣研究算法:遺傳算法示例遺傳算法示例1、P類問題、NP類問題、NPC類問題是計算機(jī)科學(xué)領(lǐng)域關(guān)于可求解性可計算性很重要的概念。關(guān)于P、NP和NPC類問題，回答下列問題。(1)下列說法不正確的是_____。(A)P類問題是計算機(jī)可以在有限時間內(nèi)能夠求解的問題；(B)NP類問題是計算機(jī)可以在有限時間內(nèi)能夠驗證“解”的正確性的問題；(C)NPC類問題是對問題的每一個可能解，計算機(jī)都可以在有限時間內(nèi)驗證“解”的正確性的問題，被

2、稱為NP完全問題；(D)上述說法有不正確的；答案：D解釋：本題考核P類問題、NP類問題、NPC類問題的概念。P類問題指計算機(jī)可以在有限時間內(nèi)求解的問題，(A)正確；NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性問題，(B)正確；NPC問題指NP問題的所有可能答案都可以在多項式時間內(nèi)進(jìn)行正確與否的驗算，稱為NPComplete問題，(C)正確；(A)(B)(C)都正確，所以(D)錯誤。具體內(nèi)容請參考第九章視頻之“可求解

3、與難求解問題”以及第九章課件。(2)可解性問題是指能夠找到多項式時間復(fù)雜性算法進(jìn)行求解的問題，難解性問題是指找不到多項式時間復(fù)雜性算法進(jìn)行求解的問題。下列說法不正確的是_____。(A)P類問題是可解性問題，NP類問題是難解性問題。(B)NP類問題不一定是難解性問題，因為P類問題也一定是NP類問題；(C)NP類問題不確定是否是P類問題，但NPC類問題一定是難解性問題；(D)上述說法有不正確的；答案：A解釋：本題考核對可解性問題和難解性問

4、題概念的理解。P類問題指計算機(jī)可以在有限時間內(nèi)求解的問題，所以是可解性問題；NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性問題，但P類問題是NP類問題的一個子集，所以NP類問題不一定是難解性問題；NPC問題指NP問題的所有可能答案都大學(xué)計算機(jī)計算思維練習(xí)題集(E)上述說法有不正確的；答案：B解釋：本題考核對P類問題、NP類問題概念的理解。P類問題是總能找到一個多項式時間復(fù)雜性算法進(jìn)行求解的問題，NP類問題雖然是不確定

5、能找到多項式時間復(fù)雜性算法進(jìn)行求解，但一定能找到多項式時間復(fù)雜性算法進(jìn)行“解”的正確性驗證的問題，所以(B)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(6)非確定性多項式問題是指這樣的問題，下列說法不正確的是_____。(A)它能夠找到一個算法、甚至是多項式時間復(fù)雜性算法進(jìn)行求解，但算法中包含“不確定性”，如“任意組合一個解，…”、“隨機(jī)組合一個解，…”等；(B)它能夠找到一個算法、甚至是多項式時間復(fù)雜性算法

6、進(jìn)行求解，但算法是通過“猜測”方式求出問題的解；(C)它能夠通過“產(chǎn)生任何一個解，并驗證解的正確性”的方法進(jìn)行求解；(D)它一定是能夠找到多項式時間復(fù)雜性算法以驗證給定“解”的正確性的問題；(E)上述說法有不正確的；答案：E解釋：本題考核對NP類問題概念的理解。NP類問題：非確定性多項式問題(NondeterministicPolynomial)。有些問題，其答案是無法直接計算得到的，只能通過間接的猜算或試算來得到結(jié)果，這就是非確定性問

7、題(Nondeterministic)。雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性的問題，即：在多項式時間內(nèi)可以由一個算法驗證一個解是否正確的非確定性問題，所以(A)(B)(C)(D)都是正確的，(E)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(7)、關(guān)于NP類問題求解，下列說法正確的是_____。(A)NP類問題求精確解，可能找不到多項式時間復(fù)雜性算法；但NP類問題求近似解，則一定能夠找到多項式