您好,登錄后才能下訂單哦!
基本思想:動態(tài)規(guī)劃算法與分治法類似,其基本思想是將帶求解的問題劃分成若干個獨立子問題,根據(jù)求得子問題的解合并而得到原問題的解。而動態(tài)規(guī)劃劃分的子問題往往不是相互獨立的,因此若采用同分治法相同的求解問題的方法會導(dǎo)致大量的子問題被重復(fù)計算,為了避免這種情況發(fā)生,我們可以用一個表來記錄我們求得的子問題的解,無論該子問題的解以后是否會用到,只要被計算,就將其填入表中。這便是動態(tài)規(guī)劃的基本思想。
求解的基本步驟:
(1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征。
(2)遞歸的定義最優(yōu)值。
(3)以自底向上的方式計算出最優(yōu)值。
(4)根據(jù)計算最優(yōu)值時得到的信息,構(gòu)造最優(yōu)解。
時間、精力和水平有限,無法給出專業(yè)詳細(xì)地分析,但我會把自己掌握的部分毫無保留分享給大家。
下面的程序我盡可能給出最詳細(xì)的注釋,如有錯誤還請及時指出,以避免產(chǎn)生沒必要的誤會。
#include <iostream> //數(shù)組p存儲連乘矩陣的維數(shù) int p[] = { 30, 35, 35, 15, 15, 5, 5, 10, 10, 20, 20, 25 }; int pcount = sizeof(p) / sizeof(*p); //二維數(shù)組m存放所有子問題的最優(yōu)值 int m[6][6]; //二維數(shù)組s存放斷開的位置k int s[6][6]; //用于打印二維數(shù)組 void debug(int array[][6]); //預(yù)初始化二維數(shù)組 void initialization(int array[][6]); //打印最優(yōu)解的構(gòu)成 void Traceback(int i, int j, int array[][6]); //根據(jù)自底向上的方式計算所有子問題最優(yōu)值 void MatrixChain(int *p, int n, int m[][6], int s[][6]) { initialization(m); initialization(s); //注意n/2得到的是相乘矩陣的個數(shù) for (int i = 0; i < n/2; i++) m[i][i] = 0; //單個矩陣最優(yōu)值為0 //外層循環(huán),從矩陣A1-A5依次計算矩陣鏈長度為2,3,4,5 for (int r = 1; r < n/2;r++) //內(nèi)層循環(huán),計算矩陣鏈長度為x(x可能為2,3,4,5)的所有值(例如:若x=2, //則計算m[1][2],m[2][3],m[3][4],m[4][5],m[5][6]) for (int i = 0; i < n/2 - r; i++) //隨矩陣鏈長度x增加,i的最大值與(n/2-r) //構(gòu)成對應(yīng)關(guān)系 { int j = i + r; //列數(shù)j取決于矩陣鏈長度和行數(shù)i m[i][j] = m[i + 1][j] + p[2 * i] * p[2 * i + 1] * p[j * 2 + 1]; //這里先求出一個基本解,以A0矩陣劃分(A[0]*A[1:5]) //std::cout << "m"<<"["<<i<<"]"<<"["<<j<<"]"<<m[i][j] << std::endl; s[i][j] = i; //保存劃分的位置,Trackback求最優(yōu)解用到 for (int k = i + 1; k < j; k++) //對每個可能劃分的位置進(jìn)行檢索 { int t = m[i][k] + m[k + 1][j] + p[2 * i] * p[2 * k + 1] * p[2 * j + 1]; //求最優(yōu)值的遞推式 //如果計算得到的值比基本解更優(yōu),那么替換原來的最優(yōu)值和劃分位置 if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;} } } } void debug(int array[][6]) { for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) std::cout << array[i][j] << " "; std::cout << std::endl; } } void initialization(int array[][6]) { for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) array[i][j] = -1; } void Traceback(int i, int j, int array[][6]) { using std::cout; using std::endl; if (i == j) return; Traceback(i, array[i][j], array); Traceback(array[i][j] + 1, j, array); cout << "Multiply A" << i << "," << array[i][j]; cout << " and A" << (array[i][j] + 1) << "," << j << endl; } //一小段測試程序,不懂請盡可能多調(diào)試以便理解。 int main() { MatrixChain(p, pcount, m, s); debug(m); //debug(s); Traceback(1, 5, s); return 0; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。