計(jì)算機(jī)問(wèn)題求解-算法方法ppt課件

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