在求解某問題時，經(jīng)過分析發(fā)現(xiàn)該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，求解過程中子問題被重復(fù)求解，則采用（）算法設(shè)計策略；若定義問題的解空間，以深度優(yōu)先的方式搜索解空間，則采用（）算法設(shè)計策略。
A.分治
B.動態(tài)規(guī)劃
C.貪心
D.回溯
正確答案：B
分治法的設(shè)計思想是將一個難以直接解決的大問題分解成一些規(guī)模較少的相同問題以便各個擊破，分而治之。動態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是獨(dú)立的。若用分治法來解這類問題，則相同的子問題會被求解多次，以至于最后解決原問題需要耗費(fèi)指數(shù)級時間。貪心法經(jīng)常用于解決最優(yōu)化問題，但他的最優(yōu)往往是從局部最優(yōu)來考慮的，每一步都選最優(yōu)的方案，但這種方案不一定能得到整體上的最優(yōu)解?；厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。題目描述中提到，需要解決的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，且求解過程中子問題被重復(fù)求解，這種情況下如果采用分治法，效率會很低，所以應(yīng)采用動態(tài)規(guī)劃法。而“以深度優(yōu)先的方式搜索解空間”則明顯是在采用回溯法。
B.動態(tài)規(guī)劃
C.貪心
D.回溯
正確答案：B
分治法的設(shè)計思想是將一個難以直接解決的大問題分解成一些規(guī)模較少的相同問題以便各個擊破，分而治之。動態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是獨(dú)立的。若用分治法來解這類問題，則相同的子問題會被求解多次，以至于最后解決原問題需要耗費(fèi)指數(shù)級時間。貪心法經(jīng)常用于解決最優(yōu)化問題，但他的最優(yōu)往往是從局部最優(yōu)來考慮的，每一步都選最優(yōu)的方案，但這種方案不一定能得到整體上的最優(yōu)解?；厮莘ㄊ且环N既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。題目描述中提到，需要解決的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，且求解過程中子問題被重復(fù)求解，這種情況下如果采用分治法，效率會很低，所以應(yīng)采用動態(tài)規(guī)劃法。而“以深度優(yōu)先的方式搜索解空間”則明顯是在采用回溯法。