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

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

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

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

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

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

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