.,計算機問題求解論題1-11-算法方法,2012年12月11日,.,方法與技術(結構),問題：給定一群人(例如：在一個大操場上)，給定一個數值(例如:175)，輸出高度恰好等于該數值的人。方法：搜索但是我們仍然需要明確，用什么樣的方式來實現“搜索”,.,問題1：你能解釋下面的話嗎？,.,搜索“解空間”一個例子,一位父親請一位數學家猜他3個孩子的年齡，他提示說：3人年齡的乘積是36。這時他們恰好經過一幢房子，父親又提示說：他們年齡之和等于這房子窗戶的個數。父親見數學家仍然猶豫，又補充說：老大很小的時候家中沒有其他孩子跟他一起玩。你能說出3個孩子的年齡嗎？,.,初始的解空間,假設年齡精確到整數,集合S,所有可能的解的集合,.,利用條件縮小可能的解空間,集合S1,所有可能的解的集合,條件1：3人年齡乘積為36,.,解空間還有縮小的可能,盡管已經知道了年齡之和,那個數學家仍然說不出答案,.,再進一步就是解！,當前可能的解的集合：(1,6,6),(2,2,9)但是：老大沒有同年齡的兄弟姐妹因此三個孩子的年齡分別是：歲、歲和歲,.,問題求解的基本“方法”,確定合理的解空間，并表示為某種“結構”。利用已知的限制條件（知識）盡可能快的壓縮可能的解空間。當解空間已經足夠小，我們就可以“直接”解題。如果很難確定解空間的范圍，或者很難有效地縮小解空間，這個題目就“很難”。,.,搜索結構,深度優先-DFS,廣度優先-BFS,.,“聰明”的搜索結構,二分搜索樹-BST,24,20,6,50,5,12,3,18,21,30,堆Heap優先隊列的一種實現,.,問題2：你能解釋一下解MaximalPolygonDistance問題的過程中是如何建立并縮小解空間的嗎？,.,.,問題3：你閱讀的材料中還介紹了哪些“算法方法”？你能從“搜索”的角度對它們加以解釋嗎？,Divide-and-Conquer;Greedy;DynamicProgramming;Using“clever”datastructure,.,Mergesort:Divide-and-Conquer,.,Greedy:MinimalSpanningTree,.,Greedy:Simple,butmayFail!,問題4：你能從“搜索”的角度說明為什么Greedy可能Fail嗎？,.,問題5：用DynamicProgramming解最短通路問題為什么就不會出錯了？,.,問題6：既然DynamicProgramming本質上是exhaustive,為什么還能保證效率可以接受？,.,用Greedy解“難”題,BinPackingProblemSupposewehaveanunlimitednumberofbinseachofcapacityone,andnobjectswithsizess1,s2,snwhere0si1(siarerationalnumbers)Optimizationproblem:Determinethesmallestnumberofbinsintowhichtheobjectscanbepackets(andfindanoptimalpacking).BinpackingisaNPCproblem,問題7：為什么這是難題？,.,FirstFitDecreasing-FFD,Thestrategy:packingthelargestaspossibleExample:S=(0.8,0.5,0.4,0.4,0.3,0.2,0.2,0.2),B1,B2,B3,B4,0.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-NF,Thestrategy:Putanewiteminthelastbinifpossible,oruseanewbin.Neverlookback!Anexample:S=0.2,0.5,0.4,0.7,0.1,0.3,0.8,0.