計算機問題求解算法方法演示

（優(yōu)選）計算機問題求解算法方法現在是1頁\一共有24頁\編輯于星期二方法與技術(結構)問題：給定一群人(例如：在一個大操場上)，給定一個數值(例如:

175)，輸出高度恰好等于該數值的人。方法：搜索但是我們仍然需要明確，用什么樣的方式來實現“搜索”現在是2頁\一共有24頁\編輯于星期二問題1：你能解釋下面的話嗎？現在是3頁\一共有24頁\編輯于星期二搜索“解空間”–一個例子一位父親請一位數學家猜他3個孩子的年齡，他提示說：3人年齡的乘積是36。這時他們恰好經過一幢房子，父親又提示說：他們年齡之和等于這房子窗戶的個數。父親見數學家仍然猶豫，又補充說：老大很小的時候家中沒有其他孩子跟他一起玩。你能說出3個孩子的年齡嗎？現在是4頁\一共有24頁\編輯于星期二初始的解空間假設年齡精確到整數集合S所有可能的解的集合S={(i,j,k)|i,j,k

是非負整數｝現在是5頁\一共有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現在是6頁\一共有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

可能的解的集合現在是7頁\一共有24頁\編輯于星期二再進一步就是解！當前可能的解的集合：{(1,6,6),(2,2,9)}但是：老大沒有同年齡的兄弟姐妹．因此三個孩子的年齡分別是：９歲、２歲和２歲現在是8頁\一共有24頁\編輯于星期二問題求解的基本“方法”確定合理的解空間，并表示為某種“結構”。利用已知的限制條件（知識）盡可能快的壓縮可能的解空間。當解空間已經足夠小，我們就可以“直接”解題。如果很難確定解空間的范圍，或者很難有效地縮小解空間，這個題目就“很難”?，F在是9頁\一共有24頁\編輯于星期二搜索結構深度優(yōu)先-

DFS廣度優(yōu)先-

BFS現在是10頁\一共有24頁\編輯于星期二“聰明”的搜索結構二分搜索樹-

BST24206505123182130堆–

Heap優(yōu)先隊列的一種實現現在是11頁\一共有24頁\編輯于星期二問題2：你能解釋一下解MaximalPolygonDistance問題的過程中是如何建立并縮小解空間的嗎？現在是12頁\一共有24頁\編輯于星期二現在是13頁\一共有24頁\編輯于星期二問題3：你閱讀的材料中還介紹了哪些“算法方法”？你能從“搜索”的角度對它們加以解釋嗎？Divide-and-Conquer;Greedy;DynamicProgramming;Using“clever”datastructure現在是14頁\一共有24頁\編輯于星期二Mergesort:Divide-and-Conquer現在是15頁\一共有24頁\編輯于星期二Greedy:MinimalSpanningTree現在是16頁\一共有24頁\編輯于星期二Greedy:Simple,butmayFail!問題4：你能從“搜索”的角度說明為什么Greedy可能Fail嗎？現在是17頁\一共有24頁\編輯于星期二問題5：用DynamicProgramming解最短通路問題為什么就不會出錯了？現在是18頁\一共有24頁\編輯于星期二問題6：既然DynamicProgramming本質上是exhaustive,為什么還能保證效率可以接受？現在是19頁\一共有24頁\編輯于星期二用Greedy解“難”題BinPackingProblemSupposewehaveanunlimitednumberofbinseachofcapacityone,andnobjectswithsizess1,s2,…,snwhere0<si1(siarerationalnumbers)Optimizationproblem:Determinethesmallestnumberofbinsintowhichtheobjectscanbepackets(andfindanoptimalpacking).BinpackingisaNPCproblem問題7：為什么這是難題？現在是20頁\一共有24頁\編輯于星期二FirstFitDecreasing-FFDThestrategy:packingthelargestaspossibleExample: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!但可以證明：也不是太差！現在是21頁\一共有24頁\編輯于星期二Online:會更困難問題8：你是否能用書上“孩子滑雪”的例子，說明：什么是online問題？為什么它被認為更困難？現在是22頁\一共有24頁\編輯于星期二NextFitAlgorithm-NFThestrategy:Putanewiteminthelastbinifpossible,oruseanewbin.Neverlookb