學(xué)校超市選址問題課程設(shè)計(jì)報(bào)告書

.PAGE.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：學(xué)校超市選址問題專業(yè)班級(jí)學(xué)生學(xué)號(hào)指導(dǎo)教師起止時(shí)間年學(xué)期問題描述對(duì)于某一學(xué)校超市,其他各單位到其的距離不同,同時(shí)各單位人員去超市的頻度也不同。請(qǐng)為超市選址,要求實(shí)現(xiàn)總體最優(yōu)。1、需求分析核心問題:求最短路徑<選址的要求就是超市到各單位權(quán)值之和最少>數(shù)據(jù)模型〔邏輯結(jié)構(gòu):帶權(quán)有向圖<權(quán)值計(jì)算:距離*頻度>存儲(chǔ)結(jié)構(gòu):typedefstruct{ stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; intvexnum;//,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)解。運(yùn)行環(huán)境DEV-C++2、概要設(shè)計(jì)Floyd算法利用動(dòng)態(tài)規(guī)劃思想,通過(guò)把問題分解為子問題來(lái)解決任意兩點(diǎn)見的最短路徑問題。設(shè)G=<V,E,w>是一個(gè)帶權(quán)有向圖,其邊V={v1,v2,…,vn}。對(duì)于k≤n,考慮其結(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á)式。上述討論可以歸納為如下遞歸式：原問題轉(zhuǎn)化為對(duì)每個(gè)i和j求,或者說(shuō)求矩陣開始流程圖開始MMain〔輸入基本信息輸入基本信息GreatMgraph〔GhGreatMgraph〔Gh建立鄰接矩陣的存儲(chǔ)結(jié)構(gòu)建立鄰接矩陣的存儲(chǔ)結(jié)構(gòu)Floyd算法Floyd算法NNYA[i][j]==INF,i!=jYA[i][j]==INF,i!=ji到j(luò)不存在路徑i到j(luò)不存在路徑Floyed〔GhFloyed〔Gh輸出i->j的路徑和路徑長(zhǎng)度輸出i->j的路徑和路徑長(zhǎng)度輸出超市的最佳地址：i輸出超市的最佳地址：i結(jié)束結(jié)束詳細(xì)設(shè)置第一步,讓所有路徑加上中間頂點(diǎn)1,取A[i][j]與A[i][1]+A[1][j]中較小的值作A[i][j]的新值,完成后得到A<1>,如此進(jìn)行下去,當(dāng)?shù)趉步完成后,A〔k[i][j]表示從i到就且路徑上的中間頂點(diǎn)的路徑的序號(hào)小于或等于k的最短路徑長(zhǎng)度。當(dāng)?shù)趎-1步完成后,得到A〔n-1,A〔n-1即所求結(jié)果。A〔n-1[i][j]表示從i到j(luò)且路徑上的中點(diǎn)頂點(diǎn)的序號(hào)小于或等于n-1的最短路徑長(zhǎng)度,即A<n-1>[i][j]表示從i到j(luò)的最短路徑長(zhǎng)度。代碼表示如下：voidFloyed<Mgraph*G>//帶權(quán)有向圖求最短路徑floyd算法{ intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; inti,j,k,pre; intcount[MAXVEX]; for<i=0;i<G->n;i++>//初始化A[][]和path[][]數(shù)組 for<j=0;j<G->n;j++>//置初值； { A[i][j]=G->dis[i][j]; path[i][j]=-1; count[i]=0; } for<k=0;k<G->n;k++>//k代表運(yùn)算步驟 { for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> if<A[i][j]><A[i][k]+A[k][j]>>//從i經(jīng)j到k的一條路徑更短 { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } cout<<endl<<"Floyed算法求解如下:"<<endl; for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> { if<i!=j> { cout<<""<<i<<"->"<<j<<";"; if<A[i][j]==INF> { if<i!=j> cout<<"不存在路徑"<<"\n"<<endl; } else { cout<<"路徑長(zhǎng)度為:"<<A[i][j]<<"\n"; cout<<"路徑為:"<<i<<"*"; pre=path[i][j]; while<pre!=-1> { cout<<pre<<"\n"; pre=path[pre][j]; } cout<<j<<endl; } } }//以下為選擇總體最優(yōu)過(guò)程,然后確址； for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> { if<A[i][j]==INF> count[i]=0; else count[i]=1; } for<i=0;i<G->n;i++> if<count[i]> { for<j=0;j<G->n;j++> if<i!=j>A[i][i]+=A[j][i]; } k=0; for<i=0;i<G->n;i++> { if<count[i]> if<A[k][k]>A[i][i]> k=i; } cout<<"超市的最佳地址為:"<<G->vexs[k]<<endl;}4、調(diào)試分析測(cè)試數(shù)據(jù)：輸入：?jiǎn)挝粋€(gè)數(shù)4單位間的路徑數(shù)6第0個(gè)單位名稱a第1個(gè)單位名稱b第2個(gè)單位名稱c第3個(gè)單位名稱d相通兩單位之間的距離0,131,222,320,330,241,31第0個(gè)單位去超市的頻率1第1個(gè)單位去超市的頻率2第2個(gè)單位去超市的頻率4第3個(gè)單位去超市的頻率3輸出：相通兩單位之間的路徑和他的長(zhǎng)度結(jié)果：附加程序#include<string.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include"malloc.h"#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;//為復(fù)雜的聲明定義簡(jiǎn)單的別名typedefstruct{ Vextypevexs[MAXVEX][MAXVEX];//單位名稱〔頂點(diǎn)信息； intadj[MAXVEX][MAXVEX]; //單位之間的相通情況〔是否有邊； intdis[MAXVEX][MAXVEX]; //單位間距離〔邊的長(zhǎng)度； intf[MAXVEX]; //各單位去超市的頻率； intn; //頂點(diǎn)數(shù)和邊數(shù)； inte;}Mgraph;voidCreatMgraph<Mgraph*G>//實(shí)現(xiàn)的是以鄰接矩陣存儲(chǔ)圖,并能將矩陣打印,同時(shí)實(shí)現(xiàn)了圖的深度遍歷{ inti,j,k; printf<"請(qǐng)輸入單位個(gè)數(shù):\n">; scanf<"%d",&<G->n>>; printf<"請(qǐng)輸入單位間的路徑數(shù):\n">; scanf<"%d",&<G->e>>; printf<"請(qǐng)輸入單位名稱:\n">; for<i=0;i<G->n;i++> { printf<"請(qǐng)輸入第%d個(gè)單位名稱:\n",i>; scanf<"%s",&G->vexs[i]>; } for<i=0;i<G->n;i++> //結(jié)構(gòu)體的初始化； for<j=0;j<G->n;j++> { G->adj[i][j]=0; G->dis[i][j]=0; G->f[i]=0; } for<k=0;k<G->e;k++> { printf<"請(qǐng)輸入相通的兩單位<輸入格式:i,j>:\n">; scanf<"%d,%d",&i,&j>;//在距離上體現(xiàn)為無(wú)向； printf<"請(qǐng)輸入相同兩個(gè)單位間的距離<格式：dis>：\n">; scanf<"%d",&<G->dis[i][j]>>; G->adj[i][j]=1; G->adj[j][i]=1; G->dis[j][i]=G->dis[i][j]; } for<k=0;k<G->n;k++> { printf<"請(qǐng)輸入第%d個(gè)單位去超市的相對(duì)頻率:\n",k>; scanf<"%d",&<G->f[k]>>; } for<i=0;i<G->n;i++> //以距離和頻率之積作為權(quán)值； for<j=0;j<G->n;j++> { G->dis[i][j]*=G->f[i];//最終權(quán)值非完全無(wú)向； if<G->adj[i][j]==0&&i!=j> G->dis[i][j]=INF; }}voidFloyed<Mgraph*G>//帶權(quán)有向圖求最短路徑floyd算法{ intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; inti,j,k,pre; intcount[MAXVEX]; for<i=0;i<G->n;i++>//初始化A[][]和path[][]數(shù)組 for<j=0;j<G->n;j++>//置初值； { A[i][j]=G->dis[i][j]; path[i][j]=-1; count[i]=0; } for<k=0;k<G->n;k++>//k代表運(yùn)算步驟 { for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> if<A[i][j]><A[i][k]+A[k][j]>>//從i經(jīng)j到k的一條路徑更短 { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } cout<<endl<<"Floyed算法求解如下:"<<endl; for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> { if<i!=j> { cout<<""<<i<<"->"<<j<<";"; if<A[i][j]==INF> { if<i!=j> cout<<"不存在路徑"<<"\n"<<endl; } else { cout<<"路徑長(zhǎng)度為:"<<A[i][j]<<"\n"; cout<<"路徑為:"<<i<<"*"; pre=path[i][j]; while<pre!=-1> { cout<<pre<<"\n"; pre=path[pre][j]; } cout<<j<<endl; } } }//以下為選擇總體最優(yōu)過(guò)程,然后確址； for<i=0;i<G->n;i++> for<j=0;j<G->n;j++> { if<A[i][j]==INF> count[i]=0; else count[i]=1; } for<i=0;i<G->n;i++> if<count[i]> {