算法设计与分析 课件 第一章 绪论1.3 例1.3_第1页
算法设计与分析 课件 第一章 绪论1.3 例1.3_第2页
算法设计与分析 课件 第一章 绪论1.3 例1.3_第3页
算法设计与分析 课件 第一章 绪论1.3 例1.3_第4页
算法设计与分析 课件 第一章 绪论1.3 例1.3_第5页
已阅读5页，还剩3页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

计算机算法设计与分析第一章绪论一个快递小哥从快递中心点出发，到周边四个小区送快递，要求经过每个小区且只能每个小区仅经过一次，最后回到快递中心点。问快递小哥应如何安排派送路线较好？例1.3快递员路线安排问题起

终ABCDEA03456B30265C42043D56405E65350（1）问题分析与问题抽象，这是一个典型的TSP问题将小区抽象为下图的顶点，两个小区之间有路直达，则对应的两个顶点之间有边关联，边的权值为两个小区之间的距离。则将快递员路线安排问题抽象为从顶点A(设A为快递中心)出发经过图中其余顶点后回到顶点A的最短简单回路问题。例1.3快递员路线安排问题3365456542EBDCA（2）数学建模：例1.3快递员路线安排问题3365456542EBDCA（3）方法一蛮力法：列出每一条可供选择的路线，计算出每条路线的距离长度，最后从中选择出一条最短路线。最短路程为：A-->B-->C-->E-->D-->A或者A-->D-->E-->C-->B-->A，最短路径长度为:18。例1.3快递员路线安排问题3365456542EBDCA（3）蛮力法算法效率分析：使用蛮力法列举除出发小区外所有小区的排列，然后选取路径最短的路线。n-1个小区的排列数为(n-1)!，当n=20时，遍历路线总数约为1.216×1017，计算机以每秒1000万条路线的检索速度计算，则约需要386年才能完成。故蛮力法的时间复杂度太高，当顶点数过多时并不适用。例1.3快递员路线安排问题（3）方法二贪心法：每次在选择下一个小区时，只考虑当前情况。在没有经过的小区中，选择距离当前小区最近的一个，直到经过所有小区，最后回到快递中心。A例1.3快递员路线安排问题3365456542EBDCA贪心法的优点是效率很高，只要n-1步判断就能得到结果。但缺点是不一定能找到问题的最优解。算法：贪心法—伪代码描述输入：小区数量n，邻接矩阵e[i,j]，顶点v[i]，出发小区编号go_city，index当前小区编号。输出：最短路线上的顶点信息，最短路径长度min_l。Greedy(index):beginfori

1tondo ifi不是出发顶点go_citythen forj

1tondo if没有经过小区jthen

筛选与当前出发点最短的顶点，并标记为cur_j endifendfor min_l

min_l+e[index,cur_j] index

cur_j//从出发点cur_j，继续下一步求解

并置cur_j顶点为经过标记

endifend for

min_

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论