無(wú)論多忙都好艘刚，每日都要進(jìn)行數(shù)學(xué)思維和計(jì)算機(jī)思維的鍛煉，才能讓自己做事高效且思維敏捷姐霍。
題目(GDINOJ)
http://114.215.99.34/#/enter/problem?pid=1044
春游的時(shí)間到了蕊玷，CC想要利用這個(gè)難得的好時(shí)間去旅游应媚。
CC有N個(gè)想要去的旅游景點(diǎn)珊泳，他想要在這個(gè)寒假全部都去玩一次鲁冯，經(jīng)過(guò)他的調(diào)查，他已經(jīng)得到了任何兩個(gè)旅游景點(diǎn)之間的路費(fèi)色查。所以他想讓你幫他設(shè)計(jì)一條旅行路線薯演，使得最終的費(fèi)用最小。
分析
這是一個(gè)很經(jīng)典的TSP問(wèn)題了秧了，NP難的一個(gè)問(wèn)題涣仿。因?yàn)闀r(shí)間復(fù)雜度是N!，所以這里輸入上限是20示惊。雖然只有20個(gè)城市，但是時(shí)間復(fù)雜度依然相當(dāng)高愉镰，常規(guī)算法依然十分耗時(shí)米罚。（現(xiàn)在已經(jīng)有很好地啟發(fā)式算法的方案來(lái)解決了，這里不展開(kāi)討論丈探，這里討論的是常規(guī)算法）
求解
我們采用動(dòng)態(tài)規(guī)劃來(lái)求解录择，動(dòng)態(tài)規(guī)劃最難的地方在于如何證明子問(wèn)題具有全局最優(yōu)，狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的設(shè)定碗降。當(dāng)然了隘竭，編程實(shí)現(xiàn)也不容易。
狀態(tài)定義
我們先尋求一下最優(yōu)解子結(jié)構(gòu)讼渊，我們先定義一個(gè)狀態(tài)dp(i,j)动看，其中i表示從旅行到了第i點(diǎn)，j是一個(gè)集合爪幻，表示未旅行的點(diǎn)的集合菱皆。所以须误，狀態(tài)dp(i,j)就表示從起點(diǎn)開(kāi)始旅行到了第i點(diǎn)，還有集合J的點(diǎn)沒(méi)有旅行的最少費(fèi)用仇轻。
狀態(tài)轉(zhuǎn)移
dp(i,j) = min( dp(i,j) , dp(i, j - k) + G[i][k]) (k 屬于集合k)京痢，狀態(tài)方程其實(shí)也比較容易理解，就是嘗試每一種未旅行的城市篷店，并且記錄下來(lái)祭椰。
實(shí)現(xiàn)細(xì)節(jié)
- 單純看轉(zhuǎn)移方程，時(shí)間復(fù)雜度是n!的。但是DP的核心是打表坤溃，所以記錄過(guò)的就不要再跑了格二。
- 如何來(lái)表示集合J呢？這里運(yùn)用了狀態(tài)壓縮的技巧臣淤，就是把城市用二級(jí)制來(lái)表示，這里注意爆內(nèi)存窃爷。
代碼
#include <string.h>
#include <math.h>
int F[30][30];
const int INF = 99999999 ;
const int MAX = (1<<20)+1 ;
int dp[21][MAX];
int dis[30][30] ;
int min(int a, int b) {
return a<b?a:b ;
}
int n ;
int InitState() {
int res = 0 ;
for( int i = 1 ; i<=n ;i++ ) {
res = res| (1<<(i-1));
}
return res ;
}
int GetState(int State, int des) {
State = State^(1<<(des-1)) ;
return State ;
}
void DP(int State, int des) {
int& Temp = dp[des][State];
if (Temp != INF) return ;
if( State == 0 ) {
Temp = F[des][0] ;
return ;
} else {
for( int i = 1 ; i<= n ;i++ ) {
if( State & (1<<(i-1)) ) {
int NewState = GetState(State,i);
DP(NewState, i);
Temp = min(Temp, dp[i][NewState]+F[des][i]);
}
}
}
}
int main()
{
// freopen("input.in","r",stdin);
while(scanf("%d",&n) != EOF) {
memset( dp , 0 , sizeof(dp) ) ;
for( int i = 1 ; i<=n ;i++ ){scanf("%d",&F[0][i]); F[i][0] = F[0][i]; }
for( int i = 1 ; i<=n ; i++) {
for( int j = 1 ; j<=n ; j++ ) {
scanf("%d",&F[i][j]);
}
}
int All = (1<<n) - 1;
//init
// printf("All: %d\n",All);
for( int i = 0 ; i<=n ; i++ )
for( int j = 0 ; j<=All ; j++)
dp[i][j] = INF ;
All = InitState();
DP(All,0);
printf("%d\n",dp[0][All]) ;
}
return 0;
}
感悟
雖然這題大二的時(shí)候就做過(guò)了邑蒋。。
我只是想試試步入了社會(huì)之后是否能沉下心來(lái)進(jìn)行數(shù)學(xué)按厘，算法和英語(yǔ)的訓(xùn)練呢医吊？堅(jiān)持它一年試試吧。逮京。卿堂。
2017-8-20
