学校超市选址问题课程设计报告书

.PAGE.数据结构课程设计报告设计题目：学校超市选址问题专业班级学生学号指导教师起止时间年学期问题描述对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,要求实现总体最优。1、需求分析核心问题:求最短路径<选址的要求就是超市到各单位权值之和最少>数据模型〔逻辑结构:带权有向图<权值计算:距离*频度>存储结构:typedefstruct{ stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; intvexnum;//,arcnum;}MGraph;核心算法:Floyd算法<弗洛伊德算法-每一对顶点之间的最短路径>输入数据:各单位名称,距离,频度,单位个数．输出数据:所选单位名称．总体思路:如果超市是要选在某个单位,那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个,那么就得到n*n的一张表格,arcs<i,j>表示i单位到j单位的最短距离/最小权值,这张表格中和最小的那一行<假设为第t行>,那么超市选在t单位处就是最优解。运行环境DEV-C++2、概要设计Floyd算法利用动态规划思想,通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=<V,E,w>是一个带权有向图,其边V={v1,v2,…,vn}。对于k≤n,考虑其结点V的一个子集。对于V中任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的所有路径,设是其中最短的,并设的路径长度为。如果结点vk不在从vi到vj的最短路径上,则；反之则可以把分为两段,其中一段从vi到vk,另一段从vk到vj,这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求,或者说求矩阵开始流程图开始MMain〔输入基本信息输入基本信息GreatMgraph〔GhGreatMgraph〔Gh建立邻接矩阵的存储结构建立邻接矩阵的存储结构Floyd算法Floyd算法NNYA[i][j]==INF,i!=jYA[i][j]==INF,i!=ji到j不存在路径i到j不存在路径Floyed〔GhFloyed〔Gh输出i->j的路径和路径长度输出i->j的路径和路径长度输出超市的最佳地址：i输出超市的最佳地址：i结束结束详细设置第一步,让所有路径加上中间顶点1,取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值,完成后得到A<1>,如此进行下去,当第k步完成后,A〔k[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后,得到A〔n-1,A〔n-1即所求结果。A〔n-1[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度,即A<n-1>[i][j]表示从i到j的最短路径长度。代码表示如下：voidFloyed<Mgraph*G>//带权有向图求最短路径floyd算法{ intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; inti,j,k,pre; intcount[MAXVEX]; for<i=0;i<G->n;i++>//初始化A[][]和path[][]数组 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代表运算步骤 { 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到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<<"路径长度为:"<<A[i][j]<<"\n"; cout<<"路径为:"<<i<<"*"; pre=path[i][j]; while<pre!=-1> { cout<<pre<<"\n"; pre=path[pre][j]; } cout<<j<<endl; } } }//以下为选择总体最优过程,然后确址； 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、调试分析测试数据：输入：单位个数4单位间的路径数6第0个单位名称a第1个单位名称b第2个单位名称c第3个单位名称d相通两单位之间的距离0,131,222,320,330,241,31第0个单位去超市的频率1第1个单位去超市的频率2第2个单位去超市的频率4第3个单位去超市的频率3输出：相通两单位之间的路径和他的长度结果：附加程序#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;//为复杂的声明定义简单的别名typedefstruct{ Vextypevexs[MAXVEX][MAXVEX];//单位名称〔顶点信息； intadj[MAXVEX][MAXVEX]; //单位之间的相通情况〔是否有边； intdis[MAXVEX][MAXVEX]; //单位间距离〔边的长度； intf[MAXVEX]; //各单位去超市的频率； intn; //顶点数和边数； inte;}Mgraph;voidCreatMgraph<Mgraph*G>//实现的是以邻接矩阵存储图,并能将矩阵打印,同时实现了图的深度遍历{ inti,j,k; printf<"请输入单位个数:\n">; scanf<"%d",&<G->n>>; printf<"请输入单位间的路径数:\n">; scanf<"%d",&<G->e>>; printf<"请输入单位名称:\n">; for<i=0;i<G->n;i++> { printf<"请输入第%d个单位名称:\n",i>; scanf<"%s",&G->vexs[i]>; } for<i=0;i<G->n;i++> //结构体的初始化； 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<"请输入相通的两单位<输入格式:i,j>:\n">; scanf<"%d,%d",&i,&j>;//在距离上体现为无向； printf<"请输入相同两个单位间的距离<格式：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<"请输入第%d个单位去超市的相对频率:\n",k>; scanf<"%d",&<G->f[k]>>; } for<i=0;i<G->n;i++> //以距离和频率之积作为权值； for<j=0;j<G->n;j++> { G->dis[i][j]*=G->f[i];//最终权值非完全无向； if<G->adj[i][j]==0&&i!=j> G->dis[i][j]=INF; }}voidFloyed<Mgraph*G>//带权有向图求最短路径floyd算法{ intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; inti,j,k,pre; intcount[MAXVEX]; for<i=0;i<G->n;i++>//初始化A[][]和path[][]数组 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代表运算步骤 { 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到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<<"路径长度为:"<<A[i][j]<<"\n"; cout<<"路径为:"<<i<<"*"; pre=path[i][j]; while<pre!=-1> { cout<<pre<<"\n"; pre=path[pre][j]; } cout<<j<<endl; } } }//以下为选择总体最优过程,然后确址； 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]> {