Establecer problema de portada | Conjunto 1 (algoritmo aproximado codicioso)

Dado un universo U de n elementos, una colección de subconjuntos de U digamos S = {S ₁ , S ₂ …,S _m } donde cada subconjunto S _i tiene un costo asociado. Encuentre una subcolección de costo mínimo de S que cubra todos los elementos de U.

Ejemplo:

   U = {1,2,3,4,5}
   S = {S1,S2,S3}
   
   S1 = {4,1,3},    Cost(S1) = 5
   S2 = {2,5},      Cost(S2) = 10
   S3 = {1,4,3,2},  Cost(S3) = 3

Output: Minimum cost of set cover is 13 and 
        set cover is {S2, S3}

There are two possible set covers {S1, S2} with cost 15
and {S2, S3} with cost 13.

¿Por qué es útil?
Fue uno de los problemas NP-completos de Karp, demostrado ser así en 1972. Otras aplicaciones: cobertura de bordes, cobertura de vértices
Ejemplo interesante: IBM encuentra virus informáticos (wikipedia)
Elementos: 5000 virus conocidos Conjuntos:
9000 substrings de 20 o más bytes consecutivos de virus, no encontrados en código ‘bueno’.
Se encontró una cubierta fija de 180. Basta con buscar estas 180 substrings para verificar la existencia de virus informáticos conocidos.

Otro ejemplo: considere que General Motors necesita comprar una cierta cantidad de suministros variados y hay proveedores que ofrecen varias ofertas para diferentes combinaciones de materiales (Proveedor A: 2 toneladas de acero + 500 tejas por $x; Proveedor B: 1 tonelada de acero + 2000 fichas por $y; etc.). Puede usar la cobertura de conjuntos para encontrar la mejor manera de obtener todos los materiales y minimizar el costo
. Fuente: http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Set Cover is NP-Hard:
No hay una solución de tiempo polinomial disponible para este problema, ya que se trata de un problema NP-Hard conocido. Hay un algoritmo aproximado Greedy de tiempo polinomial, el algoritmo greedy proporciona un algoritmo aproximado Logn.

2-Algoritmo codicioso aproximado:
Sea U el universo de elementos, {S ₁ , S ₂ , … S _m } sea una colección de subconjuntos de U y Costo(S ₁ ), C(S ₂ ), … Costo(S _m ) ser costos de subconjuntos.

1) Let I represents set of elements included so far.  Initialize I = {}

2) Do following while I is not same as U.
    a) Find the set Si in {S1, S2, ... Sm} whose cost effectiveness is 
       smallest, i.e., the ratio of cost C(Si) and number of newly added 
       elements is minimum. 
       Basically we pick the set for which following value is minimum.
           Cost(Si) / |Si - I|
    b) Add elements of above picked Si to I, i.e.,  I = I U Si

Ejemplo:
Consideremos el ejemplo anterior para comprender el algoritmo codicioso.

Primera iteración:
I = {}

El costo por elemento nuevo para S ₁ = Costo (S ₁ )/|S ₁ – I| = 5/3

El costo por elemento nuevo para S ₂ = Costo (S ₂ )/|S ₂ – I| = 10/2

El costo por elemento nuevo para S ₃ = Costo (S ₃ )/|S ₃ – I| = 3/4

Dado que S ₃ tiene un valor mínimo, se agrega S ₃ , I se convierte en {1,4,3,2}.

Segunda Iteración:
I = {1,4,3,2}

El costo por elemento nuevo para S ₁ = Costo (S ₁ )/|S ₁ – I| = 5/0
Tenga en cuenta que S ₁ no agrega ningún elemento nuevo a I.

El costo por elemento nuevo para S ₂ = Costo (S ₂ )/|S ₂ – I| = 10/1
Tenga en cuenta que S ₂ suma solo 5 a I.

El algoritmo codicioso proporciona la solución óptima para el ejemplo anterior, pero es posible que no proporcione la solución óptima todo el tiempo. Considere el siguiente ejemplo.

S1 = {1, 2}
S2 = {2, 3, 4, 5}
S3 = {6, 7, 8, 9, 10, 11, 12, 13}
S4 = {1, 3, 5, 7, 9, 11, 13}
S5 = {2, 4, 6, 8, 10, 12, 13}

Let the cost of every set be same.

The greedy algorithm produces result as {S3, S2, S1}

The optimal solution is {S4, S5} 

Prueba de que el algoritmo codicioso anterior es Logn aproximado.
Sea OPT el costo de la solución óptima. Digamos que los elementos (k-1) están cubiertos antes de una iteración del algoritmo codicioso anterior. El costo del k’ésimo elemento <= OPT / (n-k+1) (Tenga en cuenta que el costo de un elemento se evalúa por el costo de su conjunto dividido por el número de elementos agregados por su conjunto). ¿Cómo obtuvimos este resultado? Dado que el k’ésimo elemento aún no está cubierto, hay un Si _que no ha sido cubierto antes del paso actual del algoritmo codicioso y está allí en OPT. _{Dado que el algoritmo codicioso elige el S i} más rentable, el costo por elemento en el conjunto seleccionado debe ser menor que OPT dividido por los elementos restantes. Por lo tanto, costo del k’ésimo elemento <= OPT/|UI| (Tenga en cuenta que la interfaz de usuario es un conjunto de elementos aún no cubiertos en Greedy Algorithm). El valor de |UI| es n – (k-1) que es n-k+1.

Cost of Greedy Algorithm = Sum of costs of n elements 
                        [putting k = 1, 2..n in above formula]
                         <= (OPT/n + OPT(n-1) + ... + OPT/n) 
                         <= OPT(1 + 1/2 + ...... 1/n)
                        [Since 1 + 1/2 + .. 1/n ≈ Log n]
                         <= OPT * Logn

Fuente:
http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf

Este artículo es una contribución de Harshit . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.