《中国邮递员问题欧拉巡回课件.ppt》由会员分享，可在线阅读，更多相关《中国邮递员问题欧拉巡回课件.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基本概念与基本结论主要内容求欧拉图欧拉巡回的算法原始模型求解中国邮递员问题的算法案例：铲雪车的行驶路线问题原始模型问题：一位邮递员从邮局选好邮件去投递，他必须经过他所管辖的每条街至少一次，然后回到邮局，如何选择一条总行程最短的路线？v2v1v3v4v5v6v8v9v11v10v13v12v15106325457843121169v7v14653基本概念与基本结论基本概念与基本结论无向图的情形基本概念与基本结论基本概念与基本结论无向图的情形基本概念与基本结论基本概念与基本结论有向图的情形基本概念与基本结论基本概念与基本结论有向图的情形求欧拉图欧拉巡回的算法求欧拉图欧拉巡回的算法求欧拉图欧拉巡回的
2、算法求欧拉图欧拉巡回的算法求欧拉图欧拉巡回的算法求欧拉图欧拉巡回的算法求解中国邮递员问题的算法求解中国邮递员问题的算法求解中国邮递员问题的算法求解中国邮递员问题的算法问题问题 某地区的双车道公路如图1的图G（单位是千米），路上积满了雪 。一辆扫雪车从v1点出发，扫除公路上的所有积雪，最后回到v1 。 要求1） 请你为扫雪车选择一条路径，使它经过的总路程最短。 要求2） 现在先进的喷气扫雪车只需沿公路一侧行驶，就能清除两个车道的积雪。如果改用喷气扫雪车来扫雪，再请你为它选择一条路径，使它经过的总路程最短。双车道公路扫雪模型案例案例1 1：双车道公路扫雪模型：双车道公路扫雪模型v2v1v3v4v5
3、v6v8v9v11v10v13v12v15106325457843121169v7v14653要求1）的解法1 由于是双车道，因此可将每条边看成来回两条异向弧，此时，图是有向欧拉图，可用hierholzer算法在有向图上求出有向欧拉巡回。 双车道公路扫雪模型v2v1v3v4v5v6v8v9v11v10v13v12v15106325457843121169v7v14653的解法2双车道公路扫雪模型的解法2（续）双车道公路扫雪模型双车道公路扫雪模型xakhedbcflgij的解法2（续）双车道公路扫雪模型双车道公路扫雪模型v2v1v3v4v5v6v8v9v11v10v13v12v15106325457843121169v7v14653精品课件精品课件！精品课件精品课件！