当前位置:网站首页>Shortest Hamilton path (pressure DP)

Shortest Hamilton path (pressure DP)

2022-07-06 12:57:00 Classmate Chen_

subject

Given a sheet n n n A weighted undirected graph of points , Point from 0 ∼ n − 1 0∼n−1 0n1 label , Find the starting point 0 0 0 To the end point n − 1 n−1 n1 The shortest of H a m i l t o n Hamilton Hamilton route .

H a m i l t o n Hamilton Hamilton The definition of path is from 0 0 0 To n − 1 n−1 n1 Pass through every point exactly once without repetition or leakage .

Input format
Enter the integer in the first line n n n.

Next n Every line n n n It's an integer , Among them the first i i i Xing di j j j An integer represents a point i i i To j j j Distance of ( Write it down as a [ i , j ] a[i,j] a[i,j]).

For arbitrary x , y , z x,y,z x,y,z, Data assurance 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] also 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].

Output format
Output an integer , Means shortest Hamilton The length of the path .

Data range
1 ≤ n ≤ 20 1≤n≤20 1n20
0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0a[i,j]107
sample input :

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

1 3 3 5 0
sample output :

18

Pressure DP

f [ i ] [ j ] : f [ i ] [ j ] surface in from 0 go To j , go too Of the Yes spot yes i Of the Yes road path f[i][j]:f[i][j] From 0 Go to the j, All the points passed are i All the paths f[i][j]:f[i][j] surface in from 0 go To j, go too Of the Yes spot yes i Of the Yes road path

1. According to the meaning of the above state , We'll think about it very well

2. Since each f[i][j] It means from 0 Go to the j, All the points reached are i The path of , How to divide sets ?

3. Find the last difference of each scheme according to , We can find that each point can come from other points

4. If we start from a certain point k Come to the point j, Then our current state does not include j Of , Because I haven't reached j

5. according to 4 We can draw f[i][j] Can be f[i-(j)][k]+g[j][k]. explain (j):j Binary representation of this point ,g[j][k]:j Go to the k Distance of

6. Define according to the state : initialization f For negative infinity ——————————f[1][0]=0:(0 The distance to oneself must be 0)

7. The final answer is to go to n-1 Number point , And all points have passed :f[(1<<n)-1][n-1]


AC Code (C++)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=20,M=1<<N;

int f[M][N];   //f[i][j] From 0 Go to the j, All the points passed are i All the paths   example :i=110011(0 It means you haven't walked ,1 Representative walk , And on the far right is 0 This point )
int n;
int w[N][N];  //w[i][j] Express i To j The distance from this point 

int main(){
    
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    
        for(int j=0;j<n;j++){
    
            scanf("%d",&w[i][j]);
        }
    }

    memset(f,0x3f,sizeof f);   // Because the shortest path is required , Initialize to positive infinity 
    f[1][0]=0;  // The first point is that there is no cost 

    for(int i=0;i<1<<n;i++){
      // Enumerate all States of points 
        for(int j=0;j<n;j++){
       // Number of enumeration points 
            if(i>>j&1){
      //i>>j: seek i Of the j Digit number .  If &1 establish , Then represent j This point has passed 
                for(int k=0;k<n;k++){
      //k->j
                    if(i>>k&1 && j!=k){
       // Just like the above judgment ,  Express k This point goes by and is not yourself 
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);  // Judge whether this scheme is the best or from i->k, Again from k->j The optimal 
                    }
                }
            }
        }
    }
    printf("%d",f[(1<<n)-1][n-1]);  // Optimal solution 
    return 0;
}


原网站

版权声明
本文为[Classmate Chen_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/187/202207060914195956.html