某理工大学机电工程学院IE案例分析(PPT 84页)

案例一：旅游线路规划
有如下问题需要解决：
现在要在以上各地方中的某一处修建一所会议中心，已知各个景点的员工分别是40,25,45,30,20,35,50，那么会议中心应建在何处，能使各个景点的员工走的总路程最短？
为了保护园区野生生态环境，现在规定每条线路上观光旅游车的数量是一定的，见下图，其中每条弧上的数字为通行车辆容量，那么如何在不违背每条线路旅游车辆数目限制下寻求最多的车辆通行？
电信公司需要安装电话线路，联通各个景点和进出口，则最小线路安装是什么？
显然，第一个问题属于最小树生成问题，采用避圈法。
任选点S开始，离点S最近未连通是点Ａ，连通ＳＡ．
离点Ｓ或者点A最近未连通是点B（和点Ａ相连通），连通ＡB
离点Ｓ，Ａ或点B最近未连通是点C（和点Ｂ连通），连通ＢＣ
离点S，Ａ，B或者点C最近未连通是Ｅ（和点B连通），连通BE

..............................