Ejemplo de conexiones de ciudades
Enfoque de programación dinámica: este enfoque ya se analiza en el Conjunto 1 de este artículo.
Enfoque de rama y límite: el enfoque de rama y límite ya se trata en este artículo .
Array reducida: este enfoque es similar al enfoque Branch and Bound. La diferencia aquí es que el costo del camino y el límite se deciden con base en el método de reducción matricial. Los siguientes son los supuestos para una array reducida:
- Se dice que una fila o columna de la array de adyacencia de costos se reduce si y solo si contiene al menos un elemento cero y todas las entradas restantes en esa fila o columna ≥ 0.
- Si todas las filas y columnas se reducen, entonces solo la array se reduce.
- Duración del recorrido (nuevo) = Duración del recorrido (antiguo) – Valor total reducido.
- Primero reescribimos la array de adyacencia de costos original reemplazando todos los elementos diagonales de 0 a Infinito
La idea básica detrás de la solución del problema es:
- El costo de reducir la array inicialmente es el costo mínimo posible para el problema del viajante de comercio.
- Ahora, en cada paso, debemos decidir el costo mínimo posible si se toma ese camino, es decir, se sigue un camino desde el vértice u hasta el v .
- Podemos hacerlo reemplazando el costo de la u-ésima fila y la v-ésima columna por infinito y luego reduciendo aún más la array y agregando el costo adicional por la reducción y el costo del borde (u, v) con el costo de ruta mínimo ya calculado.
- Una vez que se encuentra al menos un costo de ruta, se usa como límite superior de costo para aplicar el método de bifurcación y límite en las otras rutas y el límite superior se actualiza en consecuencia cuando se encuentra una ruta con un costo más bajo.
Los siguientes son los pasos para implementar el procedimiento anterior:
- Paso 1: cree una clase (Node) que pueda almacenar la array reducida, el costo, el número de ciudad actual, el nivel (número de ciudades visitadas hasta ahora) y la ruta visitada hasta ahora.
- Paso 2: Cree una cola de prioridad para almacenar los Nodes en vivo con el costo mínimo en la parte superior.
- Paso 3: Inicialice el índice de inicio con nivel = 0 y reduzca la array. Calcula el costo de la array dada reduciendo la fila y luego la columna. El costo se calcula de la siguiente manera:
- Reducción de filas: encuentre el valor mínimo para cada fila y guárdelo. Después de encontrar el elemento mínimo de cada fila, réstelo de todos los elementos en esa fila específica.
- Reducción de columna: encuentre el valor mínimo para cada columna y guárdelo. Después de encontrar el elemento mínimo de cada columna, réstelo de todos los elementos en esa columna específica. Ahora la array se reduce.
- Ahora agregue todos los elementos mínimos en la fila y la columna que se encontraron anteriormente para obtener el costo.
- Paso 4: Empuje el elemento con toda la información requerida por Node en la cola de prioridad.
- Paso 5: Ahora, realice las siguientes operaciones hasta que la cola de prioridad se vacíe.
- Extraiga el elemento con el valor mínimo de la cola de prioridad.
- Para cada operación emergente, compruebe si el nivel del Node actual es igual al número de Nodes/ciudades o no.
- En caso afirmativo, imprima la ruta y devuelva el costo mínimo.
- Si la respuesta es No, entonces, para todos y cada uno de los Nodes secundarios del Node actual, calcule el costo usando la fórmula
: Niño->Costo = costo_array_principal + costo_desde_padreAlniño + Costo_Array_reducida_hijo.- El costo de una Array reducida se puede calcular convirtiendo todos los valores de sus filas y columnas a infinito y también haciendo el índice Array[Col][fila] = infinito.
- Luego, vuelva a empujar el Node actual a la cola de prioridad.
- Paso 6: Repita el Paso 5 hasta que no alcancemos el nivel = Número de Nodes – 1.
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Considere las conexiones como se muestra en el gráfico:
Ejemplo de conexiones
Inicialmente, la array de costos se ve así:
fila/columna
no1 2 3 4 1 – 10 15 20 2 10 – 35 25 3 15 35 – 30 4 20 25 30 – Después de la reducción de filas y columnas, la array será:
fila/columna
no1 2 3 4 1 – 0 5 10 2 0 – 25 15 3 0 20 – 15 4 0 5 10 – y los mínimos de fila son 10, 10, 15 y 20.
fila/columna
no1 2 3 4 1 – 0 0 0 2 0 – 20 5 3 0 20 – 5 4 0 5 5 – y los mínimos de las columnas son 0, 0, 5 y 10.
Entonces la reducción de costos de la array es (10 + 10 + 15 + 20 + 5 + 10) = 70Ahora consideremos el movimiento de 1 a 2: Inicialmente después de sustituir la primera fila y la segunda columna hasta el infinito, la array será:
fila/columna
no1 2 3 4 1 – – – – 2 – – 20 5 3 0 – – 5 4 0 – 5 –
- Después de reducir la array, los mínimos de fila serán 5, 0, 0
fila/columna
no1 2 3 4 1 – – – – 2 – – 15 0 3 0 – – 5 4 0 – 5 –
- y el mínimo de la columna será 0, 5, 0
fila/columna
no1 2 3 4 1 – – – – 2 – – 10 0 3 0 – – 5 4 0 – 0 –
- Entonces el costo será 70 + costo (1, 2) + 5 + 5 = 70 + 0 + 5 + 5 = 80.
Continúe este proceso hasta que se complete el recorrido y encuentre el costo mínimo.
A continuación se muestra la estructura del árbol de recursión junto con los límites:
El diagrama de recursión con límites
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// N is the number of cities/Node given
#define N 4
#define INF INT_MAX
// Structure to store all the necessary information
// to form state space tree
struct Node {
// Helps in tracing the path when the answer is found
// stores the edges of the path
// completed till current visited node
vector<pair<int, int> > path;
// Stores the reduced matrix
int reducedMatrix[N][N];
// Stores the lower bound
int cost;
// Stores the current city number
int vertex;
// Stores the total number of cities visited
int level;
};
// Formation of edges and assigning
// all the necessary information for new node
Node* newNode(int parentMatrix[N][N],
vector<pair<int, int> > const& path,
int level, int i, int j)
{
Node* node = new Node;
// Stores parent edges of the state-space tree
node->path = path;
// Skip for the root node
if (level != 0) {
// Add a current edge to the path
node->path.push_back(make_pair(i, j));
}
// Copy data from the parent node to the current node
memcpy(node->reducedMatrix, parentMatrix,
sizeof node->reducedMatrix);
// Change all entries of row i and column j to INF
// skip for the root node
for (int k = 0; level != 0 && k < N; k++) {
// Set outgoing edges for the city i to INF
node->reducedMatrix[i][k] = INF;
// Set incoming edges to city j to INF
node->reducedMatrix[k][j] = INF;
}
// Set (j, 0) to INF
// here start node is 0
node->reducedMatrix[j][0] = INF;
// Set number of cities visited so far
node->level = level;
// Assign current city number
node->vertex = j;
// Return node
return node;
}
// Function to reduce each row so that
// there must be at least one zero in each row
int rowReduction(int reducedMatrix[N][N],
int row[N])
{
// Initialize row array to INF
fill_n(row, N, INF);
// row[i] contains minimum in row i
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reducedMatrix[i][j] < row[i]) {
row[i] = reducedMatrix[i][j];
}
}
}
// Reduce the minimum value from each element
// in each row
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reducedMatrix[i][j] != INF
&& row[i] != INF) {
reducedMatrix[i][j] -= row[i];
}
}
}
return 0;
}
// Function to reduce each column so that
// there must be at least one zero in each column
int columnReduction(int reducedMatrix[N][N],
int col[N])
{
// Initialize all elements of array col with INF
fill_n(col, N, INF);
// col[j] contains minimum in col j
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reducedMatrix[i][j] < col[j]) {
col[j] = reducedMatrix[i][j];
}
}
}
// Reduce the minimum value from each element
// in each column
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (reducedMatrix[i][j] != INF
&& col[j] != INF) {
reducedMatrix[i][j] -= col[j];
}
}
}
return 0;
}
// Function to get the lower bound on the path
// starting at the current minimum node
int calculateCost(int reducedMatrix[N][N])
{
// Initialize cost to 0
int cost = 0;
// Row Reduction
int row[N];
rowReduction(reducedMatrix, row);
// Column Reduction
int col[N];
columnReduction(reducedMatrix, col);
// The total expected cost is
// the sum of all reductions
for (int i = 0; i < N; i++) {
cost += (row[i] != INT_MAX) ? row[i] : 0,
cost += (col[i] != INT_MAX) ? col[i] : 0;
}
return cost;
}
// Function to print list of cities
// visited following least cost
void TSPPAthPrint(vector<pair<int, int> > const& list)
{
for (int i = 0; i < list.size(); i++) {
cout << list[i].first + 1 << " -> "
<< list[i].second + 1 << "\n";
}
}
// Comparison object to be used to order the heap
struct Min_Heap {
bool operator()(const Node* lhs, const Node* rhs) const
{
return lhs->cost > rhs->cost;
}
};
// Function to solve the traveling salesman problem
// using Branch and Bound
int solve(int CostGraphMatrix[N][N])
{
// Create a priority queue to store live nodes
// of the search tree
priority_queue<Node*, vector<Node*>, Min_Heap> pq;
vector<pair<int, int> > v;
// Create a root node and calculate its cost.
// The TSP starts from the first city, i.e., node 0
Node* root = newNode(CostGraphMatrix, v, 0, -1, 0);
// Get the lower bound of the path
// starting at node 0
root->cost = calculateCost(root->reducedMatrix);
// Add root to the list of live nodes
pq.push(root);
// Finds a live node with the least cost,
// adds its children to the list of live nodes,
// and finally deletes it from the list
while (!pq.empty()) {
// Find a live node with
// the least estimated cost
Node* min = pq.top();
// The found node is deleted from
// the list of live nodes
pq.pop();
// i stores the current city number
int i = min->vertex;
// If all cities are visited
if (min->level == N - 1) {
// Return to starting city
min->path.push_back(make_pair(i, 0));
// Print list of cities visited
TSPPAthPrint(min->path);
// Return optimal cost
return min->cost;
}
// Do for each child of min
// (i, j) forms an edge in a space tree
for (int j = 0; j < N; j++) {
if (min->reducedMatrix[i][j] != INF) {
// Create a child node and
// calculate its cost
Node* child
= newNode(min->reducedMatrix, min->path,
min->level + 1, i, j);
child->cost
= min->cost + min->reducedMatrix[i][j]
+ calculateCost(child->reducedMatrix);
// Add a child to the list of live nodes
pq.push(child);
}
}
// Free node as we have already stored edges (i, j)
// in vector. So no need for a parent node while
// printing the solution.
delete min;
}
return 0;
}
// Driver code
int main()
{
int CostGraphMatrix[N][N] = { { INF, 10, 15, 20 },
{ 10, INF, 35, 25 },
{ 15, 35, INF, 30 },
{ 20, 25, 30, INF } };
// Function call
cout << "Total cost is " << solve(CostGraphMatrix);
return 0;
}
Producción
1 -> 3 3 -> 4 4 -> 2 2 -> 1 Total cost is 80
Complejidad temporal: O(2 N * N 2 ) donde N = número de Nodes/ciudades.
Complejidad espacial: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por rupeshsk30 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA