Ruta hamiltoniana (usando programación dinámica)

Dada una array de adyacencia adj[][] de un grafo no dirigido que consta de N vértices, la tarea es encontrar si el grafo contiene un camino hamiltoniano o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Un camino hamiltoniano se define como el camino en un gráfico dirigido o no dirigido que visita todos y cada uno de los vértices del gráfico exactamente una vez.

Ejemplos:

Entrada: adj[][] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}}
Salida:
Explicación:
existe una ruta hamiltoniana para el gráfico dado, como se muestra en la imagen a continuación:

Entrada: adj[][] = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}}
Salida : No

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de N vértices. Para cada permutación, verifique si es una ruta hamiltoniana válida verificando si hay un borde entre vértices adyacentes o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica y enmascaramiento de bits , que se basa en las siguientes observaciones:

  • La idea es tal que para todo subconjunto S de vértices, comprobar si existe un camino hamiltoniano en el subconjunto S que termina en el vértice v donde v € S .
  • Si v tiene un vecino u , donde u € S – {v} , por lo tanto, existe un camino hamiltoniano que termina en el vértice u .
  • El problema se puede resolver generalizando el subconjunto de vértices y el vértice final del camino hamiltoniano.

Siga los pasos a continuación para resolver el problema:

  • Inicialice una array booleana dp[][] en dimensión N*2 N donde dp[j ][i] representa si existe o no un camino en el subconjunto representado por la máscara i que visita todos y cada uno de los vértices en i una vez y termina en el vértice j .
  • Para el caso base, actualice dp[i][1 << i] = true , for i in range [0, N – 1]
  • Iterar sobre el rango [1, 2 N – 1] usando la variable i y realizar los siguientes pasos:
    • Todos los vértices con bits establecidos en la máscara i, se incluyen en el subconjunto.
    • Itere sobre el rango [1, N] usando la variable j que representará el vértice final de la ruta hamiltoniana de la máscara de subconjunto actual i y realice los siguientes pasos:
  • Itere sobre el rango usando la variable i y si el valor de dp[i][2 N – 1] es verdadero , entonces existe un camino hamiltoniano que termina en el vértice i . Por lo tanto, imprima “Sí” . De lo contrario, escriba “No” .

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

YES

 

Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(N * 2 N )

Publicación traducida automáticamente

Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *