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