计算机问题求解算法方法.ppt
计算机问题求解 论题1-11 -算法方法方法与技术(结构)n问题：q给定一群人(例如：在一个大操场上)，给定一个数值(例如:175)，输出高度恰好等于该数值的人。n方法：q搜索n但是我们仍然需要明确，用什么样的方式来实现“搜索”问题问题1：你能解释下面的话吗？你能解释下面的话吗？搜索“解空间”一个例子n一位父亲请一位数学家猜他3个孩子的年龄，他提示说：q3人年龄的乘积是36。q这时他们恰好经过一幢房子，父亲又提示说：他们年龄之和等于这房子窗户的个数。n父亲见数学家仍然犹豫，又补充说：q老大很小的时候家中没有其他孩子跟他一起玩。n你能说出3个孩子的年龄吗？初始的解空间假设年龄精确到整数集合S所有可能的解的集合S=(i,j,k)|i,j,k 是非负整数利用条件缩小可能的解空间 集合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解空间还有缩小的可能尽管已经知道了年龄之和,那个数学家仍然说不出答案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 可能的解的集合再进一步就是解！n当前可能的解的集合：(1,6,6),(2,2,9)n但是：老大没有同年龄的兄弟姐妹n因此三个孩子的年龄分别是：岁、岁和岁问题求解的基本“方法”n确定合理的解空间，并表示为某种“结构”。n利用已知的限制条件（知识）尽可能快的压缩可能的解空间。q当解空间已经足够小，我们就可以“直接”解题。n如果很难确定解空间的范围，或者很难有效地缩小解空间，这个题目就“很难”。搜索结构深度优先-DFS广度优先-BFS“聪明”的搜索结构二分搜索树-BST24206505123182130堆 Heap优先队列的一种实现问题问题3：你阅读的材料中还介绍了哪你阅读的材料中还介绍了哪些些“算法方法算法方法”？你能从？你能从“搜索搜索”的角度对它们加以的角度对它们加以解释吗？解释吗？Divide-and-Conquer;Greedy;Dynamic Programming;Divide-and-Conquer;Greedy;Dynamic Programming;Using“clever”data structureUsing“clever”data structureMergesort:Divide-and-ConquerGreedy:Minimal Spanning TreeGreedy:Simple,but may Fail!问题5：用 Dynamic Programming解最短通路问题为什么就不会出错了？问题6：既然Dynamic Programming 本质上是 exhaustive,为什么还能保证效率可以接受？用Greedy解“难”题nBin Packing ProblemqSuppose we have an unlimited number of bins each of capacity one,and n objects with sizes s1,s2,sn where 0si1(si are rational numbers)qOptimization problem:Determine the smallest number of bins into which the objects can be packets(and find an optimal packing).qBin packing is a NPC problemFirst Fit Decreasing-FFDnThe strategy:packing the largest as possiblenExample:S=(0.8,0.5,0.4,0.4,0.3,0.2,0.2,0.2)B1B2B3B40.8(s1)0.2(s6)0.5(s2)0.4(s3)0.4(s4)0.3(s5)0.2(s7)0.2(s8)This is NOT an optimal solution!但可以证明：也不是太差！Online:会更困难问题问题8：你是否能用书上你是否能用书上“孩子滑雪孩子滑雪”的例子，说明：什么是的例子，说明：什么是online问题？为什么它被认为更困难？问题？为什么它被认为更困难？Next Fit Algorithm-NFnThe strategy:Put a new item in the last bin if possible,or use a new bin.Never look back!nAn example:S=0.2,0.5,0.4,0.7,0.1,0.3,0.80.20.50.40.70.10.30.8
