集訓(xùn)隊作業(yè)游覽計劃trip解題報告

1、WinterCamp2008, Trip Report Yali 游覽計劃(Trip)解題報告 雅禮中學(xué) 陳丹琦問題簡述 給你一個m * n的加權(quán)非負(fù)矩陣，要求從中選出一些方格，使得任意兩個0權(quán)方格中都至少存在一條由選出的方格組成的路徑，并且要求選出的方格權(quán)和最小數(shù)據(jù)規(guī)模：，其中k為0權(quán)方格的個數(shù)算法分析 m, n, k非常小，我們很容易聯(lián)想到用基于狀態(tài)壓縮的動態(tài)規(guī)劃來解決下面從兩種不同的角度提出兩種狀態(tài)壓縮的動態(tài)規(guī)劃的算法并對它們進(jìn)行比較：【算法一】基于連通性狀態(tài)壓縮的動態(tài)規(guī)劃問題可以轉(zhuǎn)化為：一個m * n的加權(quán)非負(fù)矩陣，要求找到一個連通塊使得連通塊內(nèi)所有方格權(quán)值之和最小，且所有的0權(quán)方格必

2、須包含在這個連通塊中在筆者今年國家集訓(xùn)隊論文基于連通性狀態(tài)壓縮的動態(tài)規(guī)劃問題里面對這一類問題作過詳細(xì)的介紹，下面簡單地來介紹一下算法：按照從上到下，從左到右的順序依次來考慮每一個格子，設(shè)f (i, j, S)表示當(dāng)前考慮完(i, j)這個格子后，輪廓線上從左到右n個格子的連通標(biāo)號為S這個狀態(tài)下方格權(quán)和的最小值注意S使用最小表示法，連通的格子標(biāo)記上相同的數(shù)字，沒有選的格子標(biāo)記為0，如右邊圖中，黑色格子表示選擇了的格子，灰色格子表示輪廓線上沒有被選擇的格子，那么S = 1, 0, 2, 0, 2, 0，對于本題的數(shù)據(jù)規(guī)模來說，最多出現(xiàn)5個連通塊，建議使用8進(jìn)制來存儲S的狀態(tài)考慮狀態(tài)的轉(zhuǎn)移：根據(jù)當(dāng)前

3、格子的左邊格子和上面的格子是否選擇分情況進(jìn)行討論，可能新建一個連通塊，可能合并兩個連通塊，可能延續(xù)原來的連通塊，計算新的狀態(tài)的最小表示即可，轉(zhuǎn)移的代價為O(n)實現(xiàn)的時候建議使用寬度優(yōu)先搜索的形式，使用滾動隊列，然后用Hash表來判重，每一次從(i, j)到(i, j+1)的轉(zhuǎn)移Hash表清空因此的總的時間復(fù)雜度為O(擴(kuò)展的狀態(tài)總數(shù) * n)，狀態(tài)總數(shù)主要取決于m, n的大小，k的大小也會間接影響到擴(kuò)展的狀態(tài)總數(shù)(k越大，必須被選擇的格子就越多，那么擴(kuò)展的狀態(tài)總數(shù)就會減小)，對于第8號測試點，m = n = 10，k = 3的最壞情況，擴(kuò)展的狀態(tài)總數(shù)為639452，是完全可以承受的最慢的測試點

4、在0.2s內(nèi)可以運行出來 測試環(huán)境： 測試環(huán)境：Intel Core2 Duo T7100, 1.8GHz, 1G內(nèi)存這種算法的效率受m, n的大小的影響非常大，當(dāng)m, n 13的時候，擴(kuò)展的狀態(tài)總數(shù)已經(jīng)非常多了，算法已經(jīng)不再適用下面提出另一種算法，它的效率主要取決于k的大小【算法二】注意本題的數(shù)據(jù)規(guī)模k很小，最多為10，遠(yuǎn)遠(yuǎn)達(dá)不到O(mn)的級別，可以以此為突破口來分析問題設(shè)狀態(tài)f (i, j, S)表示以(i, j)為匯合點，k個0權(quán)方格是否已經(jīng)與(i, j)連通的二進(jìn)制狀態(tài)為S，這個狀態(tài)下選中方格的最小權(quán)和考慮狀態(tài)的轉(zhuǎn)移，主要有兩種情況：1)合并，其中為S的子集，這種情況下相當(dāng)于將兩個以

5、(i, j)為匯合點的不相交的集合進(jìn)行合并延續(xù) ，其中與(i, j)相鄰，這種情況相當(dāng)于修改匯合點考慮算法的實現(xiàn)，從小到大枚舉S：轉(zhuǎn)移1)，枚舉S的所有非空真子集，可以通過搜索找出S的所有子集，有一個小的技巧可以無重復(fù)無遺漏地枚舉所有的：Repeat If () Then Break Until False考慮二元組()，其中為S的子集，那么每個元素要不在中，要不在中或者不在中，因此共有3k個這樣的二元組，因此轉(zhuǎn)移1)的總代價為O(m * n * 3k)轉(zhuǎn)移2)，是在同一個S的之間進(jìn)行轉(zhuǎn)移，這個可以用最短路算法來進(jìn)行轉(zhuǎn)移，如果使用SPFA算法，時間復(fù)雜度為O(E) = O(mn)，因此轉(zhuǎn)移2)的總代價為O(m * n * 2k)因此這個算法總的時間復(fù)雜度為O(m * n * 3k)，最慢的測試點為0.08s，對于本題的數(shù)據(jù)規(guī)模來說效果非常好 小結(jié)上述我們提出了兩種思考角度不同的狀態(tài)壓縮算法，從本題的數(shù)據(jù)規(guī)模出發(fā)，算法二的程序效率更高，編程復(fù)雜度更低不過我們很難衡量這兩個算法孰優(yōu)孰劣，當(dāng)m = n = 20，k = 10，算法一