南方医科大学：《软件工程》课程教学资源（PPT课件）第5章 结构化实现 5.2 算法决策

软件开发过程 发布维护 系统实现 系统设计 需求分析 软件计划

软件开发过程 需求分析 系统设计 系统实现 发布维护 软件计划

第5章 结构化实现 5.1编码与程序语言 5.2算法决策【重点，难点】 5.3测试与调试

5.1 编码与程序语言 5. 2 算法决策 【重点，难点】 5.3 测试与调试 第5章 结构化实现

第5章结构化实现 5.1编码与程序语言 5.2算法决策 【重点，难点】 5.3测试【重点，难点】 5.4调试 5.5部署与交付

5.1 编码与程序语言 5.2 算法决策 【重点，难点】 5.3 测试【重点，难点】 5.4 调试 5.5 部署与交付 第5章 结构化实现

问题介绍 健康知识普及行动 健推委开展预防疾病、紧急救援、及时就医、合理 2 70 用药、应急避险等维护健康的知识宣讲活动。 10 10 计划是：从所在城市出发，到每个城市一次，最后 20 20 60 70 (9 70 返回初始城市。各个城市之间的费用是已知的。 50 30 4 80 20 为了节省费用，应选择什么样的路线，使总费用最 70 20 少？ 70 10 60

问题介绍 • 健康知识普及行动 健推委开展预防疾病、紧急救援、及时就医、合理 用药、应急避险等维护健康的知识宣讲活动。 计划是：从所在城市出发，到每个城市一次，最后 返回初始城市。各个城市之间的费用是已知的。 为了节省费用，应选择什么样的路线，使总费用最 少？

问题介绍 旅行商问题(Traveling Salesman Problem,TSP) 名旅行商要到若干个城市进行推销，各个城 50 2 10 市之间的费用是已知的。 10 10 40 20 他的计划是：从所在城市出发，到每个城市一 20 60 9 10 次，最后返回初始城市。 50 30 4 80 70 为了节省费用，应选择什么样的路线，使总费 20 10 70 用最少？ 60 应用领域：医疗物资运输、疾病调查、药物分子结构、医疗互联网架构. 启示

问题介绍 • 旅行商问题（Traveling Salesman Problem, TSP） 一名旅行商要到若干个城市进行推销，各个城 市之间的费用是已知的。 他的计划是：从所在城市出发，到每个城市一 次，最后返回初始城市。 为了节省费用，应选择什么样的路线，使总费 用最少？ 应用领域：医疗物资运输、疾病调查、药物分子结构、医疗互联网架构. 启 示

问题介绍 旅行商问题(Traveling Salesman Problem,TSP) 名旅行商要到若干个城市进行推销，各个城 50 60 2 70 市之间的费用是已知的。 10 10 10 00 20 他的计划是：从所在城市出发，到每个城市一 20 70 9 70 次，最后返回初始城市。 50 4 80 40 70 为了节省费用，应选择什么样的路线，使总费 20 70 5 用最少？ 60 应用领域：物流快递、交通运输、旅游路线、安全巡查、电路布线 启示

问题介绍 • 旅行商问题（Traveling Salesman Problem, TSP） 一名旅行商要到若干个城市进行推销，各个城 市之间的费用是已知的。 他的计划是：从所在城市出发，到每个城市一 次，最后返回初始城市。 为了节省费用，应选择什么样的路线，使总费 用最少？ 应用领域：物流快递、交通运输、旅游路线、安全巡查、电路布线 . 启 示

启示 ·从具体到抽象，再从抽象到具体 一给一个具体场景描述，能不能抽象成一类问题或一类模式？ 一给一个具体运算要求，能不能抽象出计算规律和表达形式？ 方法 工程 一有了抽象表达，能不能回归应用于具体场景？ -有了抽象模式，能不能解决类似的具体问题？

启 示 • 从具体到抽象，再从抽象到具体 – 给一个具体场景描述，能不能抽象成一类问题或一类模式？ – 给一个具体运算要求，能不能抽象出计算规律和表达形式？ – 有了抽象表达，能不能回归应用于具体场景？ – 有了抽象模式，能不能解决类似的具体问题？ 方 法 工 程

问题转化 ·旅行商问题(Traveling Salesman Problem,TSP) 50 7 10 A B 简化 3 60 6 启示 8 10 9

问题转化 • 旅行商问题（Traveling Salesman Problem, TSP） 简 化 启 示

求解分析 7 A B 最直接的做法：暴力搜索 3 第1步：列出所有可能的路线 6 第2步：计算每条路线的代价 8 第3步：选出代价最小的路线 9 A -

求解分析 • 最直接的做法：暴力搜索 第1步：列出所有可能的路线 第2步：计算每条路线的代价 第3步：选出代价最小的路线 A B C D C D D C B D D B B C C B A A A A A A

求解分析 A B 最直接的做法：暴力搜索 时间复杂度？ 第1步：列出所有可能的路线 4 6 第2步：计算每条路线的代价 8 第3步：选出代价最小的路线 9 A 7+4+9+6=26 7+8+9+3=27 - A 3+4+8+6=21√ A 3+9+8+7=27 A 6+8+4+3=21 A 6+9+4+7=26

求解分析 • 最直接的做法：暴力搜索 第1步：列出所有可能的路线 第2步：计算每条路线的代价 第3步：选出代价最小的路线 A B C D C D D C B D D B B C C B A A A A A A 7 + 4 + 9 + 6 = 26 7 + 8 + 9 + 3 = 27 3 + 4 + 8 + 6 = 21 3 + 9 + 8 + 7 = 27 6 + 8 + 4 + 3 = 21 6 + 9 + 4 + 7 = 26 ✓ 时间复杂度？