计算机问题求解 – 论题1-11 - 算法方法 2016年11月28日
Part I “解题”与“搜索”
问题1： 你能解释下面的话吗？
方法与技术(结构) 问题： 方法： 但是我们仍然需要明确，用什么样的方式来实现“搜索” 给定一群人(例如：在一个大操场上)，给定一个数值(例如: 175)，输出高度恰好等于该数值的人。 方法： 搜索 但是我们仍然需要明确，用什么样的方式来实现“搜索”
搜索“解空间” – 一个例子 一位父亲请一位数学家猜他3个孩子的年龄，他提 示说： 父亲见数学家仍然犹豫，又补充说： 3人年龄的乘积是36。 这时他们恰好经过一幢房子，父亲又提示说：他们年 龄之和等于这房子窗户的个数。 父亲见数学家仍然犹豫，又补充说： 老大很小的时候家中没有其他孩子跟他一起玩。 你能说出3个孩子的年龄吗？
初始的解空间 假设年龄精确到整数 所有可能的解的集合 集合S S = { (i, j, k) | i, j, k 是非负整数｝
利用条件缩小可能的解空间 条件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
解空间还有缩小的可能 尽管已经知道了年龄之和, 那个数学家仍然说不出答案… S1: (1, 1, 36) 38 (1, 1, 36) 38 (1, 2, 18) 21 (1, 3, 12) 16 (1, 4, 9) 14 (1, 6, 6) 13 (2, 2, 9) 13 (2, 3, 6) 11 (3, 3, 4) 10 可能的解的集合
再进一步就是解！ 当前可能的解的集合： { (1,6,6), (2,2,9) } 但是：老大没有同年龄的兄弟姐妹． 因此三个孩子的年龄分别是： ９岁、２岁和２岁
问题求解的基本“方法” 确定合理的解空间，并表示为某种“结构”。 利用已知的限制条件（知识）尽可能快的压缩可 能的解空间。 当解空间已经足够小，我们就可以“直接”解 题。 如果很难确定解空间的范围，或者很难有效地缩 小解空间，这个题目就“很难”。
只可能是1005！ 这当然是0！ 问题3： 现在除数的可能值能缩到足够小了吗？ 问题2： 你能定义这个问题的解空 间吗？如何设法缩小它？
搜索与“结构” 问题3： 书上以计算累计工资值为例， 描述了“明显的”和“不太 明显的”搜索结构。你能解 释那个例子吗？
更复杂的搜索结构 广度优先 - BFS 深度优先 - DFS
“聪明”的搜索结构 堆 – Heap 优先队列的一种实现 50 24 30 20 21 18 3 12 5 6 二分搜索树 - BST
Part II 从原则到“策略”
问题3： 你能解释一下解Maximal Polygon Distance问题 的过程中是如何建立并缩 小解空间的吗？
问题4： 你阅读的材料中还介绍了 哪些“算法方法”？你能 从“搜索”的角度对它们 加以解释吗？ Divide-and-Conquer; Greedy; Dynamic Programming; Using “clever” data structure
Mergesort: Divide-and-Conquer
Greedy: Minimal Spanning Tree
Greedy: Simple, but may Fail! 问题5： 你能从“搜索”的角度说明为什么Greedy可能Fail吗？
问题6： 用 Dynamic Programming解最短通路问题为什么就不会出错了？
问题7： 既然Dynamic Programming 本质上是 exhaustive, 为 什么还能保证效率可以接受？
问题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<si1 (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：为什么这是难题？
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! 但可以证明：也不是太差！
问题9： 你是否能用书上“孩子滑雪” 的例子，说明：什么是online 问题？为什么它被认为更困难？ Online: 会更困难 – FFD不适用 问题9： 你是否能用书上“孩子滑雪” 的例子，说明：什么是online 问题？为什么它被认为更困难？
问题10: 掌握不了孩子兴趣多大 1, 如何决策? 2, 最坏情况下代价多大? 3, 还能更好吗? 滑雪装备 – 买还是租? Off-line: 决策很简单，评价online算法的基准 问题10: 掌握不了孩子兴趣多大 1, 如何决策? 2, 最坏情况下代价多大? 3, 还能更好吗?
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：最多比最优解差多少？
课外作业 DH: 4.1; 4.2; DH: 4.8-4.9; 4.11; 4.12; DH: 4.13-14;