動態規劃是最優化原理中的一種重要的方法。
動態規劃在查找有很多重疊子問題的情況的最優解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被保存，從簡單的問題直到整個問題都被解決。因此，動態規劃保存遞歸時的結果，因而不會在解決同樣的問題時花費時間。
動態規劃只能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解。簡單地說，問題能夠分解成子問題來解決。
總的來說，動態規劃的優勢在于：
問題描述:
動態規劃舉例
圖10-3（a）示出了一個數字三角形，請編一個程序，
計算從頂至底的某處的一條路勁，
使該路勁所經過的數字的總和最大。
（1） 每一步可沿左斜線向下或右斜線向下；
（2） 1＜三角形行數≤100；
（3） 三角形中的數字為0，1，……99。
輸入數據：
由INPUT.TXT文件中首先讀到的是三角形的行數，
在例子中INPUT.TXT表示如圖13-3（b）.?
???????????????????????????????
?????????????????????????????? 7?
????????????????????????????? 3 8?
???????????????????????????? 8 1 0?
????????????????????????????2 7 4 4?
???????????????????????????4 5 2 6 5
????????????????????????? 5 6 9 5 9 8
從別人blog里看到這個題目,手上癢癢,就寫了一個.用的是逆向遞推法從頂部往下.
分2個文件,一個主程序和一個用于讀取文件的輔助類.
思路:
? 1.算出每個節點的規劃值(也就是待比較的最大值),并記錄搜索路徑
??2.取三角形底邊所有規劃值中的最大值
? 3.輸出路徑
主程序
package
?test;
import
?java.util.
*
;
/**?*/
/**
?*??用動態規劃法求出最優路徑
?*??
@author
?zqc
?*?
*/
public
?
class
?DynamicSolveTrianglePath?
{
????
????
private
?String[][]?str_triangle?
=
?
null
;
????
private
?Node[][]?triangle_nodes?
=
?
null
;
????
private
?List?nodes;
????
private
?List?paths;
????
????
//
節點
????
static
?
class
?Node
{
????????
private
?
int
?value;
????????
private
?List?path?
=
?
new
?Vector();
????????
public
?List?getPath()?
{
????????????
return
?path;
????????}
????????
public
?
void
?setPath(List?p)
{
????????????path?
=
?p;
????????}
????????
//
n=(0,0)?or?(0,1)?or?(2,2)
????????
public
?
void
?addPath(String?n)
{
????????????path.add(n);
????????}
????????
public
?
void
?addPath(List?pa)
{
????????????path.addAll(pa);
????????}
????????
public
?
int
?getValue()?
{
????????????
return
?value;
????????}
????????
public
?
void
?setValue(
int
?value)?
{
????????????
this
.value?
=
?value;
????????}
????}
????
????
public
?DynamicSolveTrianglePath()
{
????????initNodes();
????????findPath();
????}
????
????
// 從根節點開始,逆向推解出到達所有節點的最佳路徑
????private?void?initNodes(){
????????this.str_triangle?=?ReadTriangle.getTriangle();
????????triangle_nodes?=?new?Node[str_triangle.length][];
????????nodes?=?new?Vector();
????????for(int?i?=?0?;?i?<?str_triangle.length;?i++){
????????????triangle_nodes[i]?=?new?Node[str_triangle[i].length];
????????????for(int?j?=?0?;?j<str_triangle[i].length;j++){
????????????????String?currentPath?=?"("+i+","+j+")";
????????????????Node?n?=?new?Node();
???????????????if(i==0&&j==0){
???????????????????n.setValue(
??????????????????????????????c(str_triangle[0][0])????????
????????????????????????????);
???????????????????n.addPath(currentPath);
???????????????????triangle_nodes[i][j]?=?n;
???????????????????continue;
???????????????}
???????????????//左右邊界節點
???????????????if((j==0||j==str_triangle[i].length-1)){
???????????????????if(i==1){//第2行的節點
???????????????????????int?value?=?c(str_triangle[0][0])+c(str_triangle[i][j]);
???????????????????????List?ph?=?triangle_nodes[0][0].getPath();
???????????????????????n.addPath(ph);
???????????????????????n.addPath(currentPath);
???????????????????????n.setValue(value);
???????????????????????ph?=?null;
???????????????????}else{//0,1行以下的其他邊界節點
?????????????????????int?value?=?j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
?????????????????????????c(str_triangle[i][j])+triangle_nodes[i-1][j-1].getValue();
?????????????????????List?ph?=?j==0?triangle_nodes[i-1][j].getPath():
?????????????????????????triangle_nodes[i-1][j-1].getPath();
?????????????????????n.addPath(ph);
?????????????????????n.addPath(currentPath);
?????????????????????n.setValue(value);
???????????????????}
???????????????}else{//除邊界節點外其他節點
???????????????????????Node?node1?=?triangle_nodes[i-1][j-1];
???????????????????????Node?node2?=?triangle_nodes[i-1][j];
???????????????????????Node?bigger?=?max(node1,node2);
???????????????????????List?ph?=?bigger.getPath();
???????????????????????n.addPath(ph);
???????????????????????n.addPath(currentPath);
???????????????????????int?val?=?bigger.getValue()+c(str_triangle[i][j]);
???????????????????????n.setValue(val);
???????????????}
??????????????triangle_nodes[i][j]?=?n;?
??????????????n?=?null;
????????????}//end?of?for?j
????????}//end?of?for?i
????}
????
????private?Node?max(Node?node1,Node?node2){
????????int?i1?=?node1.getValue();
????????int?i2?=?node2.getValue();
????????return?i1>i2?node1:node2;
????}
????
????private?int?c(String?s){
????????return?Integer.parseInt(s);
????}
????
????//找出最佳路徑
????private?void?findPath(){
????????if(this.triangle_nodes==null)return;
????????int?max?=?0;
????????int?mi?=?0;
????????int?mj?=?0;
????????for(int?i?=?0?;?i?<?triangle_nodes.length;?i++){
????????????for(int?j?=?0?;?j<triangle_nodes[i].length;j++){
????????????????int?t?=?triangle_nodes[i][j].getValue();
????????????????if(t>max){
????????????????????max?=?t;
????????????????????mi?=?i;
????????????????????mj?=?j;
????????????????}
????????????}
????????}
????????System.out.println("Max?Path:"+triangle_nodes[mi][mj].getPath());
????????System.out.println("Max?Value:"+max);
????}
????
????public?static?void?main(String[]?args)throws?Exception{
????????DynamicSolveTrianglePath?dsp?=?new
???????????DynamicSolveTrianglePath();
????}
????
}
用于讀取文件的輔助類
package
?test;
import
?java.io.
*
;
import
?java.util.
*
;
/**?*/
/**
?*??輸入文本格式為
?*??類似這樣一個數字三角形
?*??
?*??????????x
?*?????????x?x
?*????????x?x?x
?*???????x?x?x?x
?*??????x?x?x?x?x?
?*??????
?*??
@author
?zqc
?*?
*/
public
?
class
?ReadTriangle?
{
????
public
?
static
?String?TRIANGLE_FILE?
=
?
"
d:/triangle.txt
"
;
????
????
public
?
static
?String[][]?getTriangle()
{
????????String[][]?rtn;
????????
try
?
{
????????????File?f?
=
?
new
???????????????????File(ReadTriangle.TRIANGLE_FILE);
????????????BufferedReader?br?
=
?
new
?
????????????????BufferedReader(
???????????????
new
?FileReader(f)????????
????????????);
????????????List?l?
=
?
new
?Vector();
????????????String?line?
=
?br.readLine();
????????????
while
(line
!=
null
)
{
????????????????l.add(line.trim());
????????????????line?
=
?br.readLine();
????????????}
????????????
int
?heigth?
=
?l.size();
????????????rtn?
=
?
new
?String[heigth][];
????????????
for
(
int
?i?
=
?
0
?;?i?
<
?heigth?;?i
++
)
{
????????????????String?s?
=
?(String)l.get(i);
????????????????String[]?tk?
=
?s.split(
"
?
"
);
????????????????
int
?tklen?
=
?tk.length;
????????????????rtn[i]?
=
?
new
?String[tklen];
????????????????
for
(
int
?k?
=
?
0
?;?k?
<
?tklen?;?k
++
)
{
????????????????????rtn[i][k]?
=
?tk[k];
????????????????}
????????????}
????????????
return
?rtn;
????????}
?
catch
?(FileNotFoundException?e)?
{
????????????e.printStackTrace();
????????}
?
catch
?(IOException?e)?
{
????????????e.printStackTrace();
????????}
????????
return
?
null
;
????}
????
}
結果輸出如下:
Max Path:[(0,0), (1,0), (2,0), (3,1), (4,1), (5,2)]
Max Value:39
同樣的方法可以解決很多類似的問題,比如,游戲中的最短路徑;最優化投資問題;背包問題等等.