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

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

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

3、ndows XP4、算法設(shè)計(jì)思想Floyd算法利用動(dòng)態(tài)規(guī)劃思想，通過(guò)把問(wèn)題分解為子問(wèn)題來(lái)解決任意兩點(diǎn)間的最短路徑問(wèn)題。設(shè)G=(V, E, w)是一個(gè)帶權(quán)有向圖，其邊V=v1, v2, , vn。對(duì)于kn，考慮其結(jié)點(diǎn)V的一個(gè)子集。對(duì)于V中任何兩個(gè)結(jié)點(diǎn)vi、vj，考慮從vi到vj的中間結(jié)點(diǎn)都在vk中的所有路徑，設(shè)是其中最短的，并設(shè)的路徑長(zhǎng)度為。如果結(jié)點(diǎn)vk不在從vi到vj的最短路徑上，則；反之則可以把分為兩段，其中一段從vi到vk，另一段從vk到vj，這樣便得到表達(dá)式。上述討論可以歸納為如下遞歸式：原問(wèn)題轉(zhuǎn)化為對(duì)每個(gè)i和j求，或者說(shuō)求矩陣。利用上述遞歸表達(dá)式，串行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)算法結(jié)束：D即為所有點(diǎn)對(duì)的最短路徑矩陣算法包括三個(gè)循環(huán)，每個(gè)循環(huán)需要運(yùn)行步驟n，最內(nèi)部的循環(huán)體可以在常數(shù)時(shí)間內(nèi)完成，因此算法的復(fù)雜度為：O(n3)。5、流程圖開(kāi)始開(kāi)始MMain（）輸入基本信息輸入基本信息GreatMgraph（Gh）GreatMgraph（Gh）建立鄰接矩陣的存儲(chǔ)結(jié)構(gòu)建立鄰接矩陣的存儲(chǔ)結(jié)構(gòu)Floyd算法Floyd算法NNYAij=INF,i!=jYAij=INF,i!=ji到j(luò)不存

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

6、i到j(luò)的最短路徑長(zhǎng)度。代碼表示如下：void Floyed(Mgraph *G) /帶權(quán)有向圖求最短路徑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代表運(yùn)算步驟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路徑長(zhǎng)度為:Aijn;cout路徑為:i ;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下為選擇總體最優(yōu)過(guò)程，然后確址；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、測(cè)試及結(jié)果測(cè)試數(shù)據(jù)：輸入：?jiǎn)挝粋€(gè)數(shù)、單位間的路徑數(shù)、單位名稱、相通兩單位以及之間的距離、和各單位去超市的頻率輸出：相通兩單位之間的路徑和他的長(zhǎng)度結(jié)果：8、總結(jié)與收獲這次的程序軟件基本上運(yùn)行成功，可以簡(jiǎn)單的對(duì)已經(jīng)輸入的數(shù)據(jù)進(jìn)行計(jì)算，求出超市的最佳選址單位。但是程序較小，功能不全面，只是理論，并未實(shí)踐。同時(shí)，這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讓我們感觸很深，使我們每個(gè)人都了解到的學(xué)習(xí)不應(yīng)該只局限于我們的課本，因?yàn)檎n本上告訴我們的只是很有

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

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

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

12、語(yǔ)言描述） 北京：中國(guó)水利水電出版 2006嚴(yán)蔚敏 吳偉民 編著 數(shù)據(jù)結(jié)構(gòu) （C語(yǔ)言版） 北京：清華大學(xué)出版社 2002李春葆 蘇光奎 編著 數(shù)據(jù)結(jié)構(gòu)與算法教程 北京：清華大學(xué)出版社 2005戴 敏 主編 數(shù)據(jù)結(jié)構(gòu) 北京：機(jī)械工業(yè)出版社 2008李春葆 編著 數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)知道 清華大學(xué)出版社 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; /單位名稱（頂點(diǎn)信息）；int adjMAXVEXMAXVEX;/單位之間的相通情況（是否有邊）；int disMAXVEXMAXVEX;/單位間距離（邊的長(zhǎng)度）；int fMAXVEX;/各單位去超市的頻率；int n;/頂點(diǎn)數(shù)和邊數(shù)；int e;Mgraph;void CreatMgraph(Mgraph *G) int i,j,k;printf(請(qǐng)輸入單位個(gè)數(shù):n);scanf(%d,&(G-n);print

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

15、-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;k+)printf(請(qǐng)輸入第%d個(gè)單位去超市的相對(duì)頻率:n,k);scanf(%d,&(G-fk);for(i=0;in;i+) /以距離和頻率之積作為權(quán)值；for(j=0;jn;j+)G-disij*=G-fi; /最終權(quán)值非完全無(wú)向； if(G-adjij=0&i!=j)G-disij=INF;void Floyed(Mgraph *G) /帶權(quán)有向圖求最短路徑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代表運(yùn)算步驟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路徑長(zhǎng)度為:Aijn;cout路徑為:i ;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下為選擇總體最優(yōu)過(guò)程，然后確址；for(i=0;in;i+)for(j=0;jn;j