如何理解遞歸，回溯，動態(tài)規(guī)劃等算法？遞歸比較簡單，是遞歸的逆算法。例如，給定a（10）和a（n）=f（a（n1）），讓您找到a（1）?；厮菔且环N必須用于深度優(yōu)先搜索的方法。建議大家看一看“八皇后問題”

如何理解遞歸，回溯，動態(tài)規(guī)劃等算法？

遞歸比較簡單，是遞歸的逆算法。例如，給定a（10）和a（n）=f（a（n1）），讓您找到a（1）。回溯是一種必須用于深度優(yōu)先搜索的方法。建議大家看一看“八皇后問題”，看完后要理解。動態(tài)規(guī)劃是一種以空間換時間的算法，即占用大量內(nèi)存，但具有較高的時間效率。建議你看看“攔截導(dǎo)彈”問題和“0/1背包問題”。先看動態(tài)規(guī)劃問題，再了解概念比較好

八皇后問題是一個古老而著名的問題，是回溯算法的典型例子。

19世紀(jì)著名數(shù)學(xué)家高斯在1850年提出了一個問題：在8X8格棋上放置8個皇后，使它們不能互相攻擊，即任何兩個皇后不能在同一行、同一列或同一對角線上。有多少種鐘擺。高斯認(rèn)為有76種選擇。1854年，不同的作者在柏林的國際象棋雜志上發(fā)表了40種不同的解決方案。用圖論方法得到92個結(jié)果。對于八皇后問題的實現(xiàn)，如果結(jié)合動態(tài)圖形演示，對算法的描述可以更加生動、生動，教學(xué)效果良好。下面是一個用turboc實現(xiàn)的八皇后問題的圖形程序，可以演示所有92個解。八皇后問題動態(tài)圖的實現(xiàn)

1。分治法和動態(tài)規(guī)劃的主要共同點(diǎn)是：1）都要求原問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。它們都對原問題進(jìn)行了分解和克服，并將其分解為幾個較小的子問題。然后將子問題的解進(jìn)行組合，形成原問題的解。

2、分治法與動態(tài)規(guī)劃實現(xiàn)方法：①分治法通常采用遞歸求解。

②動態(tài)規(guī)劃一般采用自下而上的迭代法求解，也可采用帶記憶函數(shù)的遞歸法自上而下求解。

3、分治法與動態(tài)規(guī)劃的主要區(qū)別如下：1。分治法把分解的子問題看作是獨(dú)立的。

②在動態(tài)規(guī)劃中，分解的子問題被理解為相互關(guān)聯(lián)和重疊的部分。

八皇后究竟有多少種解法？怎么解？

與靜態(tài)規(guī)劃模型相比，動態(tài)規(guī)劃模型具有以下優(yōu)點(diǎn)：1。得到全局最優(yōu)解。得到了一組最優(yōu)解。由于動態(tài)規(guī)劃方法反映了動態(tài)過程演化的關(guān)系和特點(diǎn)，可以利用實際知識和經(jīng)驗來提高求解效率。

動態(tài)規(guī)劃模型的缺點(diǎn)如下：1。沒有統(tǒng)一的標(biāo)準(zhǔn)模型。數(shù)值方法中存在維數(shù)災(zāi)難。