第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 ✓ 时间复杂度?