算法合集之淺談貪心思想在動態(tài)規(guī)劃中的應(yīng)用(編輯修改稿)
2025-02-17 12:06 本頁面
【文章內(nèi)容簡介】 2022 年全國信息學(xué)冬令營講座 8 Fb[u] = Fb[u] + Fb[S[i]] + 2。end。用公式的形式可以表示為： ①??? ???kiij iij SFaLeavsSFbuFa1 )][][)12][(][現(xiàn)在的問題就是如何決定訪問兒子的順序，不同的訪問順序會產(chǎn)生不同的Fa[u]。我們要使得 Fa[u]盡量的小。一種直觀的方法是 k！枚舉訪問順序，總體復(fù)雜度是 O(nk!)，實(shí)在是很低效。用狀態(tài)壓縮的動態(tài)規(guī)劃進(jìn)行二次動規(guī)的話，可以將復(fù)雜度降為 O(n2kk)，勉強(qiáng)可以接受了。 （注：由于狀態(tài)壓縮的動態(tài)規(guī)劃不是本文的重點(diǎn)，故這里不做展開）但是我們的研究并沒有因此停止!我們嘗試用貪心的思想來分析問題：考慮一種訪問順序中的兩個相鄰元素v 和 v+1，如果交換 v 和 v+1 之后得到的值不如交換前的值，那么 v 一定在 v+1的前面了。具體證明如下：我們對公式①來進(jìn)行一些處理。 ][)2][(][][ 111 ikiijjki ikii SLeavsSFbSLeavsSFa ??????????①可以看出，交換 v 和 v+1 之后，對 和 是不會產(chǎn)生?kiia1][?kii1][任何影響的，關(guān)鍵是看 是增大了還是減小了。????kiij SLevsSjFb1 ][)2][(把交換前和交換后的值做差： ][)2][(][)][(]39。[ 11 vvvv SLeasFbasuFa ?????最后得到的 則只跟元][)2 vvSLeSb??素 v 和 v+1 的信息有關(guān)，于別的元素的排列情況無關(guān)，所以元素 v 和 v+1 是可比的。證畢。另外，根據(jù)這個結(jié)果，可以得出另一個結(jié)論：如果 A 一定放在 B 前，B 一定放在 C 前，可以推導(dǎo)出 A 一定放在 C 前。證明：2022 年全國信息學(xué)冬令營講座 9 ][)2][(][)2][( BCCB ABBA SLeavsSFbLeavsSFb ????? 兩式相乘得到： ][)][(][)][( ACCA evsevs證畢。上面這個結(jié)論說明，本題中的“可比性”是可以傳遞的，因此可以根據(jù)這個性質(zhì)確定出一個全序關(guān)系，因而省去了枚舉排列的部分，只需要對所有元素進(jìn)行一次排序即可。時間復(fù)雜度為 O(nklog2k)，非常優(yōu)秀。本題小結(jié)：從原始的動態(tài)規(guī)劃模型入手，分析出算法的大體框架，巧妙的運(yùn)用貪心思想來除去原始算法中的冗余，進(jìn)而達(dá)到優(yōu)化算法的目的。貪心思想在動態(tài)規(guī)劃中的應(yīng)用總結(jié)本文通過四個例題簡單的介紹了貪心思想在動態(tài)規(guī)劃中的兩種簡單應(yīng)用——確立狀態(tài)和優(yōu)化算法。貪心思想運(yùn)用于動態(tài)規(guī)劃時的奇妙之處在于它合理的利用了問題中隱含的一些 特殊信息 ，因而可以使得看似不能動態(tài)規(guī)劃的題目確立出動態(tài)規(guī)劃的狀態(tài)，或者除去算法中的冗余，提高動態(tài)規(guī)劃的效率?！柏澙返膭討B(tài)規(guī)劃”并不是一種算法，而是一種思想，要靈活的在動態(tài)規(guī)劃中運(yùn)用好貪心思想，關(guān)鍵是在于對問題的深入理解和推敲。這要求我們具備“勇于探索” 、 “大膽創(chuàng)新” 、 “舉一反三”的能力?！靖兄x】NOI2022 浙江代表隊(duì)全體成員的支持浙江省紹興縣柯橋中學(xué)吳建峰老師的技術(shù)指導(dǎo)【參考文獻(xiàn)】[1]劉汝佳，黃亮《算法藝術(shù)與信息學(xué)競賽》[2](美)Zbigniew Michalewicz David 《如何解決問題——現(xiàn)代啟發(fā)式方法》2022 年全國信息學(xué)冬令營講座 10 [3]IOI2022 集訓(xùn)隊(duì)論文——《動態(tài)規(guī)劃算法的優(yōu)化技巧》毛子青【附錄】[參考程序][例題二]參考程序: [例題四]參考程序:[例二原題]Tian Ji The Horse RacingDescription Here is a famous story in Chinese history. That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others. Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match。 each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser. Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian39。s. As a result, each time the king takes six hundred silver dollars from Tian. Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match. It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king39。s regular, and his super beat the king39。s plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China? 2022 年全國信息學(xué)冬令營講座 11 Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian39。s horses on one side, and the king39。s horses on the other. Whenever one of Tian39。s horses can beat one from the king, we dr
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1