學校超市選址問題

1、PAGE PAGE 2數(shù)據(jù)結構課程設計報告設計題目： 學校超市選址問題專 業(yè)班 級學 生學 號指導教師 起止時間 2009.12.282009.12.31 2009年 秋季 學期數(shù)據(jù)結構課程設計PAGE 17 第 1 頁1、問題描述對于某一學校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。2、需求分析核心問題: 求最短路徑(選址的要求就是超市到各單位權值之和最少)數(shù)據(jù)模型（邏輯結構）: 帶權有向圖 (權值計算: 距離*頻度)存儲結構: typedef struct string vexsMAX_VERTEX_SIZE; int arcsMAX

2、_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一對頂點之間的最短路徑) 輸入數(shù)據(jù): 各單位名稱，距離，頻度，單位個數(shù)輸出數(shù)據(jù): 所選單位名稱總體思路:如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離/最小權值。 假設頂點個數(shù)有n個，那么就得到n*n的一張表格，arcs(i,j)表示i單位到j單位的最短距離/最小權值 , 這張表格中和最小的那一行(假設為第t行)，那么超市選在t單位處就是最優(yōu)解。3、開發(fā)環(huán)境硬件環(huán)境：PC兼容機軟件環(huán)境：DEV-C+5操作系統(tǒng)：Wi

3、ndows XP4、算法設計思想Floyd算法利用動態(tài)規(guī)劃思想，通過把問題分解為子問題來解決任意兩點間的最短路徑問題。設G=(V, E, w)是一個帶權有向圖，其邊V=v1, v2, , vn。對于kn，考慮其結點V的一個子集。對于V中任何兩個結點vi、vj，考慮從vi到vj的中間結點都在vk中的所有路徑，設是其中最短的，并設的路徑長度為。如果結點vk不在從vi到vj的最短路徑上，則；反之則可以把分為兩段，其中一段從vi到vk，另一段從vk到vj，這樣便得到表達式。上述討論可以歸納為如下遞歸式：原問題轉化為對每個i和j求，或者說求矩陣。利用上述遞歸表達式，串行Floyd算法可以寫成下面的樣子：

4、a）初始化：Du,v=Au,vb)For k:=1 to n For i:=1 to n For j:=1 to n If Di,jDi,k+Dk,j Then Di,j:=Di,k+Dk,j;c)算法結束：D即為所有點對的最短路徑矩陣算法包括三個循環(huán)，每個循環(huán)需要運行步驟n，最內(nèi)部的循環(huán)體可以在常數(shù)時間內(nèi)完成，因此算法的復雜度為：O(n3)。5、流程圖開始開始MMain（）輸入基本信息輸入基本信息GreatMgraph（Gh）GreatMgraph（Gh）建立鄰接矩陣的存儲結構建立鄰接矩陣的存儲結構Floyd算法Floyd算法NNYAij=INF,i!=jYAij=INF,i!=ji到j不存

5、在路徑i到j不存在路徑Floyed（Gh）Floyed（Gh）輸出i-j的路徑和路徑長度輸出i-j的路徑和路徑長度輸出超市的最佳地址：i輸出超市的最佳地址：i結束結束6、課程設計過程中的關鍵算法Floyd算法表述：第一步，讓所有路徑加上中間頂點1，取Aij與Ai1+A1j中較小的值作Aij的新值，完成后得到A(1),如此進行下去，當?shù)趉步完成后，A（k）ij表示從i到就且路徑上的中間頂點的路徑的序號小于或等于k的最短路徑長度。當?shù)趎-1步完成后，得到A（n-1），A（n-1）即所求結果。A（n-1）ij表示從i到j且路徑上的中點頂點的序號小于或等于n-1的最短路徑長度，即A(n-1)ij表示從

6、i到j的最短路徑長度。代碼表示如下：void Floyed(Mgraph *G) /帶權有向圖求最短路徑floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+) /初始化A和path數(shù)組for(j=0;jn;j+) /置初值；Aij=G-disij;pathij=-1;counti=0;for(k=0;kn;k+) /k代表運算步驟for(i=0;in;i+)for(j=0;jn;j+)if(Aij(Aik+Akj) /從i經(jīng)j到k的一條路徑更短Aij=Aik+Akj;pathi

7、j=k;coutendlFloyed算法求解如下:endl;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout不存在路徑nendl;elsecout路徑長度為:Aijn;cout路徑為:i ;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下為選擇總體最優(yōu)過程，然后確址；for(i=0;in;i+)for(j=0;jn;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;in;i+)if(counti)f

8、or(j=0;jn;j+)Ai0+=Aij;for(i=0;in;i+)k=0;if(counti)if(Ak0Ai0)k=i;cout超市的最佳地址為:vexskendl;7、測試及結果測試數(shù)據(jù)：輸入：單位個數(shù)、單位間的路徑數(shù)、單位名稱、相通兩單位以及之間的距離、和各單位去超市的頻率輸出：相通兩單位之間的路徑和他的長度結果：8、總結與收獲這次的程序軟件基本上運行成功，可以簡單的對已經(jīng)輸入的數(shù)據(jù)進行計算，求出超市的最佳選址單位。但是程序較小，功能不全面，只是理論，并未實踐。同時，這次數(shù)據(jù)結構課程設計讓我們感觸很深，使我們每個人都了解到的學習不應該只局限于我們的課本，因為課本上告訴我們的只是很有

9、限的一部分，所涉及的面也是狹窄的。但是怎樣在有限的范圍內(nèi)學習到無限的知識呢？那就要我們自己懂得競爭，懂得自學，懂得充分利用身邊的任何資源。應該說，我們在這次的課程設計中學到了很多知識，這并不僅僅包括書本上的知識，更重要的是我們學會了如何去和別人交流，怎樣用語言去實現(xiàn)自己的想法，在這個過程中使我懂得了勤學好問的重要性。雖然在我的程序中有一部分是從網(wǎng)上搜索得來的，但我竭力將所獲得的信息變成自己的資源。在我動手上機操作的同時，我在了解和看懂的基礎上有所改變和創(chuàng)新，但是在我的程序軟件中還有部分的不足，需要加以更新。同時，通過這次課程設計，我們都意識到了自己動手實踐的弱勢，特別是在編程方面，于是我們知道

10、了計算機的實踐操作是很重要的，只有通過上機編程才能充分的了解自己的不足。相信通過這次的課程設計，更讓我深刻意識到自己在學習中的弱點，同時也找到了克服這些弱點的方法，這也是一筆很大的資源。在以后的時間中，我應該利用更多的時間去上機實驗，多編寫程序，相信不久后我的編程能力都會有很大的提高。經(jīng)過這次課程設計，通過對程序的編制，調(diào)試和運行，使我更好的掌握了圖基本性質和關于選址問題的解決方法，熟悉了各種調(diào)用的數(shù)據(jù)類型，在調(diào)試和運行過程中使我更加的了解和熟悉程序運行的環(huán)境，提高了我對程序調(diào)試分析的能力和對錯誤的糾正能力。這次數(shù)據(jù)結構的程序設計，對于我來說是一個挑戰(zhàn)。我對數(shù)據(jù)結構的學習在程序的設計中也有所體

11、現(xiàn)。課程設計是培養(yǎng)學生綜合運用所學知識、發(fā)現(xiàn)、提出、分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對學生實際工作能力的具體訓練和考察過程。隨著科學技術發(fā)展的日新月異，當今計算機應用在生活中可以說得是無處不在。因此作為二十一世紀的大學來說掌握計算機開發(fā)技術是十分重要的。在整個課程程序中，我們充分應用和調(diào)用各個程序模塊，從而實現(xiàn)了此次程序設計的所應該有的功能。在本組看來這就是我們在課程設計是比較成功的，而在這個過程中，讓我們感覺收獲最大的就是我們都能利用這次課程設計學到很多我們在課本上沒有的知識（Floyd算法），充分的發(fā)揮了我們的主動性，使我們自主的去學習。9、參考文獻馬秋菊 主編 數(shù)據(jù)結構（C

12、語言描述） 北京：中國水利水電出版 2006嚴蔚敏 吳偉民 編著 數(shù)據(jù)結構 （C語言版） 北京：清華大學出版社 2002李春葆 蘇光奎 編著 數(shù)據(jù)結構與算法教程 北京：清華大學出版社 2005戴 敏 主編 數(shù)據(jù)結構 北京：機械工業(yè)出版社 2008李春葆 編著 數(shù)據(jù)結構教程上機實驗知道 清華大學出版社 2005附件一： 程序清單#include #include #include #include malloc.h#include #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define

13、INF 32767const int MAXVEX=100;typedef char Vextype;typedef structVextype vexsMAXVEXMAXVEX; /單位名稱（頂點信息）；int adjMAXVEXMAXVEX;/單位之間的相通情況（是否有邊）；int disMAXVEXMAXVEX;/單位間距離（邊的長度）；int fMAXVEX;/各單位去超市的頻率；int n;/頂點數(shù)和邊數(shù)；int e;Mgraph;void CreatMgraph(Mgraph *G) int i,j,k;printf(請輸入單位個數(shù):n);scanf(%d,&(G-n);print

14、f(請輸入單位間的路徑數(shù):n);scanf(%d,&(G-e);printf(請輸入單位名稱:n);for(i=0;in;i+)printf(請輸入第%d個單位名稱:n,i);scanf(%s,&G-vexsi);for(i=0;in;i+) /結構體的初始化；for(j=0;jn;j+)G-adjij=0;G-disij=0;G-fi=0;for(k=0;ke;k+)printf(請輸入相通的兩單位 (輸入格式:i,j):n);scanf(%d,%d,&i,&j);/在距離上體現(xiàn)為無向；printf(請輸入相通兩個單位間的距離(格式：dis)：n);scanf(%d,&(G-disij);G

15、-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;k+)printf(請輸入第%d個單位去超市的相對頻率:n,k);scanf(%d,&(G-fk);for(i=0;in;i+) /以距離和頻率之積作為權值；for(j=0;jn;j+)G-disij*=G-fi; /最終權值非完全無向； if(G-adjij=0&i!=j)G-disij=INF;void Floyed(Mgraph *G) /帶權有向圖求最短路徑floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVE

16、X;for(i=0;in;i+) /初始化A和path數(shù)組for(j=0;jn;j+) /置初值；Aij=G-disij;pathij=-1;counti=0;for(k=0;kn;k+) /k代表運算步驟for(i=0;in;i+)for(j=0;jn;j+)if(Aij(Aik+Akj) /從i經(jīng)j到k的一條路徑更短Aij=Aik+Akj;pathij=k;coutendlFloyed算法求解如下:endl;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout不存在路徑nendl;elsecout路徑長度為:Aijn;cout路徑為:i ;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下為選擇總體最優(yōu)過程，然后確址；for(i=0;in;i+)for(j=0;jn;j