Encuentra las esquinas

¿Cómo se pueden encontrar las esquinas $d+1$ del cubo unitario en $\mathbb{R}^d$ más cercano a un punto $x$ en el cubo?
Utilice la métrica L1, de modo que en 4d | $x$ - 0000 | = $\sum {x_i}$ , | $x$ - 0001 | = $x_3 + x_2 + x_1 + (1 - x_0)$
( $x_0$ a la derecha) y así sucesivamente.

Para una formulación alternativa, primero voltee $x_i$ > 1/2 y ordene, de modo que $0 \leq x_{d-1} \leq \dots\ x_1 \leq x_0 \leq$ 1/2; por simetría, un algoritmo para este caso puede hacer cualquier $x$ en el cubo.
Defina $c \equiv 1 - 2x$ , $1\geq c_{d-1} \geq \dots\ c_1 \geq c_0 \geq 0$ .
Entonces queremos el $d+1$esquinas con más pequeño $c \cdot$ esquina.

En 4d, por ejemplo, con $x_i$ disminuyendo 1/2 .. 0 como arriba, las 5 esquinas más cercanas pueden ser

    0 0 0 0
    0 0 0 1
    0 0 1 0

    0 1 0 0  or  0 0 1 1
                 0 1 * *

    1 0 0 0
 or 0 1 0 1

Sin embargo, en 5d, 6d ... los árboles de las esquinas crecientes parecen (para mí) cada vez más desordenados.
La heurística para el aproximado más cercano estaría bien.

Tiempo $O(d^3\log d)$

lema: Corregir cualquier . Luego hay un conjunto S que contiene d + 1 esquinas de { 0 , 1 } d que están más cerca de x y de tal manera que S está conectado (lo que significa que el subgráfico del hipercubo inducido por S está conectado).$x\in[0,1]^d$$S$$d+1$$\{0,1\}^d$$x$$S$$S$

Prueba. Consideremos en primer lugar el caso de que no tiene coordenadas iguales a 1 / 2 .$x$$1/2$

Dada cualquier esquina en S , voltear una coordenada a j de a no aumentará la distancia de a a x si | a j - x j | ≥ 1 / 2 . $a$$S$$a_j$$a$$a$$x$$|a_j - x_j| \ge 1/2$

Considere dos esquinas en S que difieren en al menos una coordenada j , y suponga WLOG que a j = 0 y b j = 1 . Si x j < 1 / 2 tras dar la vuelta b j en b da otro punto en S (debido a que disminuye la distancia desde b a x ). O, si x j > 1 / 2 tras dar la vuelta un $a,b$$S$$j$$a_j=0$$b_j=1$$x_j<1/2$$b_j$$b$$S$$b$$x$$x_j>1/2$$a_j$en da un punto en S . La repetición de este proceso para cada uno diferente de coordenadas en una y b da una vía de conexión a y b dentro de S .$a$$S$$a$$b$$a$$b$$S$

Si tiene coordenadas iguales a 1 / 2 , a continuación, en la elección de S , lazos de ruptura entre los puntos equidistantes, dando prioridad a los que tienen más coordenadas cero. Entonces el mismo argumento funcionará. QED$x$$1/2$$S$

Por el lema, se puede utilizar un algoritmo de Dijkstra-como para encontrar . Comience con una esquina más cercana a x ( una con un j = 0 si x j ≤ 1 / 2 ). A continuación, añadir varias veces para S una esquina que está más cerca de x entre los que se encuentran adyacentes a un cierto punto en S . Deténgase cuando se hayan agregado d + 1 puntos. $S$$x$$a$$a_j = 0$$x_j \le 1/2$$S$$x$$S$$d+1$

Ingenuamente (usando un montón mínimo para encontrar el siguiente punto más cercano a en cada iteración), supongo que hay iteraciones d + 1 , y cada iteración requiere trabajo O ( d 2 ) para generar los vecinos d del nodo agregado (cada de los cuales tiene representación de tamaño d ), dando tiempo de ejecución O ( d 3 log d ) .$x$$d+1$$O(d^2)$$d$$d$$O(d^3\log d)$

Tiempo $O(d^2\log d)$

Representar cada esquina implícitamente como un par ( h , d $a$$(h, d)$ , donde es un hash del conjunto de índices i de tal manera que un i = 1 , y d es la distancia desde x a una . Desde una esquina dada a , los pares para todas las esquinas vecinas se pueden generar en el tiempo O ( d ) (total). Esto reduce el tiempo de ejecución a O ( d 2 log d ) .$h$$i$$a_i=1$$d$$x$$a$$a$$O(d)$$O(d^2\log d)$

¿Más rápido?

Para facilitar la discusión, reformulemos el problema de la siguiente manera. Dada una secuencia de números no negativos $d$ , encuentre lossubconjuntos de costo mínimo d + 1 de los números, donde el costo de un subconjunto es la suma de los números que contiene. $y_1 \le y_2 \le \cdots \le y_d$$d+1$ (Para ver la conexión con el problema anterior, tomar y i = | x i -1 / 2 | ; entonces cada subconjuntoYde la y i 's corresponde a una esquinade una ( y ) del hipercubo, donde a i ( y ) es 1 if ( x i$y_i = |x_i - 1/2|$$Y$$y_i$$a(y)$$a_i(y)$ y y i ∈ Y ) o ( x i > 1 / 2 y y i ∉ Y ); y el costo de Y es la distancia desde x a una ( y ) ).$x_i \le 1/2$$y_i\in Y$$x_i>1/2$$y_i\not\in Y$$Y$$x$$a(y)$

Aquí hay una idea general para un algoritmo más rápido. Quizás alguien pueda descubrir cómo hacer que funcione.

Defina un gráfico dirigido implícito donde cada nodo sea un subconjunto de los y i 's. El nodo de inicio es el conjunto vacío. Representar los nodos implícitamente como pares$Y$$y_i$ donde h es el hash del subconjunto y c es el costo. Para cada subconjunto Y , defina los subconjuntos vecinos de alguna manera para que (i) si Y → Y ' sea ​​un borde dirigido, entonces el costo ( Y ' ) ≥ costo ( Y ) , y (ii) para cualquier subconjunto Y ' , hay un borde dirigido$(h, c)$$h$$c$$Y$$Y\rightarrow Y'$$(Y') \ge$$(Y)$$Y'$ de algún subconjunto Y donde costo ( Y ) ≤ costo ( Y ' ) . Luego ejecute Dijkstra's en este gráfico implícito comenzando en el nodo de inicio.$Y\rightarrow Y'$$Y$$(Y) \le$$(Y')$

Elija los bordes (de alguna manera) para que (i) y (ii) se mantengan, y la suma de los grados de los nodos más baratos es O ( d ) . (Esto siempre es posible, por ejemplo, tomar las aristas como las de un árbol de ruta más corta enraizada al inicio). Pero, ¿se puede definir un gráfico sin el conocimiento a priori del árbol de ruta más corta? Si es así, esto podría conducir a un algoritmo de tiempo O ( d log d ) (?).$d+1$$O(d)$$O(d\log d)$

Es equivalente a pedir, entre un conjunto de no ponderados negativamente, los subconjuntos d + 1 de peso total mínimo. Uno puede formar todos los subconjuntos de los elementos en un árbol, en el que el padre de un subconjunto se forma eliminando su elemento más pesado (con lazos rotos de manera arbitraria pero consistente); Las soluciones d + 1 formarán un subárbol de este árbol conectado en su raíz (el conjunto vacío).$d$$d+1$$d+1$

Por lo tanto, uno puede buscar en este árbol los elementos pequeños mediante una forma del algoritmo de Dijkstra en el que mantenemos una cola prioritaria de subconjuntos y los eliminamos en orden de prioridad. Comenzamos con el primer elemento seleccionado como el conjunto vacío. Luego, en cada paso, mantenemos como una invariante del algoritmo una cola de prioridad que contiene el siguiente elemento secundario no seleccionado para cada subconjunto ya seleccionado. Cuando seleccionamos un conjunto S , lo eliminamos de la cola de prioridad y agregamos a la cola de prioridad dos nuevos subconjuntos: su primer hijo (el conjunto formado al agregar el siguiente elemento más pesado que el elemento más pesado en S ) y su próximo hermano (el conjunto se formó eliminando el elemento más pesado en S y agregando el mismo siguiente elemento más pesado).$d+1$$S$$S$$S$

Después de ordenar los elementos por sus pesos, es sencillo representar cada conjunto implícitamente (como su elemento más pesado más un puntero a su conjunto primario), mantener el peso total de cada conjunto y encontrar el primer hijo y el próximo hermano que necesita el algoritmo en tiempo constante por juego. Por lo tanto, el tiempo total está dominado por la clasificación inicial y por las operaciones de cola prioritarias, que toman el tiempo total .$O(d\log d)$

Incluso esto puede mejorarse si los artículos ya están ordenados por su peso. Vea la relación "primer hijo" y "próximo hermano" del algoritmo anterior como los hijos izquierdo y derecho en un árbol binario de subconjuntos. Este árbol está ordenado en montón (el peso total aumenta de padre a hijo) para que podamos aplicar un algoritmo para encontrar los nodos de peso mínimo en un árbol binario ordenado en montón [GN Frederickson. Un algoritmo óptimo para la selección en un montón mínimo. Information and Computation, 104: 197–214, 1993]. El tiempo total, después del paso de clasificación, es O ( d ) .$d+1$$O(d)$

En la práctica, los pesos a menudo se distribuyen de manera uniforme, aproximadamente ~ 1 2 3 Entonces, una heurística simple es comenzar con:$\dots$

$\qquad$los bits individuales, p. ej. 10000000 01000000 … 00000001$d$$\dots$
$\qquad$ combinaciones de bits bajos 00000011 00000101 00000110 00000111$\lceil ln_2 d\rceil$
$\qquad$combinaciones de pocos bits del siguiente $\lceil ln_2 d\rceil$ , p. ej. 00001001 00001010 00001100.
El mejor de estos candidatos funciona bastante bien en la práctica, al menos para los pequeños d .$d+1$$d$