Te doy una lista de vectores de bits de ancho . Su objetivo es devolver dos vectores de bits de la lista que no tienen 1 en común, o bien informar que no existe dicho par.
Por ejemplo, si le doy entonces la única solución es . Alternativamente, la entrada no tiene solución. Y cualquier lista que contenga el vector de bits todo cero y otro elemento tiene una solución trivial .
Aquí hay un ejemplo un poco más difícil, sin solución (cada fila es un vector de bits, los cuadrados negros son 1s y los cuadrados blancos son 0s):
■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □
¿Cuán eficientemente se pueden encontrar dos vectores de bits no superpuestos o demostrar que no existen?
El algoritmo ingenuo, donde solo compara cada par posible, es . ¿Es posible hacerlo mejor?
algorithms
search-algorithms
Craig Gidney
fuente
fuente
Respuestas:
Calentamiento: vectores de bits aleatorios
Como calentamiento, podemos comenzar con el caso en el que cada bitvector se elige de manera uniforme al azar. Entonces resulta que el problema se puede resolver en (más precisamente, el 1.6 se puede reemplazar con lg 3 ).O ( n1.6min ( k , lgn ) ) 1.6 lg3
Consideraremos la siguiente variante de dos conjuntos del problema:
Dados los conjuntos de vectores de bits, determine dónde existe un par no superpuestoS, T⊆ { 0 , 1 }k .s ∈ S, t ∈ T
La técnica básica para resolver esto es dividir y conquistar. Aquí hay un algoritmo de tiempo ( n 1.6 k ) que usa divide y vencerás:O ( n1.6k )
Dividir y T según la posición del primer bit. En otras palabras, forma S 0 = { s ∈ S : s 0 = 0 } , S 1 = { s ∈ S : s 0 = 1 } , T 0 = { t ∈ T : t 0 = 0 } , TS T S0 0= { s ∈ S: s0 0= 0 } S1= { s ∈ S: s0 0=1} T0 0= { t ∈ T: t0 0= 0 } .T1= { t ∈ T: t0 0= 1 }
Ahora busque recursivamente un par no superpuesto de , de S 0 , T 1 y de TS0 0, T0 0 S0 0, T1 . Si alguna llamada recursiva encuentra un par no superpuesto, envíelo, de lo contrario, saldrá "No existe par superpuesto".T1, S0 0
Como todos los vectores de bits se eligen al azar, podemos esperar y | T b | ≈ | T | / 2 . Por lo tanto, tenemos tres llamadas recursivas y hemos reducido el tamaño del problema en un factor de dos (ambos conjuntos se reducen en tamaño en un factor de dos). Después de que lg min ( | S | , | T | ) se divide, uno de los dos conjuntos se reduce al tamaño 1, y el problema se puede resolver en tiempo lineal. Obtenemos una relación de recurrencia a lo largo de las líneas deEl | SsiEl | ≈ | SEl | / 2 El | TsiEl | ≈ | TEl | / 2 lgmin(|S|,|T|) , cuya solución es T ( n ) = O ( n 1.6 k ) . Teniendo en cuenta el tiempo de ejecución con mayor precisión en el caso de dos conjuntos, vemos que el tiempo de ejecución es O ( min ( | S | , | T | ) 0.6 max ( | S | , | TT(n)=3T(n/2)+O(nk) T(n)=O(n1.6k) .O(min(|S|,|T|)0.6max(|S|,|T|)k)
Esto se puede mejorar aún más, observando que si , entonces la probabilidad de que exista un par no superpuesto es exponencialmente pequeña. En particular, si x , y son dos vectores al azar, la probabilidad de que es que son no superpuestas ( 3 / 4 ) k . Si | S | = | T | = n , hay n 2 de estos pares, por lo que por un enlace de unión, la probabilidad de que exista un par no superpuesto es como máximo n 2 ( 3k≥2.5lgn+100 x,y (3/4)k |S|=|T|=n n2 . Cuando k ≥ 2.5 lg n +n2(3/4)k , esto es ≤ 1 / 2 100 . Entonces, como un paso de preprocesamiento, si k ≥ 2.5 lg n + 100 , entonces podemos devolver inmediatamente "No existe un par no superpuesto" (la probabilidad de que esto sea incorrecto es insignificantemente pequeño), de lo contrario, ejecutamos el algoritmo anterior.k≥2.5lgn+100 ≤1/2100 k≥2.5lgn+100
Por lo tanto, alcanzamos un tiempo de ejecución de (u O ( min ( | S | , | T | ) 0.6 max ( | S | , | T | ) min ( k , lg n ) ) para la variante de dos conjuntos propuesta anteriormente), para el caso especial donde los vectores de bits se eligen uniformemente al azar.O(n1.6min(k,lgn)) O(min(|S|,|T|)0.6max(|S|,|T|)min(k,lgn))
Por supuesto, este no es un análisis del peor de los casos. Los vectores de bits aleatorios son considerablemente más fáciles que el peor de los casos, pero tratémoslo como un calentamiento, para obtener algunas ideas que quizás podamos aplicar al caso general.
Lecciones del calentamiento
Podemos aprender algunas lecciones del calentamiento anterior. Primero, dividir y conquistar (dividir en una posición de bit) parece útil. En segundo lugar, desea dividir en una posición de bit con tantos en esa posición como sea posible; cuanto más 0 's hay, menos reducción en el tamaño subproblema se obtiene.1 0
En tercer lugar, esto sugiere que el problema se vuelve más difícil a medida que la densidad de hace más pequeña: si hay muy pocos 1 entre los vectores de bits (en su mayoría son 0 ), el problema parece bastante difícil, ya que cada división se reduce el tamaño de los subproblemas un poco. Por lo tanto, defina la densidad Δ como la fracción de bits que son 1 (es decir, de todos los n k bits), y la densidad de la posición de bit i como la fracción de los vectores de bits que son 11 1 0 Δ 1 nk i 1 en la posición .i
Manejo de muy baja densidad
Como siguiente paso, podríamos preguntarnos qué sucede si la densidad es extremadamente pequeña. Resulta que si la densidad en cada posición de bit es menor que , estamos garantizados de que existe un par no superpuesto: existe un argumento de existencia (no constructivo) que muestra que debe existir algún par no superpuesto. Esto no nos ayuda a encontrarlo, pero al menos sabemos que existe.1/k−−√
¿Por qué es este el caso? Digamos que un par de bitvectors está cubierto por la posición de bit i si x i = y i = 1 . Tenga en cuenta que cada par de vectores de bits superpuestos debe estar cubierto por alguna posición de bits. Ahora, si fijamos una posición de bit particular i , el número de pares que puede cubrir esa posición de bit es como máximo ( n Δ ( i ) ) 2 < n 2 / k . Resumiendo todo kx,y i xi=yi=1 i (nΔ(i))2<n2/k k de las posiciones de bit, encontramos que el número total de pares que están cubiertos por alguna posición de bit es . Esto significa que debe existir algún par que no esté cubierto por ninguna posición de bit, lo que implica que este par no se superpone. Entonces, si la densidad es suficientemente baja en cada posición de bit, entonces seguramente existe un par no superpuesto.<n2
Sin embargo, no puedo identificar un algoritmo rápido para encontrar un par que no se superponga, en este régimen, aunque se garantiza que existe uno. No veo de inmediato ninguna técnica que produzca un tiempo de ejecución que tenga una dependencia subcuadrática de . Entonces, este es un buen caso especial para enfocarse, si desea pasar un tiempo pensando en este problema.n
Hacia un algoritmo de caso general
En el caso general, una heurística natural parece ser: elija la posición de bit con el mayor número de 1 (es decir, con la densidad más alta) y divídala. En otras palabras:i 1
Encuentre una posición de bit que maximice Δ ( i ) .i Δ(i)
Dividir y T según la posición del bit i . En otras palabras, forma S 0 = { s ∈ S : s i = 0 } , S 1 = { s ∈ S : s i = 1 } , T 0 = { t ∈ T : t i = 0 } , T 1 = { t ∈ T :S T i S0={s∈S:si=0} S1={s∈S:si=1} T0={t∈T:ti=0} T1={t∈T:ti=1} .
Ahora busque recursivamente un par no superpuesto de , de S 0 , T 1 y de T 1 , S 0 . Si alguna llamada recursiva encuentra un par no superpuesto, envíelo, de lo contrario, saldrá "No existe par superpuesto".S0,T0 S0,T1 T1,S0
El desafío es analizar su desempeño en el peor de los casos.
Supongamos que, como paso previo al procesamiento, primero calculamos la densidad de cada posición de bit. Además, si para cadai, suponga que el paso de preprocesamiento genera "Existe un par superpuesto" (me doy cuenta de que esto no muestra un ejemplo de un par superpuesto, pero dejemos eso a un lado como un desafío separado). Todo esto se puede hacer enO(nk)Δ(i)<1/k−−√ i O(nk) time. The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.
What will the running time of this procedure be? I'm not sure, but here are a few observations that might help. Each level of recursion reduces the problem size by aboutn/k−−√ bitvectors (e.g., from n bitvectors to n−n/k−−√ bitvectors). Therefore, the recursion can only go about k−−√ levels deep. However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than 3k√ leaves), so I'm not sure what running time this should lead to.
fuente
Faster solution whenn≈k , using matrix multiplication
Suppose thatn=k . Our goal is to do better than an O(n2k)=O(n3) running time.
We can think of the bitvectors and bit positions as nodes in a graph. There is an edge between a bitvector node and a bit position node when the bitvector has a 1 in that position. The resulting graph is bipartite (with the bitvector-representing nodes on one side and the bitposition-representing nodes on the other), and hasn+k=2n nodes.
Given the adjacency matrixM of a graph, we can tell if there is a two-hop path between two vertices by squaring M and checking if the resulting matrix has an "edge" between those two vertices (i.e. the edge's entry in the squared matrix is non-zero). For our purposes, a zero entry in the squared adjacency matrix corresponds to a non-overlapping pair of bitvectors (i.e. a solution). A lack of any zeroes means there's no solution.
Squaring an n x n matrix can be done inO(nω) time, where ω is known to be under 2.373 and conjectured to be 2 .
So the algorithm is:
The most expensive step is squaring the adjacency matrix. Ifn=k then the overall algorithm takes O((n+k)ω)=O(nω) time, which is better than the naive O(n3) time.
This solution is also faster whenk grows not-too-much-slower and not-too-much-faster than n . As long as k∈Ω(nω−2) and k∈O(n2ω−1) , then (n+k)ω is better than n2k . For w≈2.373 that translates to n0.731≤k≤n1.373 (asymptotically). If w limits to 2, then the bounds widen towards nϵ≤k≤n2−ϵ .
fuente
Esto es equivalente a encontrar un vector de bits que es un subconjunto del complemento de otro vector; es decir, sus 1 ocurren solo donde 0 ocurren en el otro.
Si k (o el número de 1) es pequeño, puede obtenerO ( n 2k) tiempo simplemente generando todos los subconjuntos del complemento de cada bitvector y colocándolos en un trie (usando el seguimiento). Si se encuentra un vector de bits en el trie (podemos verificar cada uno antes de la inserción del complemento-subconjunto), entonces tenemos un par no superpuesto.
Si el número de 1 o 0 está limitado a un número aún menor que k, entonces el exponente puede ser reemplazado por eso. La indexación de subconjuntos puede estar en cada vector o en su complemento, siempre que el sondeo utilice lo contrario.
There's also a scheme for superset-finding in a trie that only stores each vector only once, but does bit-skipping during probes for what I believe is similar aggregate complexity; ie it haso(k) insertion but o(2k) searches.
fuente
Represent the bit vectors as ann×k matrix M . Take i and j between 1 and n .
Complexity
Using naive multiplication, this requiresO(n2k) arithmetic operations. If n=k , it takes O(n2.37) operations using the utterly impractical Coppersmith-Winograd algorithm, or O(n2.8) using the Strassen algorithm. If k=O(n0.302) , then the problem may be solved using n2+o(1) operations.
fuente