3. 更复杂的动态规划

佚名 6年前 (2019-04-12) 随笔 962人围观抢沙发百度已收录

#include<iostream>
using namespace std;
const int MAX_N = 1000;
const int MAX_M = 1000; 
//m 城市， n 车票， a -> b 
int n, m, a, b;
int t[MAX_N]; //马匹数 
int d[MAX_M][MAX_M];//图的邻接矩阵表示（-1表示没有边） 
int INF = 0x3f3f3f3f;
double dp[1 << MAX_N][MAX_M];
// dp[S][v] = 到达 v 剩下的车票集合为 S，并且现在在城市 v 的状态所需要的最小花费 
void solve() {
    for (int i = 0; i < 1 << n; i++)
        fill(dp[i], dp[i] + m, INF);
    dp[(1 << n) - 1][a - 1] = 0;
    double res = INF;
    for (int S = (1 << n) - 1; S >= 0; S--) {
        cout<<S<<' ';
        res = min(res, dp[S][b - 1]);
        for (int v = 0; v < m; v++)
            for (int i = 0; i < n; i++)
                if (S >> i & 1) {
                    cout<<S<<endl;
                    for (int u = 0; u < m; u++)
                        if (d[v][u] >= 0)
                            dp[S & ~(1 << i)][u] = min(dp[S & ~(1 << i)][u], dp[S][v] + (double) d[v][u] / t[i]);
                }
    }
    if (res == INF)
        printf("Impossible\n");
    else
        printf("%.3f\n",res);
}
int main() {
    n = 2; m = 4;
    a = 2; b = 1;
    t[0] = 3; t[1] = 1;
    d[0][0] = -1; d[0][1] = -1; d[0][2] = 3; d[0][3] = 4;
    d[1][0] = -1; d[1][1] = -1; d[1][2] = 3; d[1][3] = 5;
    d[2][0] = 3;  d[2][1] = 3;  d[2][2] = -1; d[2][3] = -1;
    d[3][0] = 2;  d[3][1] = 5;  d[3][2] = -1; d[3][3] = -1;
    solve();
}

View Code

1. 状态压缩DP

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　这个问题是著名的旅行商问题（TSP，Traveling Salesman Problem）。TSP问题是NP困难的，没有已知的多项式时间的高效算法可以解决这一问题。在这个问题中，所有可能的路线共有（n - 1）！种，所以肯定不能遍历每一种情况，我们试着用DP来解决。

　　定义： S ：为现在已经访问过的顶点的集合（起点 0 当做还未访问过的顶点）

　　　　　 v ：为当前所在的顶点

　　　　　 dp[ S ][ v ] =：从 v 出发访问剩余所有的顶点，最终回到顶点 0 的路径的权重总和的最小值。

　　由于从 v 出发可以移动到任意的一个节点 u ∉ S，递推式为：

　　　　　　dp[ V ][ 0 ] = 0

　　　　　　dp[ S ][ v ] = min { dp[ S υ { u }][ u ] + d( v, u ) | u ∉ S}

　　在这个递推式中有一个是集合而不是整数，因此需要稍加处理。首先我们使用记忆化搜索求解。虽然有一个是集合，但是我们可以把它编码为一个整数，或者给它们定义一个全序关系并用二叉搜索树存储。特别地，对于集合我们可以把每一个元素的选取与否对应到一个二进制位里，从而把状态压缩成一个整数，大大方便了计算和维护。

int n;
int d[MAX_N][MAX_N];
int dp[1 << MAX_N][MAX_N];
//已经访问过的节点集合为S,当前位置为 v 
int rec(int S, int v) {
    if (dp[S][v] >= 0)
        return dp[S][v];
    if (S == (1 << n) - 1 && v == 0)
        //已经访问过所有节点并回到 0 号点 
        return dp[S][v] = 0;
    int res = INF;
    for (int u = 0; u < n; u++)
        if (!(S >> u & 1))
            res = min(res, rec(S | 1 << u, u) + d[v][u]);
    return dp[S][v] = res;
}
void solve() {
    memset(dp, -1, sizeof(dp));
    printf("%d\n", rec(0,0));
}

　　复杂度为 0（2ⁿn²）。对于不是整数的情况，很多时候很难确定一个合适的递推顺序，因此使用记忆化搜索可以避免这个问题。不过在这个问题中，对于任意两个整数 i 和 j，如果它们对应的集合满足 S（i） ⊆ S（j），就有 i ≤ j，因此可以像下面一样用循环求解。

int n;
int d[MAX_N][MAX_N];
int dp[1 << MAX_N][MAX_N];

void solve() {
    // 用足够大的值初始化数组
    for (int S = 0; S < 1 << n; S++) 
        fill(dp[S], dp[S] + n, INF);
    dp[(1 << n) - 1][0] = 0;
    
    for (int S = (1 << n) - 2; S >= 0; S--)
        for (int v = 0; v < n; v++)
            for(int u = 0; u < n; u++)
                if (!(S >> u &1))
                    dp[S][v] = min(dp[S][v], dp[S | 1 << n][u] + d[v][u]);
    
    printf("%d\n", dp[0][0]);
}