资源描述
WinQSB软件应用软件应用2实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解网络中的服务设施布局 长虹街道近年新建了11个居民小区，各小区的大致位置及相互间的道路距离（单位：100m）如右图所示，各居民小区居民数为：1(3000),2(3500),3(3700),4(5000),5(3000),6(2500),7(2800),8(4500),9(3300),10(4000),11(3500)。试帮助决策：171024811356948556645665547684673实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v（1）在11个小区内准备共建一套医务所、邮局、储蓄所、综合超市等服务设施，应建于哪一居民小区，使对居民总体来说感到方便；v 求解问题：v 明确目标（对居民总体来说感到方便）。即使所有人到服务设施设置小区走的距离和为最小。v 求出所有人到服务设施设置小区走的距离和的所有可能值v 首先求出任意两点之间的最短距离4实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v WINQSB求解最短路问题v 新建问题界面问题类型网络图节点个数弧的权数是否对称（是否是无向图）5实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 网路图输入界面根据原图将节点放置到适当的位置节点之间连线并输入权数6实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 求解结果界面1-9的最短距离1到其他节点的最短距离7实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解任意两节点之间的最短距离表格8实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 将上表中的每行数字分别乘以各小区人数得各小区之间的人数距离和9实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 按列相加得下表求出以各小区为服务点的人数和距离数乘积之和v 其中最小的为285700，所以在小区8设置服务点总体感到满意10实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v(2)电信部门拟将宽带网铺设到各小区，应如何铺设最为经济v铺设的要求：连通各小区v如何铺设最为经济：经过的距离最小v部分图：图G1=V1,E1和图G2=V2,E2,如果V1=V2,E1包含于E2，则称G1是G2的一个部分图v树图：无圈的连通图v部分树：如果G1是G2的部分图，又是树图，则称G1是G2的部分树v所以问题实际就是从小区网络图中找出一个使各小区连通的部分图，并且使该部分图的边权数之和最小-即最小部分树问题(minimum spanning tree)11实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v WINQSB求解最小部分树问题v 新建问题问题类型网络图节点个数弧的权数是否对称（是否是无向图）12实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 网路图输入界面根据原图将节点放置到适当的位置节点之间连线并输入权数13实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v 求解结果界面（表格）最小部分树的权数之和最小部分树的各条边14实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v求解结果（图形）17102481135694556455544最小距离总和：4700m15实验三：图和网络相关问题分析求解实验三：图和网络相关问题分析求解v课堂练习：已知有6个村子，相互间道路的距离如下图所示。拟合建一所小学，已知A处有小学生50人，B处40人，C处60人，D处70人，E处70人，F处90人。问小学应建在哪一个村子，使学生上学最方面。课后作业：完成网络课程中网络分析问题作业，十一回来后提交ABCDEF2746381163
展开阅读全文