?凸多邊形的三角剖分問題。用動(dòng)態(tài)規(guī)劃算法求解最優(yōu)三角剖分,首先要分析最優(yōu)解的結(jié)構(gòu),也就是將問題分解為子問題,并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問題的方法,哪種是正確的將問題劃分為子問題的方案?正確的劃分方案共有幾種不同方式?()
A.右圖正確,4種B.右圖正確,9種C.左圖正確,4種D.左圖正確,9種
矩陣連乘問題:下圖是動(dòng)態(tài)規(guī)劃算法計(jì)算6個(gè)矩陣A1A2A3A4A5A6連乘所生成的信息表(a)表描述了計(jì)算順序(b)表是m[i][j]的最優(yōu)值表(c)表是輔助信息表(斷開位置)分析表格,給出A2A3A4A5A6五個(gè)矩陣連乘所需要的最少數(shù)乘次數(shù),并用加括號(hào)的方法表示出其乘法順序()。
A.15125,(A2A3)((A4A5)A6)B.10500,(A2(A3A4))(A5A6)C.15125,(A2(A3A4))(A5A6)D.10500,(A2A3)((A4A5)A6)
動(dòng)態(tài)規(guī)劃解題的步驟分為四步:(1)分析最優(yōu)解的結(jié)構(gòu)(2)建立遞歸關(guān)系(3)計(jì)算最優(yōu)值(4)構(gòu)造最優(yōu)解關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)?()
A.計(jì)算最優(yōu)值:以自頂往下的方法計(jì)算問題的最優(yōu)值,也就是先求解規(guī)模較大的問題的最優(yōu)值B.構(gòu)造最優(yōu)解:根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問題的最優(yōu)解,通常是用遞歸算法完成最優(yōu)解的構(gòu)造C.建立遞歸關(guān)系:建立關(guān)于問題最優(yōu)值的遞歸定義,即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到D.分析最優(yōu)解的結(jié)構(gòu):一個(gè)一般化問題可以分解為幾個(gè)性質(zhì)相同的子問題,并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到,也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)