中国邮递员问题.ppt

中国邮递员问题 (Chinese Postman Problem) ;中国邮递员问题;精品资料; 你怎么称呼老师？ 如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？ 你所经历的课堂，是讲座式还是讨论式？ 教师的教鞭 “不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘 ……” “太阳当空照，花儿对我笑，小鸟说早早早……”;中国邮递员问题;欧拉于1736年研究并解决了此问题， 他用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。之后他发表一篇论文，证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的结论。;中国邮递员问题;b;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;解决这样的问题，可以采用奇偶点图上作业法：如果在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。;中国邮递员问题;中国邮递员问题;如果在某条路线中，边[vi,vj]上重复走几次，我们就在图中vi,vj之间增加几条边，令每条边的权和原来的权相等，并把所增加的边，称为重复边，于是这条路线就是相应的新图中的尤拉图。 原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。 我们把使新图不含奇点而增加的重复边简称为可行（重复边）方案，使总权最小的可行方案为最优方案。;现在的问题是第一个可行方案如何确定？ 在确定一个可行方案后，怎么判断这个方案是否为最优方案？ 若不是最优方案，如何调整这个方案？;车辆从某配送中心（v1）出发，给街道边上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送货，如图1所示。;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递???问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题;中国邮递员问题