Encontrar la sub-familia más pequeña de subconjuntos necesaria para formar un nuevo subconjunto

Question

TL/DR

Tengo un universo $U$ de los elementos $u_i$ y una familia $F$ de los subconjuntos de a $U$ (llamar $P_j$ ⊆ $U$).

Dada esta familia de subconjuntos, me gustaría encontrar la sub-familia $C$ ⊆ $F$ de subconjuntos que se puede producir un nuevo subconjunto $P_{new}$ $u_i$ sumando (o restando) como algunos subconjuntos $P_j$ como sea posible.

Que es lo mejor que puedo hacer. Esperemos que un ejemplo más claro:

---

Ejemplo

Por ejemplo, si empezamos con la siguiente familia de subconjuntos:

$$ \begin{align} F = \{&P_1 = \{a\},\ P_2 = \{b\},\ ...,\ P_{16} = \{p\}, \\ &P_{17} = \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p\}, \\ &P_{18} = \{a, b, c, d, e\}, \\ &P_{19} = \{g, h, i\} \,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \}&\\ \end{align} $$

Cuando se solicita calcular $\{a, b, c, d, e, f, g, h, i\}$, lo más sencillo es calcular:

$$\{a, b, c, d, e, f, g, h, i\} = \{a\} + \{b\} + \{c\} +\ ...\ + \{h\} + \{i\}$$

Esto no es óptimo, aunque (requiere 8 adiciones). Por ejemplo, yo sé que podría producir rápidamente el conjunto si yo en su lugar tomó ventaja de mis previamente calculada conjuntos (usando 2 adiciones):

$$ \begin{align} P_{new} &= \{a, b, c, d, e, f, g, h, i\}\\ &= \{a, b, c, d, e\} + \{f\} + \{g, h, i\} \\ &= P_{18} + P_{6} + P_{19} \\ \mathord{\therefore}\ C ⊆ F &= \{ P_{6}, P_{18}, P_{19} \} \\ \end{align} $$

---

Ejemplo 2

Lo que es aún más complejo es que (si es posible) yo quiero saber cuando impliquen la sustracción puede ser óptimo:

$$\{e, f, g, h, i\} = \{e\} + \{f\} + \{g, h, i\}$$

Esta es la mejor solución utilizando sólo la suma (2 operaciones), Pero podría haber llegado aún más rápido con 1 resta:

$$\{e, f, g, h, i\} = \{a, b, c, d, e, f, g, h, i\} - \{a, b, c, d\}$$

---

¿Por qué necesito este

Cada subconjunto $P_j$ tiene un valor de $p_j = f(P_j)$ que puede ser calculada. La función de $f(P_j)$ es aditivo. Por lo $p_{\{1,2\}} = p_{\{1\}} + p_{\{2\}}$

Cuando inicio mi solicitud, yo sólo empieza por calcular el valor de $p_i$ por cada elemento de a $l_i$ por su propia cuenta. Por ejemplo:

$$ \begin{align} P_1 = \{a\} ,&\ \ p_1 = f(P_1) = 5 \\ P_2 = \{b\} ,&\ \ p_2 = f(P_2) = 20 \\ P_3 = \{c\} ,&\ \ p_3 = f(P_3) = 8 \\ ...\ & \end{align} $$

Entonces tengo que comenzar a atender las solicitudes de los diferentes subconjuntos. Por ejemplo:

$$ \begin{align} P_{18} &= \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p\}\ &f(P_{18}) &= 400 \\ P_{19} &= \{b, c, d\}\ &f(P_{19}) &= 43\\ P_{20} &= \{g, h, i\}\ &f(P_{20}) &= 30 \\ ...& \end{align} $$

Mi objetivo es ser capaz de procesar su solicitud lo más rápido posible. Para principios de peticiones, yo inevitablemente tiene que gastar un montón de tiempo sumando $p_j$ valores. Pero dado que estos valores son aditivos, sé que debe haber maneras más rápidas para procesar las solicitudes por tomar ventaja de los conjuntos para los cuales ya he calculado $p_j$.

Si $P_{21} = \{b, c, d, g, h, i\}$ es requerido, no quiero desperdiciar valiosos recursos de recuperar el 6 valores de $p_{2}$$p_{7}$, y la incorporación de estos valores en 5 las operaciones de larga duración, cuando yo podría haber hecho una sola operación $p_{21} = p_{19}+p_{20}$.

---

No se establece-teoría?

Este hecho podría ser una mejor opción para el álgebra lineal, si formulada de la siguiente manera:

Si tengo las siguientes ecuaciones y valores:

$$ \begin{align} P_{1} &= a, P_{2} = b,\ ...,\ P_{8} = g &f(P_{1}) &= p_{1},\ ...\\ P_{9} &= a + b + c + d &f(P_{9}) &= p_{9} \\ P_{10} &= d + e + f + g &f(P_{10}) &= p_{10} \\ \end{align} $$

Y quiero calcular

$$ \begin{align} P_{11} &= a + b + c + d + e + f + g &f(P_{11}) ? \\ \end{align} $$

Quiero ser capaz de descubrir que la solución más rápida proviene de

$$ \begin{align} P_{11} &= P_{9} + P_{10} - P_{4} \\ P_{11} &= (a + b + c + d) + (d + e + f + g) - (d) \\ &= (a + b + c + 2d + e + f + g) - (d) \\ &= a + b + c + d + e + f + g\ \checkmark\\ \mathord{\therefore}\ p_{11} &= p_{9} + p_{10} - p_{4} \\ \end{align} $$

Está empezando a parecer sospechosamente a un np problema difícil para mí :( Si nadie puede venir para arriba con una manera elegante de resolver el problema, también me gustaría aceptar una forma más elegante de la formulación del problema (tal vez en términos de un problema bien conocido), o un límite en la complejidad.

Answer 1

OK, primero que vamos a trabajar en una representación formal de su problema.

• Deje $m$ ser el número de la sets.
• Deje $n$ el número de elementos en el universo
• Deje $U=\{u_i\}_{i=1}^{n}$ ser el universo
• Deje $S$ ser el conjunto de todos los subconjuntos de a $U$
• Deje $\{P_j\}_{j=1}^{m}$ ser el ya calculada conjuntos
• Deje $A$ $n \times m$ matriz
• Deje $A_{ij} = \cases{\begin{array}[c]\\1,\,u_i \in P_j \\0,\,u_i \notin P_j \end{array}}$
• Deje $c(x) = \cases{\begin{array}[c]\\0,\,x=0\\1,\, x \ne 0 \\ \end{array}}$
• Deje $v(s): S \rightarrow \mathbb{R}^n$ ser una función que crea una representación vectorial de un subconjunto de a $U$. Definir $v(s) = \left[\begin{array}[c]\\v(s)_1\\v(s)_2\\ \,\,\,\,\vdots \\ v(s)_n \end{array}\right]$ $v(s)_i = \cases{\begin{array}[c]\\1, \, u_i \in s\\0, \, u_i \notin s \end{array} }$
• Deje $f$ ser la función, como se define en la pregunta original.

La primera cosa a tener en cuenta es que desde $f$ es lineal, y tenemos un nuevo conjunto de entrada $P^*$, si podemos encontrar un vector $q \in \mathbb{R}^m$ tal que $Aq = v(P^*)$,$f(P^*) = \sum_{i=1}^n q_i \cdot f(P_i)$. Además, tenga en cuenta que el costo de la computación $f(P^*)$ uso de la fórmula anterior es $C(q) = \sum_{i=1}^m c(q_i) $.

Con todo eso, tenemos nuestro problema de optimización: $$ \DeclareMathOperator*{\argmin}{argmin} \begin{align} \\ q^*(P^*)&=\argmin_q C(q) \text{ such that }Aq=v(P^*) \end{align} $$

$C$ es constante a trozos función, lo que significa que tiene discontinuidades tanto en valor y en derivados. Además, si alguno de los existentes subconjuntos no se utilizan en el óptimo de cálculo, se tendrá un discontinua derivada en el punto óptimo. El vector de entrada $q$ puede tomar cualquier valor en $\mathbb{R}^m$. La restricción es lineal y la igualdad de restricción.

Así, a primera vista, este es un nonsmooth problema de optimización lineal con restricciones de igualdad.

---

También hay otra forma de pensar acerca de la función objetivo. Supongamos que tenemos una suposición acerca de que las variables son no-cero en la solución óptima. Representar a este por un vector con $m$ elementos, cada uno o cero, que vamos a llamar a $b$. Podemos determinar si este conjunto de subconjuntos para su uso en el cálculo es factible, y si es así, lo que los pesos apropiados son? Podemos. Simplemente quite las columnas de a $A$ y las entradas en $q$ correspondiente a la $0$ entradas $b$, y resolver el problema resultante en un sentido de los mínimos cuadrados. Si la solución es factible, tendrá un cero residual. De lo contrario, tendrá distinto de cero residuos. Si utilizamos $b$ como variable de entrada en lugar de $q$ nos encontramos con una mejor función objetivo, con más restricción en las entradas disponibles (cada entrada de b puede ser 1 o 0):

$$ \begin{align} \\ D(b) &= 1^Tb \end{align} $$

Ahora sólo tenemos que especificar un conjunto de restricciones que hacen que la función objetivo de trabajo. En primer lugar, hemos de especificar los mínimos cuadrados problema que debemos resolver en el interior de la restricción de la función: $$ \begin{align} \\ \bar{A}\bar{q} &= v(P^*) \end{align} $$

La solución de mínimos cuadrados es : $$ \begin{align} \\ \hat{q} &= \argmin_{\bar{q}} (\bar{A}\bar{q} - v(P^*))^T (\bar{A}\bar{q} - v(P^*)) \\ \hat{q} &= \left(\bar{A}^T \bar{A} \right)^{-1} \bar{A}^T v(P^*) \\ \end{align} $$

Y nuestra limitación es $ (\bar{A}\hat{q} - v(P^*))^T(\bar{A}\hat{q} - v(P^*)) = 0 $. En esto, es importante tener en cuenta que el $\bar{A}$ $\hat{q}$ son funciones de la variable de entrada $b$.

Así, bajo esta formulación del problema, tenemos un lineal binario de un problema de programación con un no lineal de la igualdad de restricción.

---

Ambos de estos tipos de problemas son NP completo. Hay, sin embargo, los algoritmos que puede ayudar a resolver estos tipos de problemas, o al menos algo cercano a una solución óptima, en una cantidad razonable de tiempo de cálculo. Para la primera formulación de un problema, puede buscar en genética/evolutivo global de los optimizadores de, o directa/patrón de los algoritmos de búsqueda. Estos son algo común, y se incluye, por ejemplo, en MATLAB de la optimización de la caja de herramientas. La segunda sección de enfoque es bastante exótico problema, y probablemente no debería ser el foco de su búsqueda de un optimizador, aunque creo que hay algunos trabajos académicos que podría ayudar a resolver esa formulación.

Answer 2

No una respuesta, pero no me permite hacer un comentario, y tengo una pregunta, así que aquí va:

En las partes de su problema hacen que suene como el punto de su programa para calcular el $f(P)$ para un usuario de entrada de $P \subseteq U$. También decir que $f$ es lineal, y que usted calcula el $f$ para cada elemento definido en el inicio. Supongamos que el número de elementos en el universo es $u$ y el número de elementos en la que solicita el subconjunto es $r$. A continuación, la búsqueda de tiempo para el valor de la función de cada elemento en la solicitud es $\approx O(1)$ si se utiliza una tabla hash, o $O(\log_2u)$ mediante el uso de un árbol de búsqueda binario. Por lo tanto el tiempo total para la solicitud de los valores de la función es $O(r\log_2u)$ o $O(r)$. La adición tiempo sería $O(r)$. Por lo general usted está buscando en un tiempo de ejecución de $O(r)$ o $O(r\log_2u)$. Lo que parece estar bien. La única manera de que usted tiene un problema que no tiene completamente el problema es irresoluble si no es la llamada a la función que es caro, pero la operación de adición. Si ese es el caso, entonces necesitamos más información sobre el costo de las propiedades de la operación de suma para responder a la pregunta.

Por ejemplo, suponiendo que $f(P1)$ se calcula, es computing $nf(P1)$ más caro que simplemente ir a buscar a $f(P1)$? Es que el cálculo lineal en $n$? Cuadrática? Cómo sobre el cálculo de los costos de $f(P1)-f(P2)$ vs $f(P1)+f(P3)$ donde $P2$ $P3$ tienen el mismo tamaño. Línea de fondo, a menos que yo estoy totalmente de malinterpretar la pregunta, necesitamos más información para responder la pregunta.

Answer 3

Vamos a reformular el problema en términos de álgebra lineal. Deja que el universo $U$ ser finito, y considere el espacio vectorial $V=\mathbb{R}^U$ de los vectores $\mathbf{x}=(x_u)_{u\in U}$. Asociamos a cada subconjunto $S\subseteq U$ un vector $\mathbf{x}_S\in V$ por $$\mathbf{x}_u=\cases{1&if $u\en S$\\0&if $u\noen S$}$$ Entonces, dado $F\subseteq\mathcal{P}(U)$, el problema de escritura de algún subconjunto $P\subseteq U$ como una suma (resp. suma y resta) de los elementos de $F$ es exactamente el problema de encontrar una solución que contiene sólo $0$'s y $1$'s (resp. $0$s, $1$'s y $-1$'s) de $$\mathbf{A}\mathbf{y}=\mathbf{x}_P$$ donde $\mathbf{A}$ es la matriz con columnas $\mathbf{x}_f$$f\in F$. Por lo tanto el problema se reduce a encontrar algunos de celosía particular de los puntos de un subespacio lineal de $\mathbb{R}^F$. Por desgracia conozco muy poco sobre el tema, y no puedo ayudarle más, pero estoy seguro de que alguien más lo hará. La buena suerte.

Addendum: Observe que una vez que se han encontrado todos los celosía puntos que usted puede encontrar los correspondientes a la cantidad mínima necesaria de las operaciones mediante la minimización de la $\|\mathbf{y}\|_1=\sum_{f\in F}|y_f|$.