《学校超市选址问题[2].doc22》由会员分享,可在线阅读,更多相关《学校超市选址问题[2].doc22(11页珍藏版)》请在金锄头文库上搜索。
1、课程设计报告课程设计题目:学校超市选址 学生姓名学生姓名:杨婕杨婕 专专 业:软件工程业:软件工程 班班 级级:091115 学学 号:号:0911153009111530 指导教师指导教师:许志文志文2011 年年 6 月月 15 日日11 1 需求分析需求分析核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型(逻辑结构): 带权有向图 (权值计算: 距离*频度)存储结构: typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnu
2、m;MGraph; 核心算法: Floyd 算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称,距离,频度,单位个数输出数据: 所选单位名称总体思路: 如果超市是要选在某个单位,那么先用 floyd 算法得出各顶点间的最短距离/最小权值。 假设顶点个数有 n 个,那么就得到 n*n 的一张表格,arcs(i,j)表示 i 单位到 j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第 t 行),那么超市选在 t 单位处就是最优解。2 2 运行环境运行环境Visual Stdio C+6.0Windows Vista/2003/XP3 3 概要设计概要设计Floy
3、d 算法利用动态规划思想,通过把问题分解为子问题来解决任意两点见的最短路径问题。设 G=(V, E, w)是一个带权有向图,其边 V=v1, v2, , vn。对于 kn,考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi、vj,考虑从 vi 到 vj 的中间结点都在 vk 中的所有路径,设是其中最短的,并设的路径长度为。如果结点 vk 不在从 vi 到 vj 的最短路径上,则;反之则可以把分为两段,其中一段从 vi 到 vk,另一段从 vk 到 vj,这样便得到表达式。上述讨论2可以归纳为如下递归式:原问题转化为对每个 i 和 j 求,或者说求矩阵流程图4 4 详细设计详细设计第一步
4、,让所有路径加上中间顶点 1,取 Aij与 Ai1+A1j中较小的值作 Aij的新值,完成后得到 A(1),如此进行下去,当第 k 步完成后,开始Main( )输入基本信息建立邻接矩阵的存储结构GreatMgraph(Gh )Floyd 算法Aij=INF,i!= j输出 i-j 的路径和路径长度输出超市的最佳地址:i结束Floyed(Gh )Ni 到 j 不存在路 径Y3A(k)ij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于 k 的最短路径长度。当第 n-1 步完成后,得到 A(n-1) ,A(n-1)即所求结果。A(n-1)ij表示从 i 到 j 且路径上的中点顶点的序号小于
5、或等于 n-1 的最短路径长度,即 A(n-1)ij表示从 i 到 j 的最短路径长度。#include #include #include #include “malloc.h“ #include #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define INF 32767 const int MAXVEX=100; typedef char Vextype; typedef struct Vextype vexsMAXVEXMAXVEX; /单位名称(顶点信息) ; int
6、 adjMAXVEXMAXVEX;/单位之间的相通情况(是否有边) ; int disMAXVEXMAXVEX;/单位间距离(边的长度) ; int fMAXVEX;/各单位去超市的频率; int n;/顶点数和边数; int e; Mgraph; #include void CreatMgraph(Mgraph *G) int i,j,k; printf(“请输入单位个数:n“); scanf(“%d“, printf(“请输入单位间的路径数:n“); scanf(“%d“, printf(“请输入单位名称:n“); for(i=0;in;i+) printf(“请输入第%d 个单位名称:n
7、“,i); scanf(“%s“, for(i=0;in;i+) /结构体的初始化; for(j=0;jn;j+)4 G-adjij=0; G-disij=0; G-fi=0; for(k=0;ke;k+) printf(“请输入相通的两单位 (输入格式:i,j):n“); scanf(“%d,%d“,/在距离上体现为无向; printf(“请输入相同两个单位间的距离(格式:dis):n“); scanf(“%d“, G-adjij=1; G-adjji=1; G-disji=G-disij; for(k=0;kn;k+) printf(“请输入第%d 个单位去超市的相对频率:n“,k); s
8、canf(“%d“, for(i=0;in;i+) /以距离和频率之积作为权值; for(j=0;jn;j+) G-disij*=G-fi; /最终权值非完全无向; if(G-adjij=0 void Floyed(Mgraph *G) /带权有向图求最短路径 floyd 算法 int AMAXVEXMAXVEX,pathMAXVEXMAXVEX; int i,j,k,pre; int countMAXVEX; for(i=0;in;i+) /初始化 A和 path数组 for(j=0;jn;j+) /置初值; Aij=G-disij; pathij=-1; counti=0; for(k=0
9、;kn;k+) /k 代表运算步骤 for(i=0;in;i+) for(j=0;jn;j+)5if(Aij(Aik+Akj) /从 i 经 j 到 k 的一条路径更短 Aij=Aik+Akj; pathij=k; coutn;i+) for(j=0;jn;j+) if(i!=j) cout“n;i+) for(j=0;jn;j+) if(Aij=INF) counti=0; else counti=1; for(i=0;in;i+) if(counti) 6for(j=0;jn;j+) if(i!=j)Aii+=Aji; k=0; for(i=0;in;i+) if(counti) if(A
10、kkAii) k=i; coutvexskendl; void main() Mgraph *Gh=NULL; Gh=(Mgraph *)malloc(sizeof(Mgraph); CreatMgraph(Gh); Floyed(Gh); system(“pause“); /*测试数据:输入:单位个数4单位间的路径数6第 0 个单位名称a第 1 个单位名称b第 2 个单位名称c第 3 个单位名称d相通两单位 之间的距离0,1 3 1,2 2 2,3 2 0,3 3 0,2 4 1,3 1第 0 个单位去超市的频率 17第 1 个单位去超市的频率 2第 2 个单位去超市的频率 4第 3 个单位
11、去超市的频率 35 5 调试分析调试分析5.15.1 本题目的关键点之一:本题目的关键点之一:有两个权值:各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难,经过分析这两个值可以合并为一个权值即distance*frequency;这样就使得图的建立轻而易举。5.25.2 本题目的关键点之二:本题目的关键点之二:利用 floyd 算法求出每一对顶点之间的最短路径。5.35.3 本题目的关键点之三:本题目的关键点之三:选出最短路径,即最佳地点应使其到其他单位权值最小。注意:每比较一次 path 应清 0 一次(Path=0) 。6 6 测试结果测试结果6.16.1 输入输入86.
12、26.2 输出输出9总总 结结数据结构课程设计完成了,对我来说这是一项小小的挑战,它不仅检验了我的学习情况,也考验了我的意志力,收获非颇丰!通过一学期的学习,我知道数据结构是一门理论性强、思维抽象、难度较大的课程,是基础课和专业课之间的桥梁。我们应该能透彻地理解各种数据对象的特点,学会数据的组织方法和实现方法,并进一步培养良好的程序设计能力和解决实际问题的能力,而且该课程的研究方法对我们学生在校和离校后的学习和工作,也有着重要的意义。 学以致用,这才是我的目标,课程设计给了我这个机会。数据结构是计算机科学与技术专业的一门核心专业基础课程,在我们专业的课程体系中起着承上启下的作用,学好数据结构对于提高理论认知水平和实践能力有着极为重要10的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题,应该能从中抽象出一个适当的数学模型,该数学模型在计算机内部用相应的数据结构来表示,然后设计一个解此数学模型的算法,再进行编程调试,最后获得问题的解答。 通过数据结构课程实践,加上老师的全力指导,无论是理论知识,还是实践动手能力,我都有了不同程度上的提高。