菜单
　　

    3.3 中国邮路问题案例分析
     城市的交通系统由若干个路口和街道组成，每条街道都连接着两个路口。所有街道都只能单向通行，且每条街道都有一个长度值。一名邮递员传送报纸和信件，要从邮局出发经过他所管辖的每一条街道最后返回邮局（每条街道可以经过不止一次）。请问他应该如何安排自己的路线，使得他走过的总长度最短呢？
    首先计算每个顶点 的入度与出度之差 （如果G中所有的 ，那么 中已经存在欧拉回路）。入度与出度只差 有三种情况，对于 的顶点 ，需要增加 条从 出发的路径；对于 的顶点 ，需要增加 条到 结束的路径；对于 的顶点 ,要求 不作为增加的任何一条路径的端点（或者是以 为终止点的路径数等于以 为出发点的路径数，但在那种情况下，可以把后者连接到前者之后而合并成一条路径）。这个模型与网络流模型有着惊人的相似！
    网络流模型就是 的顶点 对应于网络流模型中的源点，它发出 个单位的流； 的顶点 对应于网络流模型中的汇点，它接收 个单位的流；而 的顶点 则对应于网络流模型中的中间结点，它接收的流量等于发出的流量。在上例邮路问题中还要求增加的路径总长度最小，我们可以把网络中每条边的费用值 设为图 中对应边的长度。这样，在网络中求最小费用最大流，即可使总费用  最小 。
  1. 上一篇：基于C++的教师档案管理系统的设计与实现
  2. 下一篇：ASP.NET通用权限管理系统设计+文献综述

  1. 基于MATLAB的图像增强算法设计

  2. jsp+sqlserver高校二手商品交...

  3. 基于Kinect的手势跟踪与识别算法设计

  4. JAVA基于安卓平台的医疗护工管理系统设计

  5. java+mysql设备监控记录的大...

  6. 基于核独立元分析的非线...

  7. 基于Hadoop的制造过程大数据存储平台构建

  8. 十二层带中心支撑钢结构...

  9. 乳业同业并购式全产业链...

  10. 河岸冲刷和泥沙淤积的监测国内外研究现状

  11. 杂拟谷盗体内共生菌沃尔...

  12. 电站锅炉暖风器设计任务书

  13. 当代大学生慈善意识研究+文献综述

  14. java+mysql车辆管理系统的设计+源代码

  15. 酸性水汽提装置总汽提塔设计+CAD图纸

  16. 中考体育项目与体育教学合理结合的研究

  17. 大众媒体对公共政策制定的影响

　　

About

751论文网手机版...

主页：http://www.751com.cn

关闭返回