无论多忙都好，每日都要进行数学思维和计算机思维的锻炼，才能让自己做事高效且思维敏捷。

---

题目(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)，状态方程其实也比较容易理解，就是尝试每一种未旅行的城市，并且记录下来。

实现细节

1. 单纯看转移方程，时间复杂度是n!的。但是DP的核心是打表，所以记录过的就不要再跑了。
2. 如何来表示集合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