計(jì)算機(jī)問題求解算法方法演示

（優(yōu)選）計(jì)算機(jī)問題求解算法方法當(dāng)前1頁，總共24頁。方法與技術(shù)(結(jié)構(gòu))問題：給定一群人(例如：在一個(gè)大操場上)，給定一個(gè)數(shù)值(例如:

175)，輸出高度恰好等于該數(shù)值的人。方法：搜索但是我們?nèi)匀恍枰鞔_，用什么樣的方式來實(shí)現(xiàn)“搜索”當(dāng)前2頁，總共24頁。問題1：你能解釋下面的話嗎？當(dāng)前3頁，總共24頁。搜索“解空間”–一個(gè)例子一位父親請一位數(shù)學(xué)家猜他3個(gè)孩子的年齡，他提示說：3人年齡的乘積是36。這時(shí)他們恰好經(jīng)過一幢房子，父親又提示說：他們年齡之和等于這房子窗戶的個(gè)數(shù)。父親見數(shù)學(xué)家仍然猶豫，又補(bǔ)充說：老大很小的時(shí)候家中沒有其他孩子跟他一起玩。你能說出3個(gè)孩子的年齡嗎？當(dāng)前4頁，總共24頁。初始的解空間假設(shè)年齡精確到整數(shù)集合S所有可能的解的集合S={(i,j,k)|i,j,k

是非負(fù)整數(shù)｝當(dāng)前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當(dāng)前6頁，總共24頁。解空間還有縮小的可能盡管已經(jīng)知道了年齡之和,那個(gè)數(shù)學(xué)家仍然說不出答案…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

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

DFS廣度優(yōu)先-

BFS當(dāng)前10頁，總共24頁?！奥斆鳌钡乃阉鹘Y(jié)構(gòu)二分搜索樹-

BST24206505123182130堆–

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