5/5實驗4動態規劃算法設計《算法分析與設計》實驗報告

實驗四動態規劃算法設計

姓名xxxxxxx學號xxxxxxxx班級xxxxxxxx

時間：xxxxxx地點：xxxx

同組人：無

指導教師：xxxxxx

實驗目的

1.掌握動態規劃法算法設計的一般原理和方法。

2.理解動態規劃向前處理和向后處理的思想，掌握遞推公式的求解方法。

3.掌握多段圖、每對結點之間最短路徑的計算算法。

4.能用動態規劃法設計算法求解一般問題。

實驗內容

1.設計求解多段圖問題的動態規劃程序，上機調試通過。

2.設計求解每對結點之間最短路徑問題的動態規劃程序，上機調試通過。

3.準備幾個多段圖和幾個道路交通圖的數據。

4.輸入求解多段圖問題的動態規劃程序，并用準備的數據調試通過。

5.輸入每對結點之間最短路徑問題的動態規劃程序，并用準備的數據調試通

過。

實驗環境

硬件：Intel(R)Pentium(R)CPURAM:4G

軟件：Myeclipse2013

編程語言：Java實驗前準備

1、程序設計：見附1

實驗步驟

1、準備實驗數據。

準備幾個多段圖和幾個道路交通圖的數據。

多段圖的實驗數據和道路交通圖的數據均可利用程序生成(ReadEdgeData.java的randMultGraph和radomDirectedGraph)；

其中多段圖的生成原則是n個結點分為k段，且每段大約為4到5個結點，第一個和最后一個結點要和相鄰段所有結點相連，中間段的結點與相鄰段的結點至少要有一個結點相鄰，每條邊的成本隨機生成。

道路交通圖至少則是生成有圖的方式，n個結點有（n*n）*4/5使邊數不至于多，也不至于少。

將生成的邊以數對的形式存于文本文件中，如下圖，其中第一行分別為結點數和邊數。剩下的若干行表示每條表的兩個結點和成本。在需要的時間通過讀取文本文件來獲取數據。

2、多段圖問題的動態規劃程序

根據算法設計的多段圖向前處理法的sparks語言，寫出相應的java程序，并調試驗證通過。其中邊是以鄰接表的形式表現出來更方便顯示點之間的鄰接關系。

int[]COST=newint[n+1];//用來記錄從j到最后一個結點的最小權值

int[]D=newint[n];//D[j]用來表示j到最后一個結點最短路徑上的后續一個結點

for(intj=n-1;j>=1;j--){

intminCost=Graph.MAXCOST;

intr=1;

LinkedListcostList=G.getCostList()[j];

for(Edgeedge:costList){//找到j之后的一個點r，使

edge.cost+COST[r]取最小值，并將最小值賦給minCost

intv=edge.v;//edge.cost代表j到v的權值

if(v>j

minCost=edge.cost+COST[v];

}

}

COST[j]=minCost;//將從j到最后一個結點的最短路徑的權值賦給COST[j]D[j]=r;

}

P[1]=1;//第一個結點

P[k]=n;//最后一個結點

for(intj=2;jcostList=G.getCostList()[j];

for(Edgeedge:costList){//找到j之后的一個點r，使

edge.cost+COST[r]取最小值，并將最小值賦給minCost

intv=edge.v;//edge.cost代表j到v的權值

if(v>j

2、最短路徑問題AllPaths.java

importjava.io.File;

publicclassAllPaths{

/**

*每對結點之前的最短路徑長度

*

*@paramargs

*/

publicstaticvoidmain(String[]args){

intZ=10;//數據個數

inttp=21;//文件的初始編號

long[][]D=newlong[Z][2];//記錄數據量和運行時間的數組

StringsurDir="E:\\我的文檔\\大三下\\算法分析與設計\\實驗\\實驗4動態規劃算法設計\\data";

for(intt=0;t0){

System.out.print("==>");

}

top--;

}

if(DIST[i]();

}

for(inti=1;ile=newLinkedList();

for(inti=1;ile=newLinkedList();//記錄所生成的邊for(inti=1;i=countBe){

if(countEn==n-1){

countEn=n;

countBe=n;

}else

if(countEn+pa=newLinkedList();

for(intj=countBe;j<=countEn;j++){

a.add(newInteger(j));

}

for(intj=0;j<kn;j++){

ints=a.size();

intr=(int)(Math.random()*(s));

intv=a.remove(r);

Edgee=newEdge();

e.u=i;

e.v=v;

int

eCost=(int)(Math.random()*(maxCost-minCost)+minCost);

e.cost=eCost;

le.add(e);

}

}

intm=le.size();

Edge[]edge=newEdge[m+1];

for(inti=0;i<le.size();i++){

edge[i+1]=le.get(i);

}

g.edge=edge;

g.m=m;

returng;

}

publicstaticvoidmain(String[]args){

random2();

}

publicstaticvoidrandom2(){

StringdestDir="E:\\我的文檔\\大三下\\算法分析與設計\\實驗\\實驗4動態規劃算法設計\\data";

StringdestName="MultGraph";

intn=12;

intk=5;

intminCost=1;

intmaxCost=n;

for(inti=0;i<10;i++){

Graphg=null;

if((g=randMultGraph(n,k,minCost,maxCost))!=null){

Filedest=newFile(destDir,destName+""+(i)+".txt");

if(writeEdges(dest,g)!=null){

System.out.println(dest+"文件寫入成功！");

}

}

n+=12;

k+=1;

}

}

/*

*生成有向圖

*/

publicstaticvoidrandom1(){

StringdestDir="E:\\我的文檔\\大三下\\算法分析與設計\\實驗\\實驗4動態規劃算法設計\\data";

StringdestName="Edges";

intb=10;//步長值

inttp=21;//文件的初始編號

intn=10;//結點初始值

intm=n*n*2/3;

intminCost=1;

intmaxCost=m;

for(inti=0;i<10;i++){

n=b*(i+1);

m=n*n*4/5;

minCost=1;

maxCost=m*3/5;

Graphg=null;

if((g=radomDirecte