算法基础之最短Hamilton路径

本文主要是介绍算法基础之最短Hamilton路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短Hamilton路径

• 核心思想： 数位dp

  • 用二进制数 存当前所有点 遍历过为1

  • 遍历i图中j点 若j点走过 则求j点路径长度

    • f[state][j] = f[state_k][k] + w[k][j] state为除去j点的图

  •   #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 20, M = 1<< N ;int f[M][N];int w[N][N];  //权值int n;int main(){cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];  //输入所有边长度(权值)memset(f , 0x3f, sizeof f);  //初始化无穷大 便于取minf[1][0] = 0;  //只有起点走过 且当前点为起点 距离为0for(int i=1;i< 1 << n;i++)  //遍历每一张图for(int j=0;j<n;j++)  //遍历i图中每个点if(i >> j & 1)  // 若j点走过for(int k= 0;k<n;k++)  //遍历j点前一个点kif(i >> k & 1)  //k也走过 //更新f[i][j] = f[去掉i][k] +w //特别地 当j == k时 f[state][k] 不合法 因为图中必须包含k点//所有min只会取f[i][j]f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[k][j]);cout<< f[(1 << n) - 1][n-1]<<endl;  //输出所有点都走过 当前点为n-1的数值}
    

这篇关于算法基础之最短Hamilton路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---