无论多忙都好，每日都要进行数学思维和计算机思维的锻炼，才能让自己做事高效且思维敏捷。
题目(GDINOJ)
http://114.215.99.34/#/enter/problem?pid=1044
春游的时间到了，CC想要利用这个难得的好时间去旅游。
CC有N个想要去的旅游景点，他想要在这个寒假全部都去玩一次，经过他的调查，他已经得到了任何两个旅游景点之间的路费。所以他想让你帮他设计一条旅行路线，使得最终的费用最小。
分析
这是一个很经典的TSP问题了，NP难的一个问题。因为时间复杂度是N!，所以这里输入上限是20。虽然只有20个城市，但是时间复杂度依然相当高，常规算法依然十分耗时。（现在已经有很好地启发式算法的方案来解决了，这里不展开讨论，这里讨论的是常规算法）
求解
我们采用动态规划来求解，动态规划最难的地方在于如何证明子问题具有全局最优，状态的定义和状态转移方程的设定。当然了，编程实现也不容易。
状态定义
我们先寻求一下最优解子结构，我们先定义一个状态dp(i,j)，其中i表示从旅行到了第i点，j是一个集合，表示未旅行的点的集合。所以，状态dp(i,j)就表示从起点开始旅行到了第i点，还有集合J的点没有旅行的最少费用。
状态转移
dp(i,j) = min( dp(i,j) , dp(i, j - k) + G[i][k]) (k 属于集合k)，状态方程其实也比较容易理解，就是尝试每一种未旅行的城市，并且记录下来。
实现细节
- 单纯看转移方程，时间复杂度是n!的。但是DP的核心是打表，所以记录过的就不要再跑了。
- 如何来表示集合J呢？这里运用了状态压缩的技巧，就是把城市用二级制来表示，这里注意爆内存。
代码
#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;
}
感悟
虽然这题大二的时候就做过了。。
我只是想试试步入了社会之后是否能沉下心来进行数学，算法和英语的训练呢？坚持它一年试试吧。。。
2017-8-20
