Problema de los centros K | Conjunto 1 (algoritmo aproximado codicioso)

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. 

kcenters1

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: 

  1. Elija el primer centro arbitrariamente. 
  2. 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)] 

greedyAlgo

Ejemplo (k = 3 en el gráfico anterior):

  1. Deje que el primer vértice elegido arbitrariamente sea 0. 
  2. El siguiente vértice es 1 porque 1 es el vértice más alejado de 0. 
  3. 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. 

  1. Suponga que la distancia desde el punto más lejano a todos los centros es > 2·OPT. 
  2. Esto significa que las distancias entre todos los centros también son > 2·OPT. 
  3. Tenemos k + 1 puntos con distancias > 2·OPT entre cada par. 
  4. Cada punto tiene un centro de la solución óptima con distancia <= OPT al mismo. 
  1. Existe un par de puntos con el mismo centro X en la solución óptima (principio del casillero: k centros óptimos, k+1 puntos) 
  2. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *