文档介绍：方法与技术(结构)
问题：
给定一群人(例如：在一个大操场上)，给定一个数值(例如: 175)，输出高度恰好等于该数值的人。
方法：
搜索
但是我们仍然需要明确，用什么样的方式来实现“搜索”
第一页，共24页。
问题1：
你能解释方法与技术(结构)
问题：
给定一群人(例如：在一个大操场上)，给定一个数值(例如: 175)，输出高度恰好等于该数值的人。
方法：
搜索
但是我们仍然需要明确，用什么样的方式来实现“搜索”
第一页，共24页。
问题1：
你能解释下面的话吗？
第二页，共24页。
搜索“解空间” – 一个例子
一位父亲请一位数学家猜他3个孩子的年龄，他提示说：
3人年龄的乘积是36。
这时他们恰好经过一幢房子，父亲又提示说：他们年龄之和等于这房子窗户的个数。
父亲见数学家仍然犹豫，又补充说：
老大很小的时候家中没有其他孩子跟他一起玩。
你能说出3个孩子的年龄吗？
第三页，共24页。
初始的解空间
假设年龄精确到整数
集合S
所有可能的解的集合
S = { (i, j, k) | i, j, k 是非负整数｝
第四页，共24页。
利用条件缩小可能的解空间
集合S1
所有可能的解的集合
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)
条件1：3人年龄乘积为36
第五页，共24页。
解空间还有缩小的可能
尽管已经知道了年龄之和, 那个数学家仍然说不出答案…
S1: 
(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
可能的解的集合
第六页，共24页。
再进一步就是解！
当前可能的解的集合：
{ (1,6,6), (2,2,9) }
但是：老大没有同年龄的兄弟姐妹．
因此三个孩子的年龄分别是：
９岁、２岁和２岁
第七页，共24页。
问题求解的基本“方法”
确定合理的解空间，并表示为某种“结构”。
利用已知的限制条件（知识）尽可能快的压缩可能的解空间。
当解空间已经足够小，我们就可以“直接”解题。
如果很难确定解空间的范围，或者很难有效地缩小解空间，这个题目就“很难”。
第八页，共24页。
搜索结构
深度优先 - DFS
广度优先 - BFS
第九页，共24页。
“聪明”的搜索结构
二分搜索树 - BST
24
20
6
50
5
12
3
18
21
30
堆 – Heap
优先队列的一种实现
第十页，共24页。
问题2：
你能解释一下解Maximal Polygon Distance问题的过程中是如何建立并缩小解空间的吗？
第十一页，共24页。
第十二页，共24页。
问题3：
你阅读的材料中还介绍了哪些“算法方法”？你能从“搜索”的角度对它们加以解释吗？
Divide-and-Conquer; Greedy; Dynamic Programming; Using “clever” data structure
第十三页，共24页。
Mergesort: Divide-and-Conquer
第十四页，共24页。
Greedy: Minimal Spanning Tree
第十五页，共24页。
Greedy: Simple, but may Fail!
问题4：
你能从“搜索”的角度说明为什么Greedy可能Fail吗？
第十六页，共24页。
问题5：
用 Dynamic Programming解最短通路问题为什么就不会出错了？
第十七页，共24页。
问题6：
既然Dynamic Programming 本质上是 exhaustive, 为什么还能保证效率可以接受？
第十八页，共24页。
用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 prob