13個(gè)國家集訓(xùn)隊(duì)集2004鬲融

1、淺談特殊窮舉思想的應(yīng)用河北唐山一中 鬲融窮舉的思想窮舉思想是信息學(xué)中最重要的思想之一，計(jì)算機(jī)的高速度使其具備了進(jìn)行窮舉的條件。然而，隨著圖論、數(shù)論、動(dòng)態(tài)規(guī)劃等方法的發(fā)展，以及搜索算法的不斷改進(jìn)，窮舉似乎越來越不受重視，成為了低效的代名詞。窮舉低效？讓我們先來了解一下窮舉。窮舉的思想窮舉完全窮舉部分窮舉參變量法準(zhǔn)確理解題意 確定使用窮舉思想 明確窮舉對(duì)象下面先來看一下完全窮舉的例子例一 聰明的打字員題目描述(NOI2001)使用一個(gè)只有加減1（Up/Down），左右移動(dòng)光標(biāo)（Left/Right），與1，6交換（Swap0/Swap1）六個(gè)鍵的鍵盤，用最少的步數(shù)把一個(gè)6位數(shù)轉(zhuǎn)化成另外一個(gè)。例如，

2、初始狀態(tài)是123456，要求的狀態(tài)是633451，那么最簡單的轉(zhuǎn)化方法是：123456623451623451633451Swap1UpRight思路1 搜索思路很簡單：通過廣度優(yōu)先搜索確定按鍵順序和最小按鍵次數(shù)并輸出節(jié)點(diǎn)數(shù)：6,000,000過大解決：HASH+A*或雙向廣度優(yōu)先缺點(diǎn)：實(shí)現(xiàn)復(fù)雜度太高，而且效率也不高思路2 使用窮舉思想抓住問題的難點(diǎn)：Swap0/Swap1 !要是沒有這兩個(gè)鍵直接處理就可以把這兩個(gè)鍵先處理，不影響結(jié)果！窮舉這兩個(gè)鍵的使用，只有6！=720種情況思路2 使用窮舉思想這樣我們通過完全窮舉得到了一個(gè)算法：把按鍵過程分為兩步通過Swap0/1得到一個(gè)排列計(jì)算這個(gè)排列后

3、剩余的步數(shù)一個(gè)問題：并不是所有的位置都可以改變解決方法：再次窮舉哪些位置可以改變！時(shí)間復(fù)雜度：O(6!*10)=O(1)優(yōu)秀的算法！例二 邏輯島題目描述：在邏輯島上有3種居民：永遠(yuǎn)說真話的神，永遠(yuǎn)說假話的惡魔和在白天說真話，在夜里說假話的人。一個(gè)社會(huì)學(xué)家訪問了這個(gè)島，但他無法通過外表區(qū)分這3種居民，所以他只能靠分析居民們說的話來判斷他們的種類。島上只有五個(gè)居民A，B，C，D，E。他們說的話只有3種1. I am not divine/evil/human/lying.2. X is not divine/evil/human/lying.3. It is day/night.居民們說話的總數(shù)不

4、超過50。你的任務(wù)就是通過居民們說的話來判斷他們的種類以及現(xiàn)在是白天還是黑夜讓我們用人腦分析A: B is human.B: A is evil.A: B is evil.一個(gè)簡單的例子：A的話有矛盾B是神！A是惡魔計(jì)算機(jī)怎樣完成這種推理？失?。?yīng)用窮舉思想題目特點(diǎn)：人數(shù)少于是得到了完全窮舉的算法：情況數(shù)：35*2=486對(duì)每句話進(jìn)行判斷時(shí)間復(fù)雜度：O(35*2*s)=O(s)小結(jié)先來比較一下例一的兩種算法算法時(shí)空復(fù)雜度評(píng)價(jià)搜索高,指數(shù)級(jí)未充分利用題目條件窮舉思想低,常數(shù)級(jí)巧妙選擇了窮舉對(duì)象窮舉或許具有很大的盲目性，但我們自身是靈活的！部分窮舉思想有時(shí)候，問題離高效算法只有一步之遙。問題高效算

5、法參數(shù)K我們不知道參數(shù)K，所以我們不能解決問題。部分窮舉思想問題的參數(shù)（無法窮舉）重要參數(shù)K部分窮舉，作為參變量可行通過高效算法得到答案使用部分窮舉思想的一般步驟。部分窮舉思想特別適用于最大最小問題最大最小問題定義：這類問題中定義一種權(quán)值，要求產(chǎn)生一種劃分（或其他類似的結(jié)構(gòu)），使劃分的每一部分權(quán)值的最大值達(dá)到最小。 這里最大是權(quán)的最大值，最小是劃分產(chǎn)生的“最大”的最小。一個(gè)重要的問題已知一個(gè)最大權(quán)值，如何快速判斷是否有滿足要求的劃分？ 如果我們能找到這個(gè)問題的答案,那么我們就可以把最大權(quán)值作為參變量，通過對(duì)它進(jìn)行部分窮舉和判斷，得到結(jié)論。一種常用優(yōu)化如果參變量的范圍很大，我們就需要利用題目的條

6、件進(jìn)行優(yōu)化。題目最重要的性質(zhì)是單調(diào)性。單調(diào)性是指如果參變量為x1時(shí)可行，那么參變量大（?。┯趚1時(shí)也可行，而且題目要求的是參變量的最?。ù螅┲怠＿@時(shí)，我們有兩種選擇：仍然用線形的窮舉方法，但是當(dāng)?shù)玫揭粋€(gè)可行的解時(shí)，就停止改用二分形式的窮舉方法。當(dāng)然，二分往往可以使時(shí)間復(fù)雜度減小。例三 草莓這是NOI2003的題目，相信大家都已經(jīng)很熟悉。這里我們要討論的是樹形數(shù)據(jù)。初步想法：既然是求最值，容易想到樹的動(dòng)態(tài)規(guī)劃?？墒?，我們很難列出有效的狀態(tài)轉(zhuǎn)移方程，而且該題數(shù)據(jù)較大，用動(dòng)態(tài)規(guī)劃效率太低。進(jìn)一步考慮：這是一個(gè)最小最大問題，能否使用部分窮舉？首先面臨的問題：如果已知一個(gè)分割方案所對(duì)應(yīng)的x，我們?nèi)绾稳?/p>

7、找一個(gè)解答，或者證明這種分割是不存在的？ （問題） 問題的解決這個(gè)問題可以用貪心來解決。105789x=17從下向上處理，遇到可以分成一組的就分出來。7820919對(duì)于這個(gè)算法的正確性證明請(qǐng)見我的論文。例三的解決我們找到了問題的解法，于是我們就可以通過部分窮舉，用二分法窮舉x的值，然后構(gòu)造解法。問題：相應(yīng)的最大最小問題無法解決。問題的參數(shù)（無法窮舉）部分窮舉，作為參變量可行通過高效算法得到答案草莓的分割方案重要參數(shù)KX的值使用二分法窮舉通過貪心算法得到答案最大最小匹配我們來用部分窮舉的思想解決一個(gè)經(jīng)典的圖論問題。帶權(quán)二分圖的最大最小匹配問題已知一個(gè)帶權(quán)的二分圖，求一個(gè)滿足下列條件的匹配：這個(gè)匹

8、配是一個(gè)完備匹配這個(gè)匹配是滿足第一個(gè)條件中，匹配邊的最大權(quán)最小的匹配。 最大最小匹配的實(shí)際意義這種匹配的計(jì)算在日常生活中經(jīng)常遇到。例如一個(gè)公司有n個(gè)貨倉，n個(gè)銷售點(diǎn)。已知從第i個(gè)貨倉運(yùn)送產(chǎn)品到第j個(gè)銷售點(diǎn)所需時(shí)間為T(i,j)，每個(gè)貨倉的儲(chǔ)藏量和每個(gè)銷售點(diǎn)的需求量恰好相等。如何在最短的時(shí)間內(nèi)將貨物運(yùn)送到所有銷售點(diǎn)？最大最小匹配再看一個(gè)最大最小匹配問題的實(shí)例：1231236481015為了清晰，這里只有6條邊，其他的邊權(quán)為無窮大，不考慮。我們可以看到，這個(gè)圖的最小權(quán)匹配不是最大最小匹配。最大最小匹配：解決應(yīng)用部分窮舉的思想，我們需要回答這個(gè)問題：如果已知權(quán)的最大值，如何產(chǎn)生一個(gè)滿足題目要求的匹配？ 1231236481015權(quán)的最大值：7找不到完備匹配！權(quán)的最大值：8找到完備匹配！這就是最大最小匹配。最大最小匹配：解決這樣我們得到了一個(gè)最大最小匹配問題的高效算法：對(duì)最大權(quán)進(jìn)行部分窮舉執(zhí)行最大匹配的算法尋找完備匹配時(shí)間復(fù)雜度：O(n5) 用線形窮舉，但是效果也不錯(cuò) O(n3logn)二分窮舉。對(duì)這個(gè)問題我們還可以進(jìn)行一些擴(kuò)展：最小最大匹配一樣的算法帶權(quán)圖的最大最小匹配權(quán)最大的帶權(quán)二分圖最大最小匹配總結(jié)通過分析，我們可以看出：窮舉