计算机问题求解 – 论题1-11 - 算法方法 2016年11月28日.

Presentation on theme: "计算机问题求解 – 论题1-11 - 算法方法 2016年11月28日."— Presentation transcript:

1 计算机问题求解 – 论题 算法方法 2016年11月28日

2 Part I “解题”与“搜索”

3 问题1： 你能解释下面的话吗？

4 方法与技术(结构) 问题： 方法： 但是我们仍然需要明确，用什么样的方式来实现“搜索”
给定一群人(例如：在一个大操场上)，给定一个数值(例如: 175)，输出高度恰好等于该数值的人。 方法： 搜索 但是我们仍然需要明确，用什么样的方式来实现“搜索”

5 搜索“解空间” – 一个例子 一位父亲请一位数学家猜他3个孩子的年龄，他提 示说： 父亲见数学家仍然犹豫，又补充说：
3人年龄的乘积是36。 这时他们恰好经过一幢房子，父亲又提示说：他们年 龄之和等于这房子窗户的个数。 父亲见数学家仍然犹豫，又补充说： 老大很小的时候家中没有其他孩子跟他一起玩。 你能说出3个孩子的年龄吗？

6 初始的解空间 假设年龄精确到整数 所有可能的解的集合 集合S S = { (i, j, k) | i, j, k 是非负整数｝

7 利用条件缩小可能的解空间 条件1：3人年龄乘积为36 S1: (1, 1, 36) (1, 2, 18) (1, 3, 12)
(1, 4, 9) (1, 6, 6) (2, 2, 9) (2, 3, 6) (3, 3, 4) 所有可能的解的集合 集合S1 条件1：3人年龄乘积为36

8 解空间还有缩小的可能 尽管已经知道了年龄之和, 那个数学家仍然说不出答案… S1:  (1, 1, 36) 38
(1, 1, 36) (1, 2, 18) (1, 3, 12) (1, 4, 9) (1, 6, 6) (2, 2, 9) (2, 3, 6) (3, 3, 4) 可能的解的集合

9 再进一步就是解！ 当前可能的解的集合： { (1,6,6), (2,2,9) } 但是：老大没有同年龄的兄弟姐妹．
因此三个孩子的年龄分别是： ９岁、２岁和２岁

10 问题求解的基本“方法” 确定合理的解空间，并表示为某种“结构”。 利用已知的限制条件（知识）尽可能快的压缩可 能的解空间。
当解空间已经足够小，我们就可以“直接”解 题。 如果很难确定解空间的范围，或者很难有效地缩 小解空间，这个题目就“很难”。

11 只可能是1005！ 这当然是0！ 问题3： 现在除数的可能值能缩到足够小了吗？ 问题2： 你能定义这个问题的解空 间吗？如何设法缩小它？

12 搜索与“结构” 问题3： 书上以计算累计工资值为例， 描述了“明显的”和“不太 明显的”搜索结构。你能解 释那个例子吗？

13 更复杂的搜索结构 广度优先 - BFS 深度优先 - DFS

14 “聪明”的搜索结构 堆 – Heap 优先队列的一种实现 50 24 30 20 21 18 3 12 5 6 二分搜索树 - BST

15 Part II 从原则到“策略”

16 问题3： 你能解释一下解Maximal Polygon Distance问题 的过程中是如何建立并缩 小解空间的吗？

17

18 问题4： 你阅读的材料中还介绍了 哪些“算法方法”？你能 从“搜索”的角度对它们 加以解释吗？
Divide-and-Conquer; Greedy; Dynamic Programming; Using “clever” data structure

19 Mergesort: Divide-and-Conquer

20 Greedy: Minimal Spanning Tree

21 Greedy: Simple, but may Fail!
问题5： 你能从“搜索”的角度说明为什么Greedy可能Fail吗？

22 问题6： 用 Dynamic Programming解最短通路问题为什么就不会出错了？

23 问题7： 既然Dynamic Programming 本质上是 exhaustive, 为 什么还能保证效率可以接受？

24 问题8：为什么这是难题？ 用Greedy解“难”题 Bin Packing Problem
Suppose we have an unlimited number of bins each of capacity one, and n objects with sizes s1, s2, …, sn where 0<si1 (si are rational numbers) Optimization problem: Determine the smallest number of bins into which the objects can be packets (and find an optimal packing) . Bin packing is a NPC problem 问题8：为什么这是难题？

25 First Fit Decreasing - FFD
The strategy: packing the largest as possible Example: S=(0.8, 0.5, 0.4, 0.4, 0.3, 0.2, 0.2, 0.2) B1 B2 B3 B4 0.2(s6) 0.2(s7) 0.4(s3) 0.3(s5) 0.8(s1) 0.5(s2) 0.4(s4) 0.2(s8) This is NOT an optimal solution! 但可以证明：也不是太差！

26 问题9： 你是否能用书上“孩子滑雪” 的例子，说明：什么是online 问题？为什么它被认为更困难？
Online: 会更困难 – FFD不适用 问题9： 你是否能用书上“孩子滑雪” 的例子，说明：什么是online 问题？为什么它被认为更困难？

27 问题10: 掌握不了孩子兴趣多大 1, 如何决策? 2, 最坏情况下代价多大? 3, 还能更好吗? 滑雪装备 – 买还是租?
Off-line: 决策很简单，评价online算法的基准 问题10: 掌握不了孩子兴趣多大 1, 如何决策? 2, 最坏情况下代价多大? 3, 还能更好吗?

28 Next Fit Algorithm - NF 问题10：最多比最优解差多少？
The strategy: Put a new item in the last bin if possible, or use a new bin. Never look back! An example: S={0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8} 0.1 0.5 0.8 0.7 0.4 0.3 0.2 问题10：最多比最优解差多少？

29

30 课外作业 DH: 4.1; 4.2; DH: ; 4.11; 4.12; DH: ;