计算机问题求解-算法方法.ppt

《计算机问题求解-算法方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机问题求解–论题1-11-算法方法2012年12月11日方法与技术(结构)问题：给定一群人(例如：在一个大操场上)，给定一个数值(例如:175)，输出高度恰好等于该数值的人。方法：搜索但是我们仍然需要明确，用什么样的方式来实现“搜索”问题1：你能解释下面的话吗？搜索“解空间”–一个例子一位父亲请一位数学家猜他3个孩子的年龄，他提示说：3人年龄的乘积是36。这时他们恰好经过一幢房子，父亲又提示说：他们年龄之和等于这房子窗户的个数。父亲见数学家仍然犹豫，又补充说：老大很小的时候家中没有其他孩子跟他一起玩。你能说出3个孩子的年龄吗？初始的解空间假设年龄精确到整数集合S所有可能的解的集合S={(i

2、,j,k)

3、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可能的解的集合再进一步就是解！当前可能的解的集合：{(1,6,6),(2,2,9)}但是：老大没有同年龄的兄弟姐妹．因此三个孩子的年龄分别

4、是：９岁、２岁和２岁问题求解的基本“方法”确定合理的解空间，并表示为某种“结构”。利用已知的限制条件（知识）尽可能快的压缩可能的解空间。当解空间已经足够小，我们就可以“直接”解题。如果很难确定解空间的范围，或者很难有效地缩小解空间，这个题目就“很难”。搜索结构深度优先-DFS广度优先-BFS“聪明”的搜索结构二分搜索树-BST24206505123182130堆–Heap优先队列的一种实现问题2：你能解释一下解MaximalPolygonDistance问题的过程中是如何建立并缩小解空间的吗？问题3：你阅读的材料中还介绍了哪些“算法方法”？你能从“搜索”的角度对它们加以解释吗？Divide-a

5、nd-Conquer;Greedy;DynamicProgramming;Using“clever”datastructureMergesort:Divide-and-ConquerGreedy:MinimalSpanningTreeGreedy:Simple,butmayFail!问题4：你能从“搜索”的角度说明为什么Greedy可能Fail吗？问题5：用DynamicProgramming解最短通路问题为什么就不会出错了？问题6：既然DynamicProgramming本质上是exhaustive,为什么还能保证效率可以接受？用Greedy解“难”题BinPackingProblemSup

6、posewehaveanunlimitednumberofbinseachofcapacityone,andnobjectswithsizess1,s2,…,snwhere0

7、helargestaspossibleExample: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)ThisisNOTanoptimalsolution!但可以证明：也不是太差！Online:会更困难问题8：你是否能用书上“孩子滑雪”的例子，说明：什么是online问题？为什么它被认为更困难？NextFitAlgorithm-NFThestrategy:Putanewiteminthelastbinifpossible,oruseanewbin

8、.Neverlookback!Anexample:S={0.2,0.5,0.4,0.7,0.1,0.3,0.8}0.20.50.40.70.10.30.8问题9：最多比最优解差多少？课外作业DH:4.1;4.2;DH:4.8-4.9;4.11;4.12;DH:4.13-14;