Dadas n ciudades y distancias entre cada par de ciudades, seleccione k ciudades para colocar almacenes (o cajeros automáticos o servidor en la nube) de modo que se minimice la distancia máxima de una ciudad a un almacén (o cajero automático o servidor en la nube).
Por ejemplo, considere las siguientes cuatro ciudades, 0, 1, 2 y 3, y las distancias entre ellas, cómo colocar 2 cajeros automáticos entre estas 4 ciudades para que se minimice la distancia máxima de una ciudad a un cajero automático.
No hay una solución de tiempo polinomial disponible para este problema ya que el problema es un problema NP-Hard conocido. Hay un algoritmo aproximado Greedy de tiempo polinomial, el algoritmo Greedy proporciona una solución que nunca es peor que el doble de la solución óptima. La solución codiciosa funciona solo si las distancias entre ciudades siguen la desigualdad triangular (la distancia entre dos puntos siempre es menor que la suma de las distancias a través de un tercer punto).
El algoritmo codicioso aproximado de 2:
- Elija el primer centro arbitrariamente.
- Elija los centros k-1 restantes utilizando los siguientes criterios.
- Sean c1, c2, c3, … ci los centros ya elegidos. Elegir
- (i+1)’ésimo centro eligiendo la ciudad que está más alejada de ya
- centros seleccionados, es decir, el punto p que tiene el siguiente valor como máximo
- Min[dist(p, c1), dist(p, c2), dist(p, c3), …. distancia (p, ci)]
Ejemplo (k = 3 en el gráfico anterior):
- Deje que el primer vértice elegido arbitrariamente sea 0.
- El siguiente vértice es 1 porque 1 es el vértice más alejado de 0.
- Las ciudades restantes son 2 y 3. Calcula sus distancias desde los centros ya seleccionados (0 y 1). El algoritmo codicioso básicamente calcula los siguientes valores.
- Mínimo de todos distanciados de 2 a centros ya considerados
- Min[dist(2, 0), dist(2, 1)] = Min[7, 8] = 7
- Mínimo de todos distanciados de 3 a centros ya considerados
- Min[dist(3, 0), dist(3, 1)] = Min[6, 5] = 5
- Después de calcular los valores anteriores, se elige la ciudad 2 ya que el valor correspondiente a 2 es el máximo.
Tenga en cuenta que el algoritmo codicioso no ofrece la mejor solución para k = 2, ya que este es solo un algoritmo aproximado con un límite dos veces óptimo.
Prueba de que el algoritmo codicioso anterior es 2 aproximado.
Sea OPT la distancia máxima de una ciudad a un centro en la solución Óptima. Necesitamos mostrar que la distancia máxima obtenida del algoritmo Greedy es 2*OPT.
La demostración se puede hacer por contradicción.
- Suponga que la distancia desde el punto más lejano a todos los centros es > 2·OPT.
- Esto significa que las distancias entre todos los centros también son > 2·OPT.
- Tenemos k + 1 puntos con distancias > 2·OPT entre cada par.
- Cada punto tiene un centro de la solución óptima con distancia <= OPT al mismo.
- Existe un par de puntos con el mismo centro X en la solución óptima (principio del casillero: k centros óptimos, k+1 puntos)
- La distancia entre ellos es como mucho 2·OPT (desigualdad triangular) lo cual es una contradicción.
Implementación:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int maxindex(int* dist, int n)
{
int mi = 0;
for (int i = 0; i < n; i++) {
if (dist[i] > dist[mi])
mi = i;
}
return mi;
}
void selectKcities(int n, int weights[4][4], int k)
{
int* dist = new int[n];
vector<int> centers;
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
}
// index of city having the
// maximum distance to it's
// closest center
int max = 0;
for (int i = 0; i < k; i++) {
centers.push_back(max);
for (int j = 0; j < n; j++) {
// updating the distance
// of the cities to their
// closest centers
dist[j] = min(dist[j], weights[max][j]);
}
// updating the index of the
// city with the maximum
// distance to it's closest center
max = maxindex(dist, n);
}
// Printing the maximum distance
// of a city to a center
// that is our answer
cout << endl << dist[max] << endl;
// Printing the cities that
// were chosen to be made
// centers
for (int i = 0; i < centers.size(); i++) {
cout << centers[i] << " ";
}
cout << endl;
}
// Driver Code
int main()
{
int n = 4;
int weights[4][4] = { { 0, 4, 8, 5 },
{ 4, 0, 10, 7 },
{ 8, 10, 0, 9 },
{ 5, 7, 9, 0 } };
int k = 2;
// Function Call
selectKcities(n, weights, k);
}
// Contributed by Balu Nagar
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int maxindex(int[] dist, int n)
{
int mi = 0;
for(int i = 0; i < n; i++)
{
if (dist[i] > dist[mi])
mi = i;
}
return mi;
}
static void selectKcities(int n, int weights[][],
int k)
{
int[] dist = new int[n];
ArrayList<Integer> centers = new ArrayList<>();
for(int i = 0; i < n; i++)
{
dist[i] = Integer.MAX_VALUE;
}
// Index of city having the
// maximum distance to it's
// closest center
int max = 0;
for(int i = 0; i < k; i++)
{
centers.add(max);
for(int j = 0; j < n; j++)
{
// Updating the distance
// of the cities to their
// closest centers
dist[j] = Math.min(dist[j],
weights[max][j]);
}
// Updating the index of the
// city with the maximum
// distance to it's closest center
max = maxindex(dist, n);
}
// Printing the maximum distance
// of a city to a center
// that is our answer
System.out.println(dist[max]);
// Printing the cities that
// were chosen to be made
// centers
for(int i = 0; i < centers.size(); i++)
{
System.out.print(centers.get(i) + " ");
}
System.out.print("\n");
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
int[][] weights = new int[][]{ { 0, 4, 8, 5 },
{ 4, 0, 10, 7 },
{ 8, 10, 0, 9 },
{ 5, 7, 9, 0 } };
int k = 2;
// Function Call
selectKcities(n, weights, k);
}
}
// This code is contributed by nspatilme
Python3
# Python3 program for the above approach def maxindex(dist, n): mi = 0 for i in range(n): if (dist[i] > dist[mi]): mi = i return mi def selectKcities(n, weights, k): dist = [0]*n centers = [] for i in range(n): dist[i] = 10**9 # index of city having the # maximum distance to it's # closest center max = 0 for i in range(k): centers.append(max) for j in range(n): # updating the distance # of the cities to their # closest centers dist[j] = min(dist[j], weights[max][j]) # updating the index of the # city with the maximum # distance to it's closest center max = maxindex(dist, n) # Printing the maximum distance # of a city to a center # that is our answer # print() print(dist[max]) # Printing the cities that # were chosen to be made # centers for i in centers: print(i, end = " ") # Driver Code if __name__ == '__main__': n = 4 weights = [ [ 0, 4, 8, 5 ], [ 4, 0, 10, 7 ], [ 8, 10, 0, 9 ], [ 5, 7, 9, 0 ] ] k = 2 # Function Call selectKcities(n, weights, k) # This code is contributed by mohit kumar 29.
C#
using System;
using System.Collections.Generic;
public class GFG{
static int maxindex(int[] dist, int n)
{
int mi = 0;
for(int i = 0; i < n; i++)
{
if (dist[i] > dist[mi])
mi = i;
}
return mi;
}
static void selectKcities(int n, int[,] weights,
int k)
{
int[] dist = new int[n];
List<int> centers = new List<int>();
for(int i = 0; i < n; i++)
{
dist[i] = Int32.MaxValue;
}
// Index of city having the
// maximum distance to it's
// closest center
int max = 0;
for(int i = 0; i < k; i++)
{
centers.Add(max);
for(int j = 0; j < n; j++)
{
// Updating the distance
// of the cities to their
// closest centers
dist[j] = Math.Min(dist[j],
weights[max,j]);
}
// Updating the index of the
// city with the maximum
// distance to it's closest center
max = maxindex(dist, n);
}
// Printing the maximum distance
// of a city to a center
// that is our answer
Console.WriteLine(dist[max]);
// Printing the cities that
// were chosen to be made
// centers
for(int i = 0; i < centers.Count; i++)
{
Console.Write(centers[i] + " ");
}
Console.Write("\n");
}
// Driver Code
static public void Main (){
int n = 4;
int[,] weights = new int[,]{ { 0, 4, 8, 5 },
{ 4, 0, 10, 7 },
{ 8, 10, 0, 9 },
{ 5, 7, 9, 0 } };
int k = 2;
// Function Call
selectKcities(n, weights, k);
}
}
// This code is contributed by avanitrachhadiya2155.
Javascript
<script>
// Javascript program for the above approach
function maxindex(dist,n)
{
let mi = 0;
for(let i = 0; i < n; i++)
{
if (dist[i] > dist[mi])
mi = i;
}
return mi;
}
function selectKcities(n,weights,k)
{
let dist = new Array(n);
let centers = [];
for(let i = 0; i < n; i++)
{
dist[i] = Number.MAX_VALUE;
}
// Index of city having the
// maximum distance to it's
// closest center
let max = 0;
for(let i = 0; i < k; i++)
{
centers.push(max);
for(let j = 0; j < n; j++)
{
// Updating the distance
// of the cities to their
// closest centers
dist[j] = Math.min(dist[j],
weights[max][j]);
}
// Updating the index of the
// city with the maximum
// distance to it's closest center
max = maxindex(dist, n);
}
// Printing the maximum distance
// of a city to a center
// that is our answer
document.write(dist[max]+"<br>");
// Printing the cities that
// were chosen to be made
// centers
for(let i = 0; i < centers.length; i++)
{
document.write(centers[i] + " ");
}
document.write("<br>");
}
// Driver Code
let n = 4;
let weights = [ [ 0, 4, 8, 5 ],
[ 4, 0, 10, 7 ],
[ 8, 10, 0, 9 ],
[ 5, 7, 9, 0 ] ]
let k = 2
selectKcities(n, weights, k)
// This code is contributed by unknown2108
</script>
Producción
5 0 2
Complejidad de tiempo: O(n*k), ya que estamos usando bucles anidados para recorrer n*k veces.
Espacio auxiliar: O(k), ya que estamos usando espacio extra para el centro del arreglo.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA