資源描述：
《算法合集之《參數(shù)搜索應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、參數(shù)搜索的應(yīng)用蕪湖市第一中學(xué)汪汀引言參數(shù)搜索是解決最優(yōu)解問(wèn)題的一種常見(jiàn)的方法。其本質(zhì)就是對(duì)問(wèn)題加入?yún)?shù)，先解決有參數(shù)的問(wèn)題，再不斷調(diào)整參數(shù)，最終求得最優(yōu)解。下面通過(guò)幾個(gè)例子來(lái)說(shuō)明這一點(diǎn)。問(wèn)題一分石子問(wèn)題有N個(gè)石子，每個(gè)石子重量Qi；按順序?qū)⑺鼈冄b進(jìn)K個(gè)筐中；求一種方案，使最重的筐盡量輕。問(wèn)題一分石子問(wèn)題N=9,K=3975684327
2、
3、161916最大為19975684327
4、
5、211812最大為21問(wèn)題一分石子問(wèn)題——分析本題可采用動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度O(N2)太高了能否找到實(shí)現(xiàn)更簡(jiǎn)單，更優(yōu)秀的算法呢？問(wèn)題一分石子問(wèn)題——分析９６５８８５?問(wèn)題一分石子問(wèn)題——分析引入?yún)?shù)P，求一個(gè)判定可行
6、解問(wèn)題:判斷是否存在最大重量不超過(guò)P的方案問(wèn)題一分石子問(wèn)題——分析可以用貪心法解決，具體方法如下：按順序把石子放入筐，若一個(gè)筐中石子總重量不足P，我們就繼續(xù)對(duì)這個(gè)筐加入新的石子；如果超過(guò)P，則我們將石子放入新的筐中。問(wèn)題一分石子問(wèn)題——分析N=5,K=3,P=12９６５８3問(wèn)題一分石子問(wèn)題——分析回到最初的問(wèn)題：從小到大枚舉P，找到第一個(gè)可行解，該解即為問(wèn)題所求令T=∑Qi，則這個(gè)算法的時(shí)間復(fù)雜度為O(TN)需要進(jìn)一步優(yōu)化!問(wèn)題一分石子問(wèn)題——分析若我們能找到一個(gè)最大重量不超過(guò)P的方案，則我們可以找出一個(gè)最大重量不超過(guò)P+1的方案二分法！問(wèn)題一分石子問(wèn)題——分析1MT嘗試區(qū)間[1,M-1]嘗
7、試區(qū)間[M+1,T]不斷重復(fù)以上步驟即可找到問(wèn)題的最優(yōu)解。時(shí)間復(fù)雜度O(NlogT)特別地，由于答案必定為某一段連續(xù)石子的重量和所以可以得到一個(gè)時(shí)間復(fù)雜度為O(Nlog3N)的算法小結(jié)首先引入?yún)?shù)P，解決帶參數(shù)的問(wèn)題；用貪心法可以判斷是否存在最大重量和不超過(guò)p的方案；枚舉P求出問(wèn)題的最優(yōu)解；二分法降低了算法的時(shí)間復(fù)雜度，最終解決了問(wèn)題。小結(jié)Ⅰ首先引入?yún)?shù)P，解決帶參數(shù)的問(wèn)題；判斷是否存在結(jié)果優(yōu)于P的方案Ⅱ調(diào)整P得到最優(yōu)解。通過(guò)二分法或迭代法減少調(diào)整次數(shù)，降低算法時(shí)間復(fù)雜度。問(wèn)題二最大比率問(wèn)題有N道題目，每道題目有不同的分值和難度，分別為A，B（分值及難度均為正數(shù)）；ii要求從某一題開(kāi)始，連續(xù)
8、選至少K道題目，滿足分值和與難度和的比最大。問(wèn)題二最大比率問(wèn)題例如N=7,K=3A43219899B22131121選擇第3題到第6題，比為(9+8+9+9)/(1+1+2+1)=7這是上例的最優(yōu)解問(wèn)題二最大比率問(wèn)題先來(lái)解決一個(gè)與之類似的簡(jiǎn)化版問(wèn)題：在一個(gè)數(shù)列中找連續(xù)多個(gè)數(shù)（至少K個(gè)），總和最大。建立一個(gè)隊(duì)列Q，開(kāi)始時(shí)隊(duì)列只有K個(gè)元素，按順序往隊(duì)列中添加新的元素，添加后計(jì)算Q1+Q2..+QL-K的和，記為S。若S<0，則將Q1,Q2..QL-K從隊(duì)列中刪除，否則暫時(shí)保留這些數(shù)。并不斷更新最大值。問(wèn)題二最大比率問(wèn)題——分析-12-364-13掃描一遍的復(fù)雜度是線性的這就是最優(yōu)解和為-１和為２
9、和為-1和為12問(wèn)題二最大比率問(wèn)題——分析現(xiàn)在我們已經(jīng)能在O(N)的時(shí)間內(nèi)解決簡(jiǎn)化后的問(wèn)題了。這個(gè)方法能不能應(yīng)用于原題？很遺憾，由于原題中每個(gè)數(shù)據(jù)有兩個(gè)參數(shù)，故它們對(duì)最終結(jié)果產(chǎn)生的影響是不確定的，因此對(duì)于原題我們不能直接套用這個(gè)算法?，F(xiàn)在必須消除這個(gè)不確定因素。問(wèn)題二最大比率問(wèn)題——分析為此，我們必須引入?yún)?shù)p，求一個(gè)判定可行解問(wèn)題：判斷是否存在一個(gè)比大于p的方案問(wèn)題二最大比率問(wèn)題——分析新的問(wèn)題可以這樣描述：求兩個(gè)下標(biāo)i’,j’，滿足j’-i’+1≥k①(Ai’+Ai’+1....+Aj’)/(Bi’+Bi’+1…+Bj’)>p②②Ai’+Ai’+1....+Aj’>p(Bi’+Bi’+1
10、…+Bj’)(Ai’-pBi’)+(Ai’+1-pBi’+1)…+(Aj’-pBj’)>0問(wèn)題二最大比率問(wèn)題——分析(Ai’-pBi’)+(Ai’+1-pBi’+1)…+(Aj’-pBj’)>0令Ci=Ai-pBi，Ci’+Ci’+1…+Cj’>0可以借用剛才的結(jié)論在數(shù)列C中找一段連續(xù)的數(shù)（至少K個(gè)），和為正數(shù)。我們能在O(N)的時(shí)間內(nèi)找到中和最大的一段，記為S：?若S＞0則找到了一個(gè)可行方案?若S≤0，則問(wèn)題無(wú)解問(wèn)題二最大比率問(wèn)題——分析O(N)的時(shí)間判斷出是否存在比不小于P的方案。通過(guò)二分法，調(diào)整參數(shù)P的大小，不斷逼近最優(yōu)解。時(shí)間復(fù)雜度O(NlogT)小結(jié)上例的難點(diǎn)在于每道題有難度和分值
11、兩個(gè)數(shù)據(jù)，使我們無(wú)法確定它們對(duì)最終結(jié)果的影響，因此不能直接套用之前的掃描法。引入?yún)?shù)后，成功的消除了這個(gè)不確定因素，從而輕松的解決了問(wèn)題?？偨Y(jié)?回顧兩個(gè)例子:?分石子問(wèn)題：動(dòng)態(tài)規(guī)劃時(shí)空編程復(fù)雜度都很高參數(shù)搜索時(shí)空復(fù)雜度比較優(yōu)秀效率比較高?最大比率問(wèn)題：直接掃描無(wú)法解決參數(shù)搜索問(wèn)題豁然開(kāi)朗降低思維復(fù)雜度總結(jié)?參數(shù)搜索主要解決最優(yōu)解問(wèn)題，它的應(yīng)用非常廣泛，優(yōu)點(diǎn)也十分突出，使得我們解此類問(wèn)題又多了一種有力的武器。?
