貪心算法 動(dòng)態(tài)規(guī)劃算法 實(shí)驗(yàn)報(bào)告 程序

《貪心算法 動(dòng)態(tài)規(guī)劃算法 實(shí)驗(yàn)報(bào)告 程序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、計(jì)算機(jī)算法課程實(shí)驗(yàn)報(bào)告每對(duì)結(jié)點(diǎn)間最短路徑院系：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：學(xué)號(hào)：U200814470Partone貪心法實(shí)現(xiàn)最短路徑一、實(shí)驗(yàn)?zāi)康脑O(shè)計(jì)一個(gè)C程序，實(shí)現(xiàn)求解單源點(diǎn)最短路徑問題。二、實(shí)驗(yàn)要求本實(shí)驗(yàn)要求輸出最短路徑值以及最短路徑三、實(shí)驗(yàn)內(nèi)容與原理單源點(diǎn)最短路徑問題，即，已知一個(gè)n結(jié)點(diǎn)有向圖G＝（V,E）和邊的權(quán)函數(shù)c（e），求由某指定結(jié)點(diǎn)V0到其他各個(gè)結(jié)點(diǎn)的最短路徑，這里還假定所有的權(quán)都是正的。為了制定產(chǎn)生最短路徑的貪心算法，對(duì)于這個(gè)問題應(yīng)該想出一個(gè)多級(jí)解決辦法和一種最優(yōu)的量度標(biāo)準(zhǔn)。方法之一是逐條構(gòu)造這些最短路徑，可以使用迄今已生成的所有路徑長(zhǎng)度之

2、和作為一種量度，為了使這一量度達(dá)到最小，其單獨(dú)的每一條路徑都必須具有最小長(zhǎng)度。使用這一量度標(biāo)準(zhǔn)時(shí)，假定已經(jīng)構(gòu)造了i條最短路徑，則下面要構(gòu)造的路徑應(yīng)該是下一條最短的最小長(zhǎng)度路徑。首先，生成從V0到所有其它結(jié)點(diǎn)的最短路徑。然后生成一條到第二近結(jié)點(diǎn)的最短路徑等等。四、程序流程圖關(guān)鍵思想闡述：從v0開始，只通過S中的結(jié)點(diǎn)并且在S外的結(jié)點(diǎn)w初結(jié)束的最短路徑可能會(huì)減小，即DIST（w）的值可能改變。如果長(zhǎng)度改變了，則它必定是由一條從v0開始，經(jīng)過u然后到w的跟段的路徑所造成的。v0到y(tǒng)的路徑以及u到w的路徑上的中間結(jié)點(diǎn)應(yīng)全部在S中。而且，v0到u的路徑必定是這樣一條最

3、短的路徑，否則就不符合DIST（w）的定義英雌，可以得出結(jié)論，如果DIST(w)會(huì)減少，那是由于有一條從v0靜u到w的更短的路，而從u到w的路徑是邊.這條路徑的長(zhǎng)度是DIST(U)+C(u,w)。分析得到程序流程圖如下：五、算法及程序說明本算法使用貪心法設(shè)計(jì)，生成從v0到所有其它結(jié)點(diǎn)的最短路徑的貪心方法就是按照路徑長(zhǎng)度的非降次序生成這些路徑。六、源程序/*單源點(diǎn)最短路徑*/#includeintsearch(int*,int,int,int*,int);main(){/*生成單源點(diǎn)最短路徑的貪心算法*/intCOST[7][7]

4、={{0,20,50,30,200,200,200},{200,0,25,200,200,70,200},{200,200,0,40,25,50,200},{200,200,200,0,55,200,200},{200,200,200,200,0,10,70},{200,200,200,200,200,0,50},{200,200,200,200,200,200,0}};/*COST[i][j]表示成本鄰接矩陣,200表示無(wú)窮大*/intfront_point[7]={0,0,0,0,0,0,0};/*用來(lái)存放各結(jié)點(diǎn)的最短路徑上的前一結(jié)點(diǎn)*/intDIST

5、[7];/*DIST[i]表示第i個(gè)結(jié)點(diǎn)到源結(jié)點(diǎn)的路徑長(zhǎng)度*/intS[7];/*S中表示對(duì)其已經(jīng)生成了最短路徑的那些結(jié)點(diǎn)，S[i]=1表示第i個(gè)結(jié)點(diǎn)在S中，否則不在*/intu,num,i,w,j,k;for(k=0;k<7;k++){/*j對(duì)應(yīng)到其他所有點(diǎn)的最短距離*/for(i=0;i<7;i++){front_point[i]=k;}for(i=0;i<7;i++){S[i]=0;/*初始狀態(tài)時(shí)，所有結(jié)點(diǎn)均不在S中*/DIST[i]=COST[k][i];/*各結(jié)點(diǎn)到源結(jié)點(diǎn)的最短路徑的初始長(zhǎng)度為它們的直接距離*/}S[k]=1;/*將源結(jié)點(diǎn)放入S中

6、*/DIST[k]=0;/*自身到自身的路徑為0*/for(num=2;num<=6;num++){/*加入五個(gè)結(jié)點(diǎn)到S中，最后一個(gè)不需要*/intmin=32767;for(w=0;w<=6;w++){/*找出不在S的結(jié)點(diǎn)中到源結(jié)點(diǎn)直接距離最短的結(jié)點(diǎn)*/if(!S[w]){if(DIST[w]

7、w])

8、*輸出結(jié)果*/printf("v%d",search(front_