tsp問題之動態(tài)規(guī)劃法-資料下載頁
2025-07-25 20:35本頁面
【正文】 個最優(yōu)決策序列。 ?原理告訴我們，一個最優(yōu)問題的任何實例的最優(yōu)解是由該實例的子實例的最優(yōu)解組成。 ?一般來說，如果所求解問題對于最優(yōu)性原理成立，則說明用動態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲取各階段問題的遞推關(guān)系式。 動態(tài)規(guī)劃法（三） ? 動態(tài)規(guī)劃法步驟 （ 1）分段：將原問題分解為若干個相互重疊的子問題； （ 2）分析：分析問題是否滿足最優(yōu)性原理，找出動態(tài)規(guī)劃函數(shù)的遞推式； （ 3）求解：利用遞推式自底向上計算，實現(xiàn)動態(tài)規(guī)劃過程。 動態(tài)規(guī)劃法解決的常用問題（一） ? 斐波那契數(shù) F(n) = 0 n =0 1 n = 1 F(n1) + F(n2) n=2 動態(tài)規(guī)劃法解決的常用問題（二） ? 多段圖的最短路徑問題 2 1 2 0 3 4 5 6 7 8 9 4 9 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 動態(tài)規(guī)劃法解決的常用問題（三） ? POJ 1163 數(shù)字三角形 問題描述：在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經(jīng)過的數(shù)字之和最大。路徑上的每一步都只能往左下或右下走。只需要求出這個最大和即可，不必給出具體路徑 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 動態(tài)規(guī)劃法解決的常用問題（四） ? 近似串匹配問題 ? 最長公共子序列問題 ? ０ /１背包問題
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1