經(jīng)過前面對RRT的介紹，我們發(fā)現(xiàn)基于采樣的規(guī)劃算法與基于圖搜索的規(guī)劃算法都是通過對路徑樹進行拓展新節(jié)點，來找到起點到終點的路徑解。RRT家族通過隨機采樣來生成這棵路徑樹，隨機采樣會面臨采樣低效的問題——大部分采樣的新節(jié)點都無益于提升路徑解的最優(yōu)性。動態(tài)規(guī)劃基于特定規(guī)劃問題的結(jié)構(gòu)，通過固定的采樣得到眾多節(jié)點，將多階段的規(guī)劃問題轉(zhuǎn)變成一系列單階段最優(yōu)化問題。同樣的規(guī)劃問題，若能用動態(tài)規(guī)劃來求解，那么動態(tài)規(guī)劃方法的效率比RRT算法要高很多。
一、動態(tài)規(guī)劃：復(fù)雜問題簡單化
在pygraph實現(xiàn)graph圖結(jié)構(gòu)+Dijkstra最短路徑（python庫）中，給出的例子如下所示。這個圖的最短路徑問題可以用圖搜索方法解決，也可以用動態(tài)規(guī)劃方法解決。
動態(tài)規(guī)劃通過把原問題分解為相對簡單的子問題的方式來求解復(fù)雜問題的方法。但是，不是所有的原問題劃分成子問題都能用動態(tài)規(guī)劃方法來求解，分解后的子問題必須滿足以下兩個條件：
1）最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）。可以從子問題的最優(yōu)解推出原問題的最優(yōu)解。
2）無后效性。即，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它后續(xù)的決策。例如，馬爾可夫決策過程就是無后效性的。文章來源：http://www.zghlxwxcb.cn/news/detail-676984.html
如果一個復(fù)雜的多步?jīng)Q策文章來源地址http://www.zghlxwxcb.cn/news/detail-676984.html
到了這里，關(guān)于基于采樣的規(guī)劃算法之動態(tài)規(guī)劃方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
