學(xué)校超市選址問題

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告PAGE3-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：學(xué)校超市選址問題 目錄 第1章需求分析 -2-第2章總體設(shè)計 -2-2.1文字描述 -2-2.2程序流程圖 -2-第3章詳細(xì)設(shè)計 -3-3.1數(shù)據(jù)結(jié)構(gòu) -3-3.2功能實(shí)現(xiàn)的算法及思路 -3-3.2.1建立圖的鄰接矩陣 -4-3.2.2迪杰斯特拉算法 -4-3.2.3確定最優(yōu)地址 -4-第4章實(shí)現(xiàn)部分 -5-4.1核心代碼 -5-第5章程序測試 -10-5.1測試數(shù)據(jù) -10-5.2程序運(yùn)行圖 -11-5.3結(jié)果分析 -12-第6章總結(jié) -12-參考文獻(xiàn) -12-第1章需求分析我的課程設(shè)計題目為學(xué)校超市選址問題。對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同，根據(jù)以上這兩個條件，確定學(xué)校的超市要建在什么地方，才能使得方案達(dá)到最優(yōu)。該程序要能夠確定超市的最優(yōu)地址。而這個最有地址只能在所有單位所在地中選擇。通過這個課程設(shè)計，真正理解弗洛伊德算法的思想，鍛煉自主學(xué)習(xí)能力和程序編寫能力，以及能夠處理現(xiàn)實(shí)生活中類似的問題。第2章總體設(shè)計2.1文字描述首先，建立圖的鄰接矩陣。輸入相關(guān)基本數(shù)據(jù)信息，以單位作為圖的頂點(diǎn)，以單位之間的距離與各個單位去超市的頻率之積作為圖的權(quán)值，建立鄰接矩陣。然后，調(diào)用弗洛伊德算法。單位i與j之間，加入過渡點(diǎn)k，若i、k間距離與k、j間距離之和小于i、j間的距離，修改矩陣。如此反復(fù)執(zhí)行下去。完成后，得到i到j(luò)得最短距離。最后，確定最優(yōu)地點(diǎn)。根據(jù)某單位到各個單位的最短距離之和最短，該單位所在地即為最優(yōu)地址。2.2程序流程圖開始開始MMain()函數(shù)輸入數(shù)據(jù)輸入數(shù)據(jù)建立圖的鄰接矩陣建立圖的鄰接矩陣dijkstra算法dijkstra算法i!=j?i!=j?Y輸出i->j的最短距離及路徑輸出i->j的最短距離及路徑輸出最優(yōu)地址輸出最優(yōu)地址結(jié)束結(jié)束第3章詳細(xì)設(shè)計數(shù)據(jù)結(jié)構(gòu)定義一個Graph類來存儲圖的基本信息，代碼如下：#definen4//定義頂點(diǎn)數(shù)#definee8//定義邊數(shù)#define$32767//用$表示無窮大template<classT>classGraph{public: Graph(inta[][5]); voidvalue(intindex);//獲得一個點(diǎn)到各個點(diǎn)的權(quán)值(提取dist數(shù)組中的數(shù)據(jù)) voidchoice();//計算路徑之和選擇最佳位置 voidprint(intindex);//打印路徑 voidall_point();//多次調(diào)用迪杰斯特拉以實(shí)現(xiàn)求多源點(diǎn)路徑的最小路徑 voidshortest(intindex);//核心算法private: Tpath[n+1];//路徑 intdist[n+1];//權(quán)值 Ts[n+1];//集合s保存已求出最短路徑的頂點(diǎn) intarcs[n+1][n+1];//鄰接矩陣 Tv[n+1];//保存頂點(diǎn) inttimes[n+1][n+1];//保存一個頂點(diǎn)到其他頂點(diǎn)的頻度（也包括到自身的頻度為0） intval[n+1][n+1];//保存一個頂點(diǎn)到其他頂點(diǎn)的權(quán)值(也包括到自身的距離為0)};3.2功能實(shí)現(xiàn)的算法及思路3.2.1建立圖的鄰接矩陣主要是通過多次調(diào)用迪杰斯特拉算法來完成對每個點(diǎn)求出最短路徑。定義數(shù)組dist[n+1][n+1]存儲單位間距離，數(shù)組times[n+1]存儲各單位去超市的頻率，數(shù)組arcs[n+1][n+1]表示單位間相通情況,數(shù)組path[n+1]保存路徑,數(shù)組val[n+1]依次存儲個點(diǎn)的dist數(shù)據(jù)。如果兩單位i、j相通，則令arcs[i][j]=相應(yīng)的權(quán)值，不相通則為$表示無窮大，自身到自身的權(quán)值為0。3.2.2迪杰斯特拉德算法首先，引進(jìn)一個輔助向量D，它的每個分量D表示當(dāng)前所找到的從始點(diǎn)v到每個終點(diǎn)vi的最短路徑的長度。如D[3]=2表示從始點(diǎn)v到終點(diǎn)3的路徑相對最小長度為2。這里強(qiáng)調(diào)相對就是說在算法過程中D的值是在不斷逼近最終結(jié)果但在過程中不一定就等于最短路徑長度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長度為D[j]=Min{D|vi∈V}的路徑就是從v出發(fā)的長度最短的一條最短路徑。此路徑為(v,vj)。那么，下一條長度次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。一般情況下，假設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)上的權(quán)值，或者是D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。迪杰斯特拉算法描述如下：1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長度的初值為D=arcs[LocateVex(G,v),i]vi∈V2）選擇vj，使得D[j]=Min{D|vi∈V-S}3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長度。3.2.3確定最優(yōu)地址將數(shù)組a[i][j]中每行值之和放入每行的首地址中，即a[i][1]+=a[i][j]。然后比較每行首地址中的值。令k=1，若a[k][1]>a[i][1]，則將i賦給k.。如此循環(huán)n次。最后，輸出unitname[k]，即為所求的地址。第4章實(shí)現(xiàn)部分實(shí)現(xiàn)代碼/***********************************迪杰斯特拉算法 單源點(diǎn)最短路徑 有向圖利用鄰接 矩陣進(jìn)行存儲************************************/#ifndef_DIJKSTRA_H_#define_DIJKSTRA_H_#definen4//定義頂點(diǎn)數(shù)#definee8//定義邊數(shù)#define$32767//用$表示無窮大template<classT>classGraph{public: Graph(inta[][5]); voidvalue(intindex);//獲得一個點(diǎn)到各個點(diǎn)的權(quán)值(提取dist數(shù)組中的數(shù)據(jù)) voidchoice();//計算路徑之和選擇最佳位置 voidprint(intindex);//打印路徑 voidall_point();//多次調(diào)用迪杰斯特拉以實(shí)現(xiàn)求多源點(diǎn)路徑的最小路徑 voidshortest(intindex);//核心算法private: Tpath[n+1];//路徑 intdist[n+1];//權(quán)值 Ts[n+1];//集合s保存已求出最短路徑的頂點(diǎn) intarcs[n+1][n+1];//鄰接矩陣 Tv[n+1];//保存頂點(diǎn) inttimes[n+1][n+1];//保存一個頂點(diǎn)到其他頂點(diǎn)的頻度（也包括到自身的頻度為0） intval[n+1][n+1];//保存一個頂點(diǎn)到其他頂點(diǎn)的權(quán)值(也包括到自身的距離為0)};#endif//dijkstra類的實(shí)現(xiàn)：#include<iostream>#include"dijkstra.h"usingnamespacestd;template<classT>Graph<T>::Graph(inta[][5]){ for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { arcs[i][j]=a[i][j];//賦值操作 val[i][j]=0; } } for(inti=1;i<=n;i++) { cout<<"請輸入頂點(diǎn)："; cin>>v[i]; } for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { if(i!=j) { cout<<"請輸入"<<v[i]<<"到"<<v[j]<<"的頻度:"; cin>>times[i][j]; } else { times[i][j]=0;//自己到自己的頻度為0； } } cout<<endl; } system("pause"); system("cls");}template<classT>voidGraph<T>::all_point()//多次調(diào)用算法獲得路徑{ for(inti=1;i<=n;i++) { shortest(i); print(i); value(i); }}template<classT>voidGraph<T>::shortest(intindex){ for(inti=1;i<=n;i++)//數(shù)據(jù)初始 { dist[i]=arcs[index][i]; s[i]=0; if((i!=index)&&(dist[i]<$)) { path[i]=v[index]; } else { path[i]=0; } } s[index]=v[index];//將源點(diǎn)并入S中 //dist[index]=0; for(inti=1;i<n;i++)//掃描一行獲得權(quán)值 { intmin=$; intu=index; for(intj=1;j<=n;j++) { if((!s[j])&&(dist[j]<min)) { min=dist[j];//選取權(quán)值最小的路徑 u=j;//并記錄下該頂點(diǎn)號的位置 } } s[u]=v[u];//將求出的最短路徑的頂點(diǎn)號并入S中 for(intw=1;w<=n;w++) { if((!s[w])&&(arcs[u][w]<$)&&(dist[u]+arcs[u][w]<dist[w]))//更新dist[]中的數(shù)據(jù) { dist[w]=dist[u]+arcs[u][w];//權(quán)值更新 path[w]=v[u];//路徑更新 } } } }template<classT>voidGraph<T>::print(intindex)//打印路徑{ for(inti=1;i<=n;i++) { if(i!=index) { cout<<dist[i]<<":"; cout<<v[i];//輸出終點(diǎn) Tpre=path[i]; while(pre!=0) { cout<<"←"<<pre; pre=path[pre]; } cout<<endl; } } cout<<"********************************************"<<endl;}template<classT>voidGraph<T>::value(intindex)//獲取權(quán)值{ for(inti=1;i<=n;i++) { val[index][i]=dist[i]; }}template<classT>voidGraph<T>::choice()//計算權(quán)值{ for(inti=1;i<=n;i++) { val[i][0]=0;//用零號單元保存路徑之和,數(shù)據(jù)初始化 } /*for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { cout<<times[i][j]<<""; } cout<<endl; }*/ for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { val[i][0]+=(val[i][j]*times[i][j]);//開始計算權(quán)值與頻度之積 } } intp=1;//記錄最佳位置 intmin=val[1][0]; for(intk=1;k<=n;k++) { if(val[k][0]<min)//路徑之和達(dá)到最小的即是最佳位置 { min=val[k][0]; p++; } cout<<v[k]<<"的路徑之和為："<<val[k][0]<<endl; } cout<<"******************************************"<<endl; cout<<"******************************************"<<endl; cout<<endl<<""<<v[p]<<"的路徑之和為："<<min<<"達(dá)到最小"<<endl; cout<<endl<<""<<"超市的位置選擇在："<<v[p]<<"為最佳方案!"<<endl;}//main()函數(shù)引用部分/*該程序在vs2010旗艦版中順利編譯并且運(yùn)行結(jié)果正確如果因?yàn)関c6.0編譯環(huán)境下造成無法運(yùn)行，則應(yīng)修改代碼中的循環(huán)變量，因?yàn)関c6.0對變量的作用域控制不夠嚴(yán)謹(jǐn)導(dǎo)致程序無法運(yùn)行。*****************************************************注意建立工程時應(yīng)選擇win32控制臺，并且應(yīng)對上述代碼自行建立dijkstea.h，dijkstra.cpp和main.cpp三個工程文件*/#include<iostream>#include"dijkstra.cpp"intmain(){ /*inta[6][6]={-1,-1,-1,-1,-1,-1, -1,0,10,$,30,100, -1,