对使用状态压缩和动态规划求hamilton最短路径的理解

Nambers commented 3 years ago

https://eritque-arcus.tech/2021/06/20/%E5%AF%B9%E4%BD%BF%E7%94%A8%E7%8A%B6%E6%80%81%E5%8E%8B%E7%BC%A9%E5%92%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%B1%82hamilton%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E7%9A%84%E7%90%86%E8%A7%A3/#%E7%AE%97%E6%B3%95%E4%BB%A3%E7%A0%81

使用状态压缩和动态规划求hamilton最短路径

JIACHENG135 commented 2 years ago

请问下怎么复现具体的最短路？

输入

输出

0->4->2->4->2->
18

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int g[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> g[i][j];

    int state,substate,dp[n][1<<n];
    memset(dp, 0x3f3f3f, sizeof dp);
    int next[n];
    memset(next, 0x3f3f3f, sizeof next);
    dp[0][1] = 0;
    for(state = 0; state < 1 << n; state ++ ){
        for(int i = 0;i<n;i++){
            if(state >> i & 1){
                substate = state - ( 1 << i);
                for(int j = 0 ; j < n ; j++){
                    if(substate >> j & 1){
                        if(dp[j][substate] + g[j][i] < dp[i][state]){
                            dp[i][state] = dp[j][substate] + g[j][i];
                            next[j] = i;
                        }
                    }
                }
            }
        }
    }
    int ct = 0, first = 0;
    while(ct < n){
        cout << first << "->";
        ct++;
        first = next[first];
    }
    cout << endl;
    cout << dp[n-1][(1<<n) - 1];
    return 0;
}

Nambers commented 2 years ago

@JIACHENG135 请问下怎么复现具体的最短路？

输入

输出

0->4->2->4->2->
18

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int g[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> g[i][j];

    int state,substate,dp[n][1<<n];
    memset(dp, 0x3f3f3f, sizeof dp);
    int next[n];
    memset(next, 0x3f3f3f, sizeof next);
    dp[0][1] = 0;
    for(state = 0; state < 1 << n; state ++ ){
        for(int i = 0;i<n;i++){
            if(state >> i & 1){
                substate = state - ( 1 << i);
                for(int j = 0 ; j < n ; j++){
                    if(substate >> j & 1){
                        if(dp[j][substate] + g[j][i] < dp[i][state]){
                            dp[i][state] = dp[j][substate] + g[j][i];
                            next[j] = i;
                        }
                    }
                }
            }
        }
    }
    int ct = 0, first = 0;
    while(ct < n){
        cout << first << "->";
        ct++;
        first = next[first];
    }
    cout << endl;
    cout << dp[n-1][(1<<n) - 1];
    return 0;
}

已补充到文章

Nambers / Nambers.github.io

对使用状态压缩和动态规划求hamilton最短路径的理解 | Eritque arcus's blog #16