Problema del viajante de comercio (TSP): dado un conjunto de ciudades y distancias 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 del lado derecho. Un recorrido TSP en el gráfico es 1-2-4-3-1. El costo del tour es 10+25+30+15 que son 80.
El problema es un famoso problema NP-difícil. No existe una solución conocida en tiempo polinomial para este problema.
Ejemplos:
Output of Given Graph: minimum weight Hamiltonian Cycle : 10 + 25 + 30 + 15 := 80
En esta publicación, se analiza la implementación de una solución simple.
- Considere la ciudad 1 como el punto inicial y final. Dado que la ruta es cíclica, podemos considerar cualquier punto como punto de partida.
- ¡Genera todo (n-1)! permutaciones de ciudades.
- Calcule el costo de cada permutación y realice un seguimiento de la permutación de costo mínimo.
- Devolver la permutación con coste mínimo.
A continuación se muestra la implementación de la idea anterior.
C++
// CPP program to implement traveling salesman
// problem using naive approach.
#include <bits/stdc++.h>
using namespace std;
#define V 4
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do {
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];
// update minimum
min_path = min(min_path, current_pathweight);
} while (
next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
// Driver Code
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;
}
Java
// Java program to implement
// traveling salesman problem
// using naive approach.
import java.util.*;
class GFG{
static int V = 4;
// implementation of traveling
// Salesman Problem
static int travllingSalesmanProblem(int graph[][],
int s)
{
// store all vertex apart
// from source vertex
ArrayList<Integer> vertex =
new ArrayList<Integer>();
for (int i = 0; i < V; i++)
if (i != s)
vertex.add(i);
// store minimum weight
// Hamiltonian Cycle.
int min_path = Integer.MAX_VALUE;
do
{
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0;
i < vertex.size(); i++)
{
current_pathweight +=
graph[k][vertex.get(i)];
k = vertex.get(i);
}
current_pathweight += graph[k][s];
// update minimum
min_path = Math.min(min_path,
current_pathweight);
} while (findNextPermutation(vertex));
return min_path;
}
// Function to swap the data
// present in the left and right indices
public static ArrayList<Integer> swap(
ArrayList<Integer> data,
int left, int right)
{
// Swap the data
int temp = data.get(left);
data.set(left, data.get(right));
data.set(right, temp);
// Return the updated array
return data;
}
// Function to reverse the sub-array
// starting from left to the right
// both inclusive
public static ArrayList<Integer> reverse(
ArrayList<Integer> data,
int left, int right)
{
// Reverse the sub-array
while (left < right)
{
int temp = data.get(left);
data.set(left++,
data.get(right));
data.set(right--, temp);
}
// Return the updated array
return data;
}
// Function to find the next permutation
// of the given integer array
public static boolean findNextPermutation(
ArrayList<Integer> data)
{
// If the given dataset is empty
// or contains only one element
// next_permutation is not possible
if (data.size() <= 1)
return false;
int last = data.size() - 2;
// find the longest non-increasing
// suffix and find the pivot
while (last >= 0)
{
if (data.get(last) <
data.get(last + 1))
{
break;
}
last--;
}
// If there is no increasing pair
// there is no higher order permutation
if (last < 0)
return false;
int nextGreater = data.size() - 1;
// Find the rightmost successor
// to the pivot
for (int i = data.size() - 1;
i > last; i--) {
if (data.get(i) >
data.get(last))
{
nextGreater = i;
break;
}
}
// Swap the successor and
// the pivot
data = swap(data,
nextGreater, last);
// Reverse the suffix
data = reverse(data, last + 1,
data.size() - 1);
// Return true as the
// next_permutation is done
return true;
}
// Driver Code
public static void main(String args[])
{
// matrix representation of graph
int graph[][] = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
int s = 0;
System.out.println(
travllingSalesmanProblem(graph, s));
}
}
// This code is contributed by adityapande88
Python3
# Python3 program to implement traveling salesman # problem using naive approach. from sys import maxsize from itertools import permutations V = 4 # implementation of traveling Salesman Problem def travellingSalesmanProblem(graph, s): # store all vertex apart from source vertex vertex = [] for i in range(V): if i != s: vertex.append(i) # store minimum weight Hamiltonian Cycle min_path = maxsize next_permutation=permutations(vertex) for i in next_permutation: # store current Path weight(cost) current_pathweight = 0 # compute current path weight k = s for j in i: current_pathweight += graph[k][j] k = j current_pathweight += graph[k][s] # update minimum min_path = min(min_path, current_pathweight) return min_path # Driver Code if __name__ == "__main__": # matrix representation of graph graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] s = 0 print(travellingSalesmanProblem(graph, s))
C#
// C# program to implement
// traveling salesman problem
// using naive approach.
using System;
using System.Collections.Generic;
class GFG {
static int V = 4;
// implementation of traveling Salesman Problem
static int travllingSalesmanProblem(int[, ] graph,
int s)
{
List<int> vertex = new List<int>();
for (int i = 0; i < V; i++)
if (i != s)
vertex.Add(i);
// store minimum weight
// Hamiltonian Cycle.
int min_path = Int32.MaxValue;
do {
// store current Path weight(cost)
int current_pathweight = 0;
int k = s;
// compute current path weight
for (int i = 0; i < vertex.Count; i++) {
current_pathweight += graph[k, vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k, s];
// update minimum
min_path
= Math.Min(min_path, current_pathweight);
} while (findNextPermutation(vertex));
return min_path;
}
// Function to swap the data resent in the left and
// right indices
public static List<int> swap(List<int> data, int left,
int right)
{
// Swap the data
int temp = data[left];
data[left] = data[right];
data[right] = temp;
// Return the updated array
return data;
}
// Function to reverse the sub-array starting from left
// to the right both inclusive
public static List<int> reverse(List<int> data,
int left, int right)
{
// Reverse the sub-array
while (left < right) {
int temp = data[left];
data[left++] = data[right];
data[right--] = temp;
}
// Return the updated array
return data;
}
// Function to find the next permutation of the given
// integer array
public static bool findNextPermutation(List<int> data)
{
// If the given dataset is empty
// or contains only one element
// next_permutation is not possible
if (data.Count <= 1)
return false;
int last = data.Count - 2;
// find the longest non-increasing
// suffix and find the pivot
while (last >= 0) {
if (data[last] < data[last + 1])
break;
last--;
}
// If there is no increasing pair
// there is no higher order permutation
if (last < 0)
return false;
int nextGreater = data.Count - 1;
// Find the rightmost successor
// to the pivot
for (int i = data.Count - 1; i > last; i--) {
if (data[i] > data[last]) {
nextGreater = i;
break;
}
}
// Swap the successor and
// the pivot
data = swap(data, nextGreater, last);
// Reverse the suffix
data = reverse(data, last + 1, data.Count - 1);
// Return true as the
// next_permutation is done
return true;
}
// Driver Code
public static void Main(string[] args)
{
// matrix representation of graph
int[, ] graph
= new int[4, 4] { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 45 } };
int s = 0;
Console.WriteLine(
travllingSalesmanProblem(graph, s));
}
}
// This code is contributed by Tapesh(tapeshdua420)
Producción
80
Publicación traducida automáticamente
Artículo escrito por Nishant_Singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA