请在下方输入要搜索的题目：

中国邮路问题例2 中国邮递员问题:中国邮递员从邮局出发,经过他所投递范围的每一条街道至少一次,完成投递任务后返回邮局,问应如何安排邮递员的行走路线才能使总行程路线最短?

发布时间：2024-12-30 18:58:05

推荐参考答案 ( 由快搜搜题库官方老师解答 )

联系客服

答案：解 1)、如G是欧拉回路,Euler 设计了一条求欧拉回路的算法:2)、对于非欧拉图,邮递员返回邮局必须将图转换成欧拉图,为此需添加重复边以清除奇次顶点,与奇点关联的边应添加奇数条,与偶点关联的边应添加偶数条(含0条),现在的问题是求解使重复边总权重值最小的方案。具体方法;1)、如果在配送范围内,街道拐弯处没有奇点,那么邮递员可以从配送中心出发,走过每条街道一次且仅一次最后回到配送中心,他走的路径为最短路径。2)、对于有奇点的街道图,必须在一些街道重复走一次或多次,这样相当于我们在图中如

之间增加几条重复边,令每条重复边的权与原来的边的权相等,于是这条路线就是新图中的欧拉图,它使新图不含奇点,并且重复边的总权最小。这一方案分两步(见下例):例1 一车辆从某配送中心出发,给街道上的7个超市-送货,求使总行程最短的送货方案。第一步:使新图不含奇点而增加重复边由图论,在任何一个连通图中,奇点个数必为偶数,所以如图中有奇点,可把它们配对。又因为图是连通的,故每一对奇点之间必有一条链,我们把这条链的所有边作为重复边加到图中去,新图中必无奇点。这就得出第一可行方案,即把使新图不含奇点而增加的重复边叫可行(重复边)方案。图1 未加重复边前的图 2 4