状态压缩动态规划:最短Hamilton路径

2023-12-13 03:51:20

题目链接

[状态压缩动态规划] 最短Hamilton路径

题目描述

给定一张 n n n 个点的带权无向图,点从 0 0 0~ n ? 1 n-1 n?1 标号,求起点 0 0 0 到终点 n ? 1 n-1 n?1 的最短 H a m i l t o n Hamilton Hamilton路径。 H a m i l t o n Hamilton Hamilton路径的定义是从 0 0 0 n ? 1 n-1 n?1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n n n

接下来 n n n行每行 n n n个整数,其中第 i i i行第 j j j个整数表示点 i i i j j j的距离(记为 a [ i , j ] a[i,j] a[i,j])。

对于任意的 x x x, y y y, z z z,数据保证 a [ x , x ] = 0 a[x,x]=0 a[x,x]=0 a [ x , y ] = a [ y , x ] a[x,y]=a[y,x] a[x,y]=a[y,x] 并且 a [ x , y ] + a [ y , z ] > = a [ x , z ] a[x,y]+a[y,z]>=a[x,z] a[x,y]+a[y,z]>=a[x,z]

输出格式

输出一个整数,表示最短 H a m i l t o n Hamilton Hamilton路径的长度。

样例 #1

样例输入 #1

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5

样例输出 #1

18

提示

【数据范围】

1 ≤ n ≤ 20 1≤n≤20 1n20

0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0a[i,j]107

算法思想

根据题目描述, H a m i l t o n Hamilton Hamilton路径的定义是从 0 0 0 n ? 1 n-1 n?1 不重不漏地经过每个点恰好一次,求最短 H a m i l t o n Hamilton Hamilton路径的长度。

从数据范围来看, 1 ≤ n ≤ 20 1≤n≤20 1n20,点非常少,可以考虑使用状态压缩的方式表示每个点是否经过。例如,有 5 5 5个点,经过了点 0 、 2 、 3 0、2、3 023,其状态的二进制形式为 ( 01101 ) 2 (01101)_2 (01101)2?

状态表示

f [ s t a t e ] [ i ] f[state][i] f[state][i]表示从起点走到 i i i点时,并且经过点的状态为 s t a t e state state的情况下,最短 H a m i l t o n Hamilton Hamilton路径的长度。

最终结果为 f [ 2 n ? 1 ] [ n ? 1 ] f[2^n-1][n-1] f[2n?1][n?1]

状态计算

计算 f [ s t a t e ] [ i ] f[state][i] f[state][i]可以根据最后一步走到 i i i点的情况分成若干类。

不妨设上一点为 j j j,那么 f [ s t a t e ] [ i ] f[state][i] f[state][i]应该为不包含 i i i的状态走到 j j j点的最短路径长度,再加上 a [ j ] [ i ] a[j][i] a[j][i],即
f [ s t a t e ] [ i ] = m i n { f [ s t a t e ? ( 1 < < i ) ] [ j ] + a [ j ] [ i ] } f[state][i]=min\{f[state-(1<<i)][j]+a[j][i]\} f[state][i]=min{f[state?(1<<i)][j]+a[j][i]}

注意:计算 f [ s t a t e ] [ i ] f[state][i] f[state][i]前提是状态 s t a t e state state已经包含了 i i i点和 j j j点。

初始状态

  • 题目中求最短路径长度,状态应初始化为无穷大。
  • 0 0 0点出发,因此 f [ 1 ] [ 0 ] = 0 f[1][0]=0 f[1][0]=0

时间复杂度

  • 状态数为 2 n × n 2^n\times n 2n×n
  • 状态计算过程中要枚举所有能到达 i i i的点 j j j,时间复杂度为 O ( n ) O(n) O(n)

总的时间复杂度为 O ( n 2 × 2 n ) = 400 × 1048576 = 419 , 430 , 400 O(n^2\times2^n)=400\times 1048576=419,430,400 O(n2×2n)=400×1048576=419,430,400

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << 20, INF = 0x3f3f3f3f;
int a[N][N], f[M][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    //初始状态
    memset(f, 0x3f, sizeof f);       
    f[1][0] = 0;
    //状态计算
    for(int state = 0; state < 1 << n; state ++)
    {
        for(int i = 0; i < n; i ++)
        {
            //状态中包含i点
            if(state >> i & 1)
            {
                //枚举i的上一点j
               for(int j = 0; j < n; j ++)
               {
                   //状态中包含j
                   if((state >> j & 1) && i != j)
                        f[state][i] = min(f[state][i], f[state - (1 << i)][j] + a[j][i]);
               }
            }
        }
    }
    
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

文章来源:https://blog.csdn.net/qiaoxinwei/article/details/134944642
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。