Dada una array 2D , arr[][] que denota una lista de coordenadas de N vértices en un espacio 2D que ya está ordenado por coordenadas x e y, la tarea es encontrar la distancia mínima de un recorrido que comienza desde el extremo izquierdo vértice, y va estrictamente a la derecha, y luego, al llegar al vértice más a la derecha, el recorrido va estrictamente de derecha a izquierda hasta el vértice inicial.
Ejemplos:
Entrada: N = 7, arr[][] = {{0, 6}, {1 0}, {2 3}, {5 4}, {6 1}, {7 5}, {8 2}}
Salida : 25.582
Explicación:
El recorrido TSP : 0-3-5-6-4-1-2-0 no es un recorrido TSP bitónico porque aunque el recorrido inicialmente va de izquierda a derecha (0-3-5-6) y luego vuelve de derecha a la izquierda (6-4-1), luego da otro paso de izquierda a derecha (1-2) y luego de derecha a izquierda (2-0).
El recorrido: 0-2-3-5-6-4-1-0 es un recorrido TSP Bitonic válido porque se puede descomponer en dos recorridos: 0-2-3-5-6 que va de izquierda a derecha y 6 -4-1-0 que retrocede de derecha a izquierda.Entrada: N = 3, arr[][] = {{1, 1}, {2, 3}, {3, 1}}
Salida: 6,47
Enfoque: El problema anterior se puede resolver usando Programación Dinámica . En aras de la comprensión, el problema se puede convertir en dos personas. Ambos deben comenzar desde el punto más a la izquierda al mismo tiempo. Camine por dos caminos diferentes y finalmente llegue al punto más a la derecha, excepto el punto de partida y el punto final.
- Cada punto pasa a ser pasado por una persona. Aquí, dp[i][j] representa la distancia que camina la primera persona hacia i y la segunda hacia j .
- En la solución, dp[i][j] significa que se ha caminado de 1 a max(i, j) , y las posiciones actuales de las dos personas son i y j respectivamente, y la distancia que deben recorrer.
- También se puede inferir que dp[i][j] es igual a dp[j][i] , por lo que de ahora en adelante se estipula que i siempre es mayor que j es decir i>j en el estado.
- De esta manera, no importa esa persona, el siguiente paso solo puede ir a i+1, i+2,… estos puntos.
- Entonces, el estado dp[i][j] solo se puede transferir a dp[i+1][j] o dp[i][i+1].
Siga los pasos a continuación para resolver el problema:
- Cree una array 2D , dp[][] de tamaño N*N .
- Iterar la última fila de la tabla, dp , y actualizar dp[N-1][i] a la suma de distancia(N-1, N) y distancia(i, N) , donde distancia(x, y) representa la Distancia euclidiana entre los puntos x e y de arr .
- Cree una función recursiva findTour (i, j) para llenar todas las demás celdas
- Actualice dp[i][j] al mínimo de findTour(i+1, j)+distance(i, i+1) y findTour(i+1, i)+distance(j, i+1) .
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;
// Size of the array a[]
const int mxN = 1005;
// Structure to store the x and
// y coordinates of a point
struct Coordinates {
double x, y;
} a[mxN];
// Declare a 2-D dp array
float dp[mxN][mxN];
// Function to calculate the
// distance between two points
// in a Euclidian plane
float distance(int i, int j)
{
// Return the distance
return sqrt(
(a[i].x - a[j].x) * (a[i].x - a[j].x)
+ (a[i].y - a[j].y) * (a[i].y - a[j].y));
}
// Utility recursive function to find
// the bitonic tour distance
float findTourDistance(int i, int j)
{
// Memoization
if (dp[i][j] > 0)
return dp[i][j];
// Update dp[i][j]
dp[i][j] = min(
findTourDistance(i + 1, j) + distance(i, i + 1),
findTourDistance(i + 1, i) + distance(j, i + 1));
return dp[i][j];
}
// Function to find the
// bitonic tour distance
void bitonicTSP(int N)
{
// Initialize the dp array
memset(dp, 0, sizeof(dp));
// Base Case
for (int j = 1; j < N - 1; j++)
dp[N - 1][j] = distance(N - 1, N)
+ distance(j, N);
// Print the answer
printf("%.2f\n", findTourDistance(1, 1));
}
// Driver Code
int main()
{
// Given Input
int N = 3;
a[1].x = 1, a[1].y = 1;
a[2].x = 2, a[2].y = 3;
a[3].x = 3, a[3].y = 1;
// Function Call
bitonicTSP(N);
}
6.47
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )