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

基于Apriori算法的电影推荐

PHP+IOS的会议管理系统的设计+ER图

数据挖掘在电子商务中的应用

数据挖掘的主题标绘数据获取技术与实现

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

基于网络的通用试题库系...

AT89C52单片机的超声波测距...

10万元能开儿童乐园吗,我...

医院财务风险因素分析及管理措施【2367字】

C#学校科研管理系统的设计

神经外科重症监护病房患...

国内外图像分割技术研究现状

承德市事业单位档案管理...

中国学术生态细节考察《...

公寓空调设计任务书

志愿者活动的调查问卷表