基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題

1、基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題長(zhǎng)沙市雅禮中學(xué)長(zhǎng)沙市雅禮中學(xué)陳丹琦陳丹琦【摘要摘要】基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題是一類以集合信息為狀態(tài)且狀態(tài)總數(shù)為指數(shù)級(jí)的特殊的動(dòng)態(tài)規(guī)劃問題在狀態(tài)壓縮的基礎(chǔ)上，有一類問題的狀態(tài)中必須要記錄若干個(gè)元素的連通情況，我們稱這樣的問題為基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題，本文著重對(duì)這類問題的解法及優(yōu)化進(jìn)行探討和研究本文主要從動(dòng)態(tài)規(guī)劃的幾個(gè)步驟——?jiǎng)澐蛛A段，確立狀態(tài)，狀態(tài)轉(zhuǎn)移以及程序?qū)崿F(xiàn)來介紹這類問題的一般解法，會(huì)特別

2、針對(duì)到目前為止信息學(xué)競(jìng)賽中涌現(xiàn)出來的幾類題型的解法作一個(gè)探討結(jié)合例題，本文還會(huì)介紹作者在減少狀態(tài)總數(shù)和降低轉(zhuǎn)移開銷兩個(gè)方面對(duì)這類問題優(yōu)化的一些心得【關(guān)鍵詞關(guān)鍵詞】狀態(tài)壓縮連通性括號(hào)表示法輪廓線插頭棋盤模型IOI2008中國國家集訓(xùn)隊(duì)論文長(zhǎng)沙市雅禮中學(xué)陳丹琦第3頁【序言序言】先看一個(gè)非常經(jīng)典的問題——旅行商問題(即TSP問題，TravelingSalesmanProblem)：一個(gè)n(≤15)個(gè)點(diǎn)的帶權(quán)完全圖，求權(quán)和最小的經(jīng)過每個(gè)點(diǎn)恰好一

3、次的封閉回路這個(gè)問題已經(jīng)被證明是NP完全問題，那么對(duì)于這樣一類無多項(xiàng)式算法的問題，搜索算法是不是解決問題的唯一途徑呢答案是否定的不難發(fā)現(xiàn)任何時(shí)候我們只需要知道哪些點(diǎn)已經(jīng)被遍歷過而遍歷點(diǎn)的具體順序?qū)σ院蟮臎Q策是沒有影響的，因此不妨以當(dāng)前所在的位置i，遍歷過的點(diǎn)的集合S為狀態(tài)作動(dòng)態(tài)規(guī)劃：，其中ji，i，jinS()min()()fiSfjSidistji???動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為，雖然為指數(shù)級(jí)算法，但是對(duì)于n=152(2)nOn的數(shù)據(jù)規(guī)模

4、來說已經(jīng)比樸素的的搜索算法高效很多了我們通常把這樣一(!)On類以一個(gè)集合內(nèi)的元素信息作為狀態(tài)且狀態(tài)總數(shù)為指數(shù)級(jí)別的動(dòng)態(tài)規(guī)劃稱為基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃或集合動(dòng)態(tài)規(guī)劃于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃或集合動(dòng)態(tài)規(guī)劃基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題通常具有以下兩個(gè)特點(diǎn)：1數(shù)據(jù)規(guī)模的某一維或幾維非常小；2它需要具備動(dòng)態(tài)規(guī)劃問題的兩個(gè)基本性質(zhì)：最優(yōu)性原理最優(yōu)性原理和無后效性無后效性一般的狀態(tài)壓縮問題，壓縮的是一個(gè)小范圍內(nèi)每個(gè)元素的決策，狀態(tài)中元素的信息相對(duì)獨(dú)立而有

5、些問題，僅僅記錄每個(gè)元素的決策是不夠的，不妨再看一個(gè)例子：給你一個(gè)mn(mn≤9)的矩陣，每個(gè)格子有一個(gè)價(jià)值，要求ijV找一個(gè)連通塊使得該連通塊內(nèi)所有格子的價(jià)值之和最大按從上到下的順序依次考慮每個(gè)格子選還是不選，下圖為一個(gè)極端情況，其中黑色的格子為所選的連通塊只考慮前5行的時(shí)候，所有的黑色格子形成了三個(gè)連通塊，而最后所有的黑色格子形成一個(gè)連通塊如果狀態(tài)中只單純地記錄前一行或前幾行的格子選還是不選，是無法準(zhǔn)確描述這個(gè)狀態(tài)的，因此壓縮的狀態(tài)

6、中我們需要增加一維，記錄若干個(gè)格子之間的連通情況我們把這一類必須要在狀態(tài)中記錄若干個(gè)元素之間的連通信息的問題稱為基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題本文著重對(duì)這類問題進(jìn)行研究連通是圖論中一個(gè)非常重要的概念，在一個(gè)無向圖中，如果兩個(gè)頂點(diǎn)之間存在一條路徑，則稱這兩個(gè)點(diǎn)連通而基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃問題與圖論模型有著密切的關(guān)聯(lián)，比如后文涉及到的哈密爾頓回路、生成樹等等通常這類問題的本身與連通性有關(guān)或者隱藏著連通