算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-預(yù)覽頁
【正文】 行解一般來說是不唯一的。決策一旦作出，就不可再更改。如果當(dāng)前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。2. 輸入5個的圖的鄰接矩陣，程序加入統(tǒng)計(jì)prim算法訪問圖的節(jié)點(diǎn)數(shù)和邊數(shù)的語句。 //w通過1與T建立聯(lián)系 dist[w] ←weight(1,w) //w到T的距離 repeatwhile status[t]≠ “tree node” do pick a fringe u with min dist[w] // 選取到T最近的節(jié)點(diǎn) status[u]←“tree node” for each edge(u,w) do 修改w和T的關(guān)系 repeatrepeat2. Prim算法PrimMST(G，T，r){ InitCandidateSet(…)；//初始化：設(shè)置初始的輕邊候選集，并置T=({r}，￠) //物品該放的數(shù)量 int flag。j=n。 i。 for(i=1。 //背包剩余容量 for(i=1。 cu=cugoods[i].w。j++) { goods[0]=goods[j]。 } goods[i+1]=goods[0]。i++) { cout第i件物品要放:。 int j。//定義一個指針 while(j) { cout請輸入物品的總數(shù)量：。 cinM。i=n。 cout請輸入第i件物品的效益:。 } Insertionsort(goods,n)。 cinj。typedef struct ArcCell{ VRType adj。 AdjMatrix arcs。 VRType lowcost。void MiniSpanTree_PRIM(MGraph G, VerTexType u)。 MGraph G。 i++) { for(j = 0。 } coutendl。}void CreateGraph(MGraph amp。 coutinput the number for vexnum and arum:。 i++) { for(j = 0。 coutinputchar for vexs:。 coutendl。 for(i=0。 cintide。 [j][k].adj = weigh。 coutendl。 for ( j = 0。 } } close[j].lowcost = 88。 close[k].adjvex = u。 coutclose[k].adjvex。 close[k].lowcost = 0。 close[j].lowcost = [k][j].adj。}int minimum(closedge close){ int j1=0, client = 88, j2。amp。 } return j2。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計(jì)方法－動態(tài)規(guī)劃。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。us 初始值，uj第j段的最優(yōu)值。1. 編程實(shí)現(xiàn)多段圖的最短路徑問題的動態(tài)規(guī)劃算法。多段圖算法procedure FGRAPH(E，k，n，P) //輸入是按段的順序給結(jié)點(diǎn)編號的，有n個結(jié)點(diǎn) 的k段圖。E且使c(j，r)+COST(r)取最小值 COST(j)←c(j，r)+COST(r) D(j)←r repeat //向前對j1進(jìn)行決策// P(1)←1；P(k)←n； for j←2 to k1 do //找路徑上的第j個節(jié)點(diǎn)// P(j)←D ( P(j1) ) repeat end FGRAPH多段圖問題includeincludeincludedefine MAX_VERTEX_NUM 50typedef struct ArcNode{ int adjvex。typedef struct VNode{ int data。 int vexnum,arum。 if(n 0) return printf(ERROR)。 //圖的弧數(shù) for(m = 0。 } for(m = 1。 scanf(%d,%d,%d,amp。 p = (ArcNode*)malloc(sizeof(ArcNode))。 while(Gvertices[i].data != t) i++。 q = qnextarc)。 int i。 printf([%d],i)。 }}void fgraph(ALGraph G ,int k,int n){ //多段圖ALGraph G，n為結(jié)點(diǎn)數(shù)，k為圖的段數(shù) //輸入是按段的順序給結(jié)點(diǎn)編號 int cost[100]。 node p。 j) //向前處理結(jié)點(diǎn) { p = Gvertices[j].firstArc。 while(p != NULL) { //r是一個的這樣的結(jié)點(diǎn)，權(quán)值c(j,r)+cost[r]取最小值 if((pvalue + cost[padjvex]) min) { min = pvalue + cost[padjvex]。 } cost[j] = value + cost[r]。 for(i = 2。 printf(最小成本路徑為: )。}void main(){ ALGraph g。 scanf(%d, amp。a)。 printf(輸入多段圖的弧的信息（弧頭，弧尾，權(quán)值）\n)。 fgraph(g, k, n)。當(dāng)所有的邊(v,w)都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v的頂點(diǎn)。每個頂點(diǎn)開始均為白色，搜索中被發(fā)現(xiàn)時置為灰色，當(dāng)其鄰接表被完全檢索之后又被置成黑色。4． 修改算法使之可以判斷圖是否存在一個環(huán)。end。 repeat color[u]←Black。 //頂點(diǎn)數(shù)和矩陣int loop=0。G39。G39。 if(color[k]==39。B39。 cout請輸入總邊數(shù)：\n。i++) { for(j=1。W39。 cini。 //有邊的賦值為1 } for(i=1。) DFS(i)。jn。 } if(loop==0) { cout該圖中無環(huán)!endl。 }}實(shí)驗(yàn)五 回溯法1. 理解可用回溯法求解的問題問題P通常要能表達(dá)為對已知的、由n元組(x1，…，xn)組成的狀態(tài)空間E={(x1，…，xn)| xi206。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ǖ男问矫枋觯簆rocedure BACAKTRACE(n) k =1 。n皇后算法procedure NQUEENS(n)X(1)←0；k←1 //k是當(dāng)前行；X(k)是當(dāng)前列//While k0 do //對所有的行執(zhí)行以下語句//{ X(k)←X(k)+1 //移到下一列//While X(k)≤n and not PLACE(k) do X(k)←X(k)十l if X(k)≤n //找到一個位置// then if k=n //是一個完整的解嗎// then print(X) //是，打印這個數(shù)組// else {k←k+1；X(k)←0；} else k←k－1 //回溯//}end NQUEENSinclude include /*檢查可不可以放置一個新的皇后*/bool place(int k, int *X){ int i。 } return true。 while(k 0) { X[k] = X[k] + 1。 //不滿足條件,繼續(xù)搜索下一列位置 if(X[k] = n) //存在滿足條件的列 { if(k == n) //是最后一個皇后,完成搜索 { for(int i = 1。 } else { k = k + 1。 //回溯到前一列 } }}void main(){ int n, i。 printf(||\n\n)。 X = new int[n]。 printf(Press 0 to exit
物理相關(guān)推薦
鄂ICP備17016276號-1