Hallazgo N elementos que se incluyen en tantos conjuntos como sea posible

Question

Decir que tengo 20 juegos, que contiene una cantidad variable de elementos. Cómo se podría ir sobre la búsqueda de los 10 elementos que cubren el mayor número de conjuntos?

Imagínate que yo podría buscar tres términos a la vez en la Wikipedia. Sé que todos los datos en la Wikipedia. Cada página es un conjunto de palabras. Quiero búsqueda de los tres términos que volverá tantos resultados como sea posible.

En primer lugar, parece que la búsqueda de la más frecuente de las palabras es la mejor solución - este es probablemente muy bien para solo tres términos a la vez, pero imagino que de diez mil términos, de muy pequeños conjuntos. Los dos más frecuente de las palabras tienden a ocurrir juntos en nuestros sets (e.g, Feliz Cumpleaños) - estamos tratando de encontrar algo como la mejor representación ortogonal de todos estos conjuntos, con N dimensiones.

No he estudiado la teoría de conjuntos, sin embargo, y aunque estoy leyendo a través de Suppes' Axiomático que la Teoría de conjuntos en la actualidad, estoy seguro de que no he formulado este problema en lenguaje matemático preciso, y me disculpo por ello. Estoy dispuesto a aclarar el problema.

Estoy en busca de un algoritmo, o un modelo matemático que podría implementar un algoritmo. Tal vez esta pregunta es mejor postula a StackOverflow!

Tenga en cuenta que el resultado debe ser optimizado, pero no necesariamente perfecto.

Answer 1

El problema es conocido como el Máximo de Cobertura Problema. Es NP-duro. Por lo tanto no podemos resolverlo en el polinomio de tiempo (≈eficiente) a menos $P=NP$. Un algoritmo voraz da un $1-1/e$ aproximación y no es una coincidencia de la dureza de aproximación resultado [Hochbaum '97, Feige '98].

El problema está estrechamente relacionado con el Conjunto de la Cubierta Problema: tenemos un conjunto de elementos de la $X$ y una familia de subconjuntos de a $\cal S$ $X$ (cada una de las $S\in \cal S$ es un subconjunto de a $X$); nuestro objetivo es elegir el menor número posible de conjuntos en $\cal S$ que cubren $X$. Este problema es NP-duro [Karp' 72]. Hay un $O(\log n)$ algoritmo de aproximación para él y una coincidencia de la dureza de aproximación resultado [Lund, Yannakakis '94, Feige '98].

Answer 2

Una posible formulación matemática es el siguiente: Vamos a $X = \{x_1, \dots, x_N\}$ ser el conjunto de elementos bajo consideración y $A = \{A_1, \dots, A_M\}$ ser la colección de conjuntos. Definir un bipartito grafo con nodos $X \cup A$ y el conjunto de borde $E = \{ (x_i, \, A_j) | x_i \in A_j\}$. Si entiendo correctamente, usted está interesado en la búsqueda de un subconjunto $X_0 \subset X$ con cardinalidad tal que el conjunto de $A_j \in A$ que están conectados a $X_0$ tiene cardinalidad máxima.

Un enfoque posible: el Uso de un algoritmo voraz.

Inicializar mediante el establecimiento $A^{(0)} = A$. Para $k = 1, 2, \dots$ definir una secuencia de $x^{(k)}$ como sigue:

1. Dado $A^{(k-1)}$, elija $x^{(k)}$ de manera tal que el conjunto $\{A_j \in A^{(k-1)}| x^{(k)} \in A_j \}$ es máxima.

2. Set $A^{(k)} = A^{(k-1)} \setminus \{ A_j | x^{(k)} \in A_j \}$ y el ir a 1.

Puede haber algoritmos de la teoría de grafos que hacer un mejor trabajo.