學(xué)校超市選址問題課程設(shè)計

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

2、; 核心算法: Floyd算法(弗洛伊德算法-每一對頂點之間的最短路徑) 輸入數(shù)據(jù): 各單位名稱，距離，頻度，單位個數(shù)輸出數(shù)據(jù): 所選單位名稱總體思路:如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離/最小權(quán)值。 假設(shè)頂點個數(shù)有n個，那么就得到n*n的一張表格，arcs(i,j)表示i單位到j(luò)單位的最短距離/最小權(quán)值 , 這張表格中和最小的那一行(假設(shè)為第t行)，那么超市選在t單位處就是最優(yōu)解。運行環(huán)境DEV-C+2、概要設(shè)計Floyd算法利用動態(tài)規(guī)劃思想，通過把問題分解為子問題來解決任意兩點見的最短路徑問題。設(shè)G=(V, E, w)是一個帶權(quán)有向圖，其邊V=v1, v2

3、, , vn。對于kn，考慮其結(jié)點V的一個子集。對于V中任何兩個結(jié)點vi、vj，考慮從vi到vj的中間結(jié)點都在vk中的所有路徑，設(shè)是其中最短的，并設(shè)的路徑長度為。如果結(jié)點vk不在從vi到vj的最短路徑上，則；反之則可以把分為兩段，其中一段從vi到vk，另一段從vk到vj，這樣便得到表達(dá)式。上述討論可以歸納為如下遞歸式：原問題轉(zhuǎn)化為對每個i和j求，或者說求矩陣開始流程圖Main（）輸入基本信息GreatMgraph（Gh）建立鄰接矩陣的存儲結(jié)構(gòu)Floyd算法NYAij=INF,i!=ji到j(luò)不存在路徑Floyed（Gh）輸出i->j的路徑和路徑長度輸出超市的最佳地址：i結(jié)束3、 詳細(xì)設(shè)置

4、第一步，讓所有路徑加上中間頂點1，取Aij與Ai1+A1j中較小的值作Aij的新值，完成后得到A(1),如此進(jìn)行下去，當(dāng)?shù)趉步完成后，A（k）ij表示從i到就且路徑上的中間頂點的路徑的序號小于或等于k的最短路徑長度。當(dāng)?shù)趎-1步完成后，得到A（n-1），A（n-1）即所求結(jié)果。A（n-1）ij表示從i到j(luò)且路徑上的中點頂點的序號小于或等于n-1的最短路徑長度，即A(n-1)ij表示從i到j(luò)的最短路徑長度。代碼表示如下：void Floyed(Mgraph *G) /帶權(quán)有向圖求最短路徑floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre

5、;int countMAXVEX;for(i=0;i<G->n;i+) /初始化A和path數(shù)組for(j=0;j<G->n;j+) /置初值；Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+) /k代表運算步驟for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj) /從i經(jīng)j到k的一條路徑更短Aij=Aik+Akj;pathij=k;cout<<endl<<"Floyed算法求解如下:&q

6、uot;<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<"不存在路徑"<<"n"<<endl;elsecout<<"路徑長度為:"<<Aij<<&quo

7、t;n"cout<<"路徑為:"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl; /以下為選擇總體最優(yōu)過程，然后確址；for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+)if(counti

8、)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji; k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<"超市的最佳地址為:"<<G->vexsk<<endl;4、調(diào)試分析測試數(shù)據(jù)：輸入：單位個數(shù)4單位間的路徑數(shù)6第0個單位名稱a第1個單位名稱b第2個單位名稱c第3個單位名稱d相通兩單位 之間的距離0,1 31,2 22,3 20,3 30,2 41,3 1第0個單位去超市的頻率 1第1個單位去超市的頻率 2第2個單位去超市的頻

9、率 4第3個單位去超市的頻率 3輸出：相通兩單位之間的路徑和他的長度結(jié)果：附加程序#include <string.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXV

10、EX=100;typedef char Vextype; /為復(fù)雜的聲明定義簡單的別名typedef structVextype vexsMAXVEXMAXVEX; /單位名稱（頂點信息）；int adjMAXVEXMAXVEX;/單位之間的相通情況（是否有邊）；int disMAXVEXMAXVEX;/單位間距離（邊的長度）；int fMAXVEX;/各單位去超市的頻率；int n;/頂點數(shù)和邊數(shù)；int e;Mgraph;void CreatMgraph(Mgraph *G) /實現(xiàn)的是以鄰接矩陣存儲圖，并能將矩陣打印，同時實現(xiàn)了圖的深度遍歷int i,j,k;printf("請

11、輸入單位個數(shù):n");scanf("%d",&(G->n);printf("請輸入單位間的路徑數(shù):n");scanf("%d",&(G->e);printf("請輸入單位名稱:n");for(i=0;i<G->n;i+)printf("請輸入第%d個單位名稱:n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+) /結(jié)構(gòu)體的初始化；for(j=0;j<G-&

12、gt;n;j+)G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf("請輸入相通的兩單位 (輸入格式:i,j):n");scanf("%d,%d",&i,&j);/在距離上體現(xiàn)為無向；printf("請輸入相同兩個單位間的距離(格式：dis)：n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;

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

14、MAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+) /初始化A和path數(shù)組for(j=0;j<G->n;j+) /置初值；Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+) /k代表運算步驟for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj) /從i經(jīng)j到k的一條路徑更短Aij=Aik+Akj;pathij=k;cout<

15、<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<"不存在路徑"<<"n"<<endl;elsecout<<&quo

16、t;路徑長度為:"<<Aij<<"n"cout<<"路徑為:"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl; /以下為選擇總體最優(yōu)過程，然后確址；for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j