13個國家集訓隊集2004鬲融

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

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

3、剩余的步數(shù)一個問題：并不是所有的位置都可以改變解決方法：再次窮舉哪些位置可以改變！時間復雜度：O(6!*10)=O(1)優(yōu)秀的算法！例二 邏輯島題目描述：在邏輯島上有3種居民：永遠說真話的神，永遠說假話的惡魔和在白天說真話，在夜里說假話的人。一個社會學家訪問了這個島，但他無法通過外表區(qū)分這3種居民，所以他只能靠分析居民們說的話來判斷他們的種類。島上只有五個居民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。你的任務就是通過居民們說的話來判斷他們的種類以及現(xiàn)在是白天還是黑夜讓我們用人腦分析A: B is human.B: A is evil.A: B is evil.一個簡單的例子：A的話有矛盾B是神！A是惡魔計算機怎樣完成這種推理？失敗！應用窮舉思想題目特點：人數(shù)少于是得到了完全窮舉的算法：情況數(shù)：35*2=486對每句話進行判斷時間復雜度：O(35*2*s)=O(s)小結(jié)先來比較一下例一的兩種算法算法時空復雜度評價搜索高,指數(shù)級未充分利用題目條件窮舉思想低,常數(shù)級巧妙選擇了窮舉對象窮舉或許具有很大的盲目性，但我們自身是靈活的！部分窮舉思想有時候，問題離高效算法只有一步之遙。問題高效算

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

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

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

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