哈密??顿路径(使用动态规划)

代码目录

Hamiltonian Path ( Using Dynamic Programming )
C++ 实现
Java实现
Python3实现
C#实现
Javascript实现

Hamiltonian Path ( Using Dynamic Programming )

给定一个由N个顶点组成的无向图的邻接矩阵 adj[][]，任务是找出该图是否包含一个汉密尔顿路径与否。如果发现是真的，则打印“是”。否则，打印“否”。

哈密顿路径定义为有向或无向图中的路径，该路径仅访问图的每个顶点一次。

例子：

输入：adj[][] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1 , 0, 1, 0, 0}}输出：是解释：给定图存在哈密顿路径，如下图所示：

输入：adj[][] = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0 }}输出：否

朴素方法：解决给定问题的最简单方法是生成 N 个顶点的所有可能排列。对于每个排列，通过检查相邻顶点之间是否存在边来检查它是否是有效的哈密顿路径。如果发现是真的，则打印“是”。否则，打印“否”。

时间复杂度：O(N * N!)空间复杂度：O(1)

高效方法：上述方法可以通过使用动态规划和位优化掩蔽基于以下观察：

这个想法是这样的，对于每个顶点子集 S，检查子集 S 中是否存在一个汉密尔顿路径，它在顶点 v 处结束v 欧元。
如果 v 有一个邻居 u，其中 u € S – {v}，则存在一条以顶点 u 结束的哈密顿路径。
可以通过推广哈密顿路径的顶点子集和结束顶点来解决该问题。

按照以下步骤解决问题：

初始化一个布尔矩阵 dp[][] 维度为 N*2^N 其中 dp[j ][i] 表示子集中是否存在由掩码 i 表示的路径访问 i 中的每个顶点一次，并在顶点 j 处结束。
对于基本情况，更新 dp[i][1 << i] = true，因为 i 在 [0, N – 1] 范围内
迭代范围 [1, 2^N – 1] 使用变量 i 并执行以下步骤：
- 在掩码 i 中设置了位的所有顶点都包含在子集中。
- 迭代范围 [1, N] 使用将表示当前子集掩码 i 的哈密顿路径的结束顶点的变量 j 和执行以下步骤：
  - 如果 i 和 2^j 的值为真，则使用变量 k 迭代范围 [1, N] 并且如果 dp[k][i^2^j] 为真，则标记 dp[j][i] 为真并跳出循环。
  - 否则，继续下一次迭代。
使用变量 i 遍历范围，如果 dp[i][2^N 的值 – 1 ] 为真，则存在一个汉密尔顿路径结束于顶点 i。因此，打印“是”。否则，打印“否”。

下面是上述方法的实现：

C++ 实现

// C++ program for the above approach

 #include <bits/stdc++.h>

using namespace std;

const int N = 5;

 // Function to check whether there

// exists a Hamiltonian Path or not

bool Hamiltonian_path(

    vector<vector<int> >& adj, int N)

{

    int dp[N][(1 << N)];

     // Initialize the table

    memset(dp, 0, sizeof dp);

     // Set all dp[i][(1 << i)] to

    // true

    for (int i = 0; i < N; i++)

        dp[i][(1 << i)] = true;

     // Iterate over each subset

    // of nodes

    for (int i = 0; i < (1 << N); i++) {

         for (int j = 0; j < N; j++) {

             // If the jth nodes is included

            // in the current subset

            if (i & (1 << j)) {

                 // Find K, neighbour of j

                // also present in the

                // current subset

                for (int k = 0; k < N; k++) {

                     if (i & (1 << k)

                        && adj[k][j]

                        && j != k

                        && dp[k][i ^ (1 << j)]) {

                         // Update dp[j][i]

                        // to true

                        dp[j][i] = true;

                        break;

                    }

                }

            }

        }

    }

     // Traverse the vertices

    for (int i = 0; i < N; i++) {

         // Hamiltonian Path exists

        if (dp[i][(1 << N) - 1])

            return true;

    }

     // Otherwise, return false

    return false;

}

 // Driver Code

int main()

{

     // Input

    vector<vector<int> > adj = { { 0, 1, 1, 1, 0 },

                                 { 1, 0, 1, 0, 1 },

                                 { 1, 1, 0, 1, 1 },

                                 { 1, 0, 1, 0, 0 } };

    int N = adj.size();

     // Function Call

    if (Hamiltonian_path(adj, N))

        cout << "YES";

    else

        cout << "NO";

     return 0;

}

Java实现

// Java program for the above approach

import java.io.*;

import java.lang.*;

import java.util.*;

 class GFG{

 // Function to check whether there

// exists a Hamiltonian Path or not

static boolean Hamiltonian_path(int adj[][], int N)

{

    boolean dp[][] = new boolean[N][(1 << N)];

     // Set all dp[i][(1 << i)] to

    // true

    for(int i = 0; i < N; i++)

        dp[i][(1 << i)] = true;

     // Iterate over each subset

    // of nodes

    for(int i = 0; i < (1 << N); i++)

    {

        for(int j = 0; j < N; j++)

        {

                         // If the jth nodes is included

            // in the current subset

            if ((i & (1 << j)) != 0)

            {

                 // Find K, neighbour of j

                // also present in the

                // current subset

                for(int k = 0; k < N; k++)

                {

                                         if ((i & (1 << k)) != 0 &&

                         adj[k][j] == 1 && j != k &&

                           dp[k][i ^ (1 << j)])

                    {

                                                 // Update dp[j][i]

                        // to true

                        dp[j][i] = true;

                        break;

                    }

                }

            }

        }

    }

     // Traverse the vertices

    for(int i = 0; i < N; i++)

    {

                 // Hamiltonian Path exists

        if (dp[i][(1 << N) - 1])

            return true;

    }

     // Otherwise, return false

    return false;

}

 // Driver Code

public static void main(String[] args)

{

    int adj[][] = { { 0, 1, 1, 1, 0 },

                    { 1, 0, 1, 0, 1 },

                    { 1, 1, 0, 1, 1 },

                    { 1, 0, 1, 0, 0 } };

    int N = adj.length;

     // Function Call

    if (Hamiltonian_path(adj, N))

        System.out.println("YES");

    else

        System.out.println("NO");

}

}

 // This code is contributed by Kingash

Python3实现

# Python3 program for the above approach

 # Function to check whether there

# exists a Hamiltonian Path or not

def Hamiltonian_path(adj, N):

         dp = [[False for i in range(1 << N)]

                 for j in range(N)]

     # Set all dp[i][(1 << i)] to

    # true

    for i in range(N):

        dp[i][1 << i] = True

     # Iterate over each subset

    # of nodes

    for i in range(1 << N):

        for j in range(N):

             # If the jth nodes is included

            # in the current subset

            if ((i & (1 << j)) != 0):

                 # Find K, neighbour of j

                # also present in the

                # current subset

                for k in range(N):

                    if ((i & (1 << k)) != 0 and

                             adj[k][j] == 1 and

                                     j != k and

                          dp[k][i ^ (1 << j)]):

                                                 # Update dp[j][i]

                        # to true

                        dp[j][i] = True

                        break

         # Traverse the vertices

    for i in range(N):

         # Hamiltonian Path exists

        if (dp[i][(1 << N) - 1]):

            return True

     # Otherwise, return false

    return False

 # Driver Code

adj = [ [ 0, 1, 1, 1, 0 ] ,

        [ 1, 0, 1, 0, 1 ],

        [ 1, 1, 0, 1, 1 ],

        [ 1, 0, 1, 0, 0 ] ]

 N = len(adj)

 if (Hamiltonian_path(adj, N)):

    print("YES")

else:

    print("NO")

 # This code is contributed by maheshwaripiyush9

C#实现

// C# program for the above approach

using System;

 class GFG{

 // Function to check whether there

// exists a Hamiltonian Path or not

static bool Hamiltonian_path(int[,] adj, int N)

{

    bool[,] dp = new bool[N, (1 << N)];

     // Set all dp[i][(1 << i)] to

    // true

    for(int i = 0; i < N; i++)

        dp[i, (1 << i)] = true;

     // Iterate over each subset

    // of nodes

    for(int i = 0; i < (1 << N); i++)

    {

        for(int j = 0; j < N; j++)

        {

                         // If the jth nodes is included

            // in the current subset

            if ((i & (1 << j)) != 0)

            {

                                 // Find K, neighbour of j

                // also present in the

                // current subset

                for(int k = 0; k < N; k++)

                {

                                         if ((i & (1 << k)) != 0 &&

                        adj[k, j] == 1 && j != k &&

                        dp[k, i ^ (1 << j)])

                    {

                         // Update dp[j][i]

                        // to true

                        dp[j, i] = true;

                        break;

                    }

                }

            }

        }

    }

     // Traverse the vertices

    for(int i = 0; i < N; i++)

    {

                 // Hamiltonian Path exists

        if (dp[i, (1 << N) - 1])

            return true;

    }

     // Otherwise, return false

    return false;

}

 // Driver Code

public static void Main(String[] args)

{

    int[,] adj = { { 0, 1, 1, 1, 0 },

                   { 1, 0, 1, 0, 1 },

                   { 1, 1, 0, 1, 1 },

                   { 1, 0, 1, 0, 0 } };

    int N = adj.GetLength(0);

     // Function Call

    if (Hamiltonian_path(adj, N))

        Console.WriteLine("YES");

    else

        Console.WriteLine("NO");

}

}

 // This code is contributed by ukasp

Javascript实现

<script>

 // Javascript program for the above approach

var N = 5;

 // Function to check whether there

// exists a Hamiltonian Path or not

function Hamiltonian_path( adj, N)

{

    var dp = Array.from(Array(N), ()=> Array(1 << N).fill(0));

      // Set all dp[i][(1 << i)] to

    // true

    for (var i = 0; i < N; i++)

        dp[i][(1 << i)] = true;

     // Iterate over each subset

    // of nodes

    for (var i = 0; i < (1 << N); i++) {

         for (var j = 0; j < N; j++) {

             // If the jth nodes is included

            // in the current subset

            if (i & (1 << j)) {

                 // Find K, neighbour of j

                // also present in the

                // current subset

                for (var k = 0; k < N; k++) {

                     if (i & (1 << k)

                        && adj[k][j]

                        && j != k

                        && dp[k][i ^ (1 << j)]) {

                         // Update dp[j][i]

                        // to true

                        dp[j][i] = true;

                        break;

                    }

                }

            }

        }

    }

     // Traverse the vertices

    for (var i = 0; i < N; i++) {

         // Hamiltonian Path exists

        if (dp[i][(1 << N) - 1])

            return true;

    }

     // Otherwise, return false

    return false;

}

 // Driver Code

// Input

var adj = [ [ 0, 1, 1, 1, 0 ],

                             [ 1, 0, 1, 0, 1 ],

                             [ 1, 1, 0, 1, 1 ],

                             [ 1, 0, 1, 0, 0 ] ];

var N = adj.length;

// Function Call

if (Hamiltonian_path(adj, N))

    document.write( "YES");

else

    document.write( "NO");

  </script>

输出：

YES

时间复杂度：O(N * 2^N)空间复杂度：O(N * 2^N)

注：本文由VeryToolz翻译自 Hamiltonian Path ( Using Dynamic Programming ) ，非经特殊声明，文中代码和图片版权归原作者 ramandeep8421所有，本译文的传播和使用请遵循“署名-相同方式共享 4.0 国际 (CC BY-SA 4.0)”协议。