單項選擇題

?凸多邊形的三角剖分問題。用動態(tài)規(guī)劃算法求解最優(yōu)三角剖分,首先要分析最優(yōu)解的結構,也就是將問題分解為子問題,并具有最優(yōu)子結構性質。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問題的方法,哪種是正確的將問題劃分為子問題的方案?正確的劃分方案共有幾種不同方式?()

A.右圖正確,4種
B.右圖正確,9種
C.左圖正確,4種
D.左圖正確,9種


您可能感興趣的試卷

你可能感興趣的試題

2.單項選擇題

動態(tài)規(guī)劃解題的步驟分為四步:
(1)分析最優(yōu)解的結構
(2)建立遞歸關系
(3)計算最優(yōu)值
(4)構造最優(yōu)解
關于這四個步驟的內容描述不正確的是哪個?()

A.計算最優(yōu)值:以自頂往下的方法計算問題的最優(yōu)值,也就是先求解規(guī)模較大的問題的最優(yōu)值
B.構造最優(yōu)解:根據計算最優(yōu)值時得到的信息構造出問題的最優(yōu)解,通常是用遞歸算法完成最優(yōu)解的構造
C.建立遞歸關系:建立關于問題最優(yōu)值的遞歸定義,即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到
D.分析最優(yōu)解的結構:一個一般化問題可以分解為幾個性質相同的子問題,并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到,也就是要滿足最優(yōu)子結構性質

4.單項選擇題?下面哪些不是遞歸算法的特點?()

A.結構清晰
B.容易用數學歸納法證明算法的正確性
C.遞歸算法耗費的時間和占用的內存空間要比解決同一問題的非遞歸算法要少
D.可讀性強