Problema del viajante de comercio (TSP): dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida.
Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema del ciclo hamiltoniano es encontrar si existe un recorrido que visite cada ciudad exactamente una vez. Aquí sabemos que existe el recorrido hamiltoniano (porque el gráfico está completo) y, de hecho, existen muchos recorridos de este tipo, el problema es encontrar un ciclo hamiltoniano de peso mínimo.
Por ejemplo, considere el gráfico que se muestra en la figura. Un recorrido TSP en el gráfico es 1 -> 2 -> 4 -> 3 -> 1. El costo del recorrido es 10 + 25 + 30 + 15 que es 80.
El problema es un famoso problema difícil NP. No existe una solución conocida en tiempo polinomial para este problema.
Salida del gráfico dado:
Peso mínimo Ciclo hamiltoniano: 10 + 25 + 30 + 15 = 80
Enfoque: en esta publicación, se analiza la implementación de una solución simple.
- Considere la ciudad 1 (digamos el Node 0) como el punto inicial y final. Dado que la ruta es cíclica, podemos considerar cualquier punto como punto de partida.
- Comience a atravesar desde la fuente a sus Nodes adyacentes en forma de dfs.
- Calcule el costo de cada recorrido y realice un seguimiento del costo mínimo y continúe actualizando el valor del valor almacenado de costo mínimo.
- Devolver la permutación con coste mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define V 4
// Function to find the minimum weight Hamiltonian Cycle
void tsp(int graph[][V], vector<bool>& v, int currPos,
int n, int count, int cost, int& ans)
{
// If last node is reached and it has a link
// to the starting node i.e the source then
// keep the minimum value out of the total cost
// of traversal and "ans"
// Finally return to check for more possible values
if (count == n && graph[currPos][0]) {
ans = min(ans, cost + graph[currPos][0]);
return;
}
// BACKTRACKING STEP
// Loop to traverse the adjacency list
// of currPos node and increasing the count
// by 1 and cost by graph[currPos][i] value
for (int i = 0; i < n; i++) {
if (!v[i] && graph[currPos][i]) {
// Mark as visited
v[i] = true;
tsp(graph, v, i, n, count + 1,
cost + graph[currPos][i], ans);
// Mark ith node as unvisited
v[i] = false;
}
}
};
// Driver code
int main()
{
// n is the number of nodes i.e. V
int n = 4;
int graph[][V] = {
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 }
};
// Boolean array to check if a node
// has been visited or not
vector<bool> v(n);
for (int i = 0; i < n; i++)
v[i] = false;
// Mark 0th node as visited
v[0] = true;
int ans = INT_MAX;
// Find the minimum weight Hamiltonian Cycle
tsp(graph, v, 0, n, 1, 0, ans);
// ans is the minimum weight Hamiltonian Cycle
cout << ans;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find the minimum weight
// Hamiltonian Cycle
static int tsp(int[][] graph, boolean[] v,
int currPos, int n,
int count, int cost, int ans)
{
// If last node is reached and it has a link
// to the starting node i.e the source then
// keep the minimum value out of the total cost
// of traversal and "ans"
// Finally return to check for more possible values
if (count == n && graph[currPos][0] > 0)
{
ans = Math.min(ans, cost + graph[currPos][0]);
return ans;
}
// BACKTRACKING STEP
// Loop to traverse the adjacency list
// of currPos node and increasing the count
// by 1 and cost by graph[currPos,i] value
for (int i = 0; i < n; i++)
{
if (v[i] == false && graph[currPos][i] > 0)
{
// Mark as visited
v[i] = true;
ans = tsp(graph, v, i, n, count + 1,
cost + graph[currPos][i], ans);
// Mark ith node as unvisited
v[i] = false;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// n is the number of nodes i.e. V
int n = 4;
int[][] graph = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
// Boolean array to check if a node
// has been visited or not
boolean[] v = new boolean[n];
// Mark 0th node as visited
v[0] = true;
int ans = Integer.MAX_VALUE;
// Find the minimum weight Hamiltonian Cycle
ans = tsp(graph, v, 0, n, 1, 0, ans);
// ans is the minimum weight Hamiltonian Cycle
System.out.println(ans);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach V = 4 answer = [] # Function to find the minimum weight # Hamiltonian Cycle def tsp(graph, v, currPos, n, count, cost): # If last node is reached and it has # a link to the starting node i.e # the source then keep the minimum # value out of the total cost of # traversal and "ans" # Finally return to check for # more possible values if (count == n and graph[currPos][0]): answer.append(cost + graph[currPos][0]) return # BACKTRACKING STEP # Loop to traverse the adjacency list # of currPos node and increasing the count # by 1 and cost by graph[currPos][i] value for i in range(n): if (v[i] == False and graph[currPos][i]): # Mark as visited v[i] = True tsp(graph, v, i, n, count + 1, cost + graph[currPos][i]) # Mark ith node as unvisited v[i] = False # Driver code # n is the number of nodes i.e. V if __name__ == '__main__': n = 4 graph= [[ 0, 10, 15, 20 ], [ 10, 0, 35, 25 ], [ 15, 35, 0, 30 ], [ 20, 25, 30, 0 ]] # Boolean array to check if a node # has been visited or not v = [False for i in range(n)] # Mark 0th node as visited v[0] = True # Find the minimum weight Hamiltonian Cycle tsp(graph, v, 0, n, 1, 0) # ans is the minimum weight Hamiltonian Cycle print(min(answer)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the minimum weight Hamiltonian Cycle
static int tsp(int [,]graph, bool []v, int currPos,
int n, int count, int cost, int ans)
{
// If last node is reached and it has a link
// to the starting node i.e the source then
// keep the minimum value out of the total cost
// of traversal and "ans"
// Finally return to check for more possible values
if (count == n && graph[currPos,0] > 0)
{
ans = Math.Min(ans, cost + graph[currPos,0]);
return ans;
}
// BACKTRACKING STEP
// Loop to traverse the adjacency list
// of currPos node and increasing the count
// by 1 and cost by graph[currPos,i] value
for (int i = 0; i < n; i++) {
if (v[i] == false && graph[currPos,i] > 0)
{
// Mark as visited
v[i] = true;
ans = tsp(graph, v, i, n, count + 1,
cost + graph[currPos,i], ans);
// Mark ith node as unvisited
v[i] = false;
}
}
return ans;
}
// Driver code
static void Main()
{
// n is the number of nodes i.e. V
int n = 4;
int [,]graph = {
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 }
};
// Boolean array to check if a node
// has been visited or not
bool[] v = new bool[n];
// Mark 0th node as visited
v[0] = true;
int ans = int.MaxValue;
// Find the minimum weight Hamiltonian Cycle
ans = tsp(graph, v, 0, n, 1, 0, ans);
// ans is the minimum weight Hamiltonian Cycle
Console.Write(ans);
}
}
// This code is contributed by mits
Javascript
<script>
// Javascript implementation of the approach
var V = 4;
var ans = 1000000000;
// Boolean array to check if a node
// has been visited or not
var v = Array(n).fill(false);
// Mark 0th node as visited
v[0] = true;
// Function to find the minimum weight Hamiltonian Cycle
function tsp(graph, currPos, n, count, cost)
{
// If last node is reached and it has a link
// to the starting node i.e the source then
// keep the minimum value out of the total cost
// of traversal and "ans"
// Finally return to check for more possible values
if (count == n && graph[currPos][0]) {
ans = Math.min(ans, cost + graph[currPos][0]);
return;
}
// BACKTRACKING STEP
// Loop to traverse the adjacency list
// of currPos node and increasing the count
// by 1 and cost by graph[currPos][i] value
for (var i = 0; i < n; i++) {
if (!v[i] && graph[currPos][i]) {
// Mark as visited
v[i] = true;
tsp(graph, i, n, count + 1,
cost + graph[currPos][i]);
// Mark ith node as unvisited
v[i] = false;
}
}
};
// Driver code
// n is the number of nodes i.e. V
var n = 4;
var graph = [
[ 0, 10, 15, 20 ],
[ 10, 0, 35, 25 ],
[ 15, 35, 0, 30 ],
[ 20, 25, 30, 0 ]
];
// Find the minimum weight Hamiltonian Cycle
tsp(graph, 0, n, 1, 0);
// ans is the minimum weight Hamiltonian Cycle
document.write( ans);
</script>
Producción:
80
Complejidad de Tiempo: O(N!), En cuanto al primer Node hay N posibilidades y para el segundo Node hay n – 1 posibilidades.
Para N Nodes complejidad temporal = N * (N – 1) * . . . 1 = O(N!)
Espacio auxiliar: O(N)