本文主要是介绍状态压缩动态规划:最短Hamilton路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接
[状态压缩动态规划] 最短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 1≤n≤20,
0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0≤a[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 1≤n≤20,点非常少,可以考虑使用状态压缩的方式表示每个点是否经过。例如,有 5 5 5个点,经过了点 0 、 2 、 3 0、2、3 0、2、3,其状态的二进制形式为 ( 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的上一点jfor(int j = 0; j < n; j ++){//状态中包含jif((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;
}
这篇关于状态压缩动态规划:最短Hamilton路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!