超市选址问题.docx

2008/2009学年度第二学期

《数据结构》课程设计
说明书

题 目： 学校超市选址问题
班 级：
姓 名：
学 号：
指导教师：
日 期：2009-6-22~2009-6-26

计算机与信息工程系

1、问题描述
对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。
2、需求分析
核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)
数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)
存储结构: typedef struct
{
string vexs[MAX_VERTEX_SIZE];
int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
int vexnum;// ,arcnum;
}MGraph;
核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)
输入数据: 各单位名称，距离，频度，单位个数．
输出数据: 所选单位名称．
总体思路:　如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。
假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。
3、开发环境
1. 硬件环境：PC兼容机
2. 软件环境：Visual C++ 6.0
3. 操作系统：Windows 2000
4、算法设计思想
　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求，或者说求矩阵。
利用上述递归表达式，串行Floyd算法可以写成下面的样子：
a）初始化：D[u,v]=A[u,v]
　　b)　For k:=1 to n
　　 For i:=1 to n
　　 For j:=1 to n
　　 If D[i,j]>D[i,k]+D[k,j]
Then D[i,j]:=D[i,k]+D[k,j];
　　c)　算法结束：D即为所有点对的最短路径矩阵
算法包括三个循环，每个循环需要运行步骤n，最内部的循环体可以在常数时间内完成，因此算法的复杂度为：O(n^3)。
5、流程图
开始

Main（）

输入基本信息

GreatMgraph（Gh）

建立邻接矩阵的存储结构

Floyd算法

N

Y
A[i][j]==INF,i!=j

i到j不存在路径

Floyed（Gh）

输出i->j的路径和路径长度

输出超市的最佳地址：i

结束

6、课程设计过程中的关键算法
Floyd算法表述：
第一步，让所有路径加上中间顶点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的最短路径长度。
代码表示如下：
void Floyed(Mgraph G) //带权有向图求最短路径floyd算法
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
int count[MAXVEX];
for(i=0;in;i++) //初始化A[][]和path[][]数组
for(j=0;jn;j++) //置初值；
{
A[i][j]=G->dis[i][j];
path[i][j]=-1;
count[i]=0;
}
for(k=0;kn;k++) //k代表运算步骤
{
for(i=0;in;i++)
for(j=0;jn;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<n;i++)
for(j=0;jn;j++)
{
if(i!=j)
{
cout<<" "<"<pre<<"\n";
pre=path[pre][j];
}
cout<n;i++)
for(j=0;jn;j++)
{
if(A[i][j]==INF)
count[i]=0;
else
count[i]=1;
}
for(i=0;in;i++)
if(count[i])
{
for(j=0;jn;j++)
A[i][0]+=A[i][j];
}
for(i=0;in;i++)
{
k=0;
if(count[i])
if(A[k][0]>A[i][0])
k=i;
}
cout<<"超市的最佳地址为:"<vexs[k]<小，功能不全面，只是理论，并未实践。
同时，这次数据结构课程设计让我们感触很深，使我们每个人都了解到的学习不应该只局限于我们的课本，因为课本上告诉我们的只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有限的范围内学习到无限的知识呢？那就要我们自己懂得竞争，懂得自学，懂得充分利用身边的任何资源。应该说，我们在这次的课程设计中学到了很多知识，这并不仅仅包括书本上的知识，更重要的是我们学会了如何去和别人交流，怎样用语言去实现自己的想法，在这个过程中使我懂得了勤学好问的重要性。
虽然在我的程序中有一部分是从网上搜索得来的，但我竭力将所获得的信息变成自己的资源。在我动手上机操作的同时，我在了解和看懂的基础上有所改变和创新，但是在我的程序软件中还有部分的不足，需要加以更新。同时，通过这次课程设计，我们都意识到了自己动手实践的弱势，特别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。
相信通过这次的课程设计，更让我深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这也是一笔很大的资源。在以后的时间中，我应该利用更多的时间去上机实验，多编写程序，相信不久后我的编程能力都会有很大的提高。经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。
在整个课程程序中，我们充分应用和调用各个程序模块，从而实现了此次程序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让我们感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识（Floyd算法），充分的发挥了我们的主动性，使我们自主的去学习。
9、参考文献
1. 马秋菊 主编 《数据结构（C语言描述）》 北京：中国水利水电出版 2006
2. 严蔚敏 吴伟民 编著 《数据结构 （C语言版）》 北京：清华大学出版社 2002
3. 李春葆 苏光奎 编著 《数据结构与算法教程》 北京：清华大学出版社 2005
4. 戴 敏 主编 《数据结构》 北京：机械工业出版社 20008
10、指导教师评语

附件一： 程序清单
#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 vexs[MAXVEX][MAXVEX]; //单位名称（顶点信息）；
int adj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）；
int dis[MAXVEX][MAXVEX]; //单位间距离（边的长度）；
int f[MAXVEX]; //各单位去超市的频率；
int n; //顶点数和边数；
int e;
}Mgraph;
void CreatMgraph(Mgraph *G)
{
int i,j,k;
printf("请输入单位个数:\n");
scanf("%d",&(G->n));
printf("请输入单位间的路径数:\n");
scanf("%d",&(G->e));
printf("请输入单位名称:\n");
for(i=0;in;i++)
{
printf("请输入第%d个单位名称:\n",i);
scanf("%s",&G->vexs[i]);
}
for(i=0;in;i++) //结构体的初始化；
for(j=0;jn;j++)
{
G->adj[i][j]=0;
G->dis[i][j]=0;
G->f[i]=0;
}
for(k=0;ke;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;kn;k++)
{
printf("请输入第%d个单位去超市的相对频率:\n",k);
scanf("%d",&(G->f[k]));
}
for(i=0;in;i++) //以距离和频率之积作为权值；
for(j=0;jn;j++)
{
G->dis[i][j]*=G->f[i]; //最终权值非完全无向；
if(G->adj[i][j]==0&&i!=j)
G->dis[i][j]=INF;
}
}
void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法
{

int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
int count[MAXVEX];
for(i=0;in;i++) //初始化A[][]和path[][]数组
for(j=0;jn;j++) //置初值；
{
A[i][j]=G->dis[i][j];
path[i][j]=-1;
count[i]=0;
}
for(k=0;kn;k++) //k代表运算步骤
{
for(i=0;in;i++)
for(j=0;jn;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<n;i++)
for(j=0;jn;j++)
{
if(i!=j)
{
cout<<" "<"< }
cout<n;i++)
for(j=0;jn;j++)
{
if(A[i][j]==INF)
count[i]=0;
else
count[i]=1;
}
for(i=0;in;i++)
if(count[i])
{
for(j=0;jn;j++)
A[i][0]+=A[i][j];
}
for(i=0;in;i++)
{
k=0;
if(count[i])
if(A[k][0]>A[i][0])
k=i;
}
cout<<"超市的最佳地址为:"<vexs[k]<