En una entrada anterior planteé el siguiente problema:
Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto
de vectores linealmente independientes $B =
\{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho
n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a
$P$?
Expliqué y ejemplifiqué una posible estrategia consistente en el método exhaustivo, es decir, comprobar todos los posibles vértices. Concluí la entrada con la observación de que el número de vértices crece de manera exponencial con la dimensión y esto supone un problema de coste computacional en dimensiones grandes.
En esta entrada vamos a trabajar otra posible estrategia, basada en el algoritmo de Babai, desarrollado por el matemático húngaro László Babai.
El fundamento detrás del procedimiento es relativamente sencillo.
Si $P\in\mathcal{F}$ entonces $P$ se puede escribir como combinación lineal de la base $B$:
$$P = \sum_{i=1}^{n}{a_i·\vec{b}_i}$$
Lo que hacemos es redondear al entero los coeficientes $0 \leq a_i \leq 1$ de la combinación lineal:
$$z_i = redondear(a_i)$$
Entonces, el vértice del n-paralelepípedo más próximo a $P$ viene dado por:
$$V = \sum_{i=1}^{n}{z_i·\vec{b}_i}$$
Ejemplo: Hagamos este método con el mismo ejemplo que utilizamos en el método exhaustivo, en $\mathbb{R}^2$.
$B=\{(30,
3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos
hallar el vértice del paralelogramo más cercano a $Q$.
Primero calcularemos la combinación lineal de la base $B$ que da el punto $Q$:
$$\vec{a} = B^{-1} · \overrightarrow{OQ} =\begin{pmatrix}30 & 5\\3 & 0\end{pmatrix}^{-1} · \begin{pmatrix}25.5 \\ 2.5\end{pmatrix} \simeq \begin{pmatrix}0.8333333333333333 \\ 0.10000000000000053\end{pmatrix}$$
Ahora redondeamos los coeficientes obtenidos:
$$\vec{z} = \begin{pmatrix}1 \\ 0\end{pmatrix}$$
Y calculamos a qué vértice corresponde dicha combinación lineal:
$$\overrightarrow{OV} = B · \vec{z} = \begin{pmatrix}30 & 5\\3 & 0\end{pmatrix} · \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}30 \\ 3\end{pmatrix}$$
Es decir, el vértice más cercano al punto $Q$ es (30, 3). (Coincide con el obtenido por el método exhaustivo)
Los cálculos del ejemplo han sido realizados con wxMaxima:
Desde un punto de vista geométrico e informal podríamos decir que el procedimiento anterior es equivalente a dividir con "hiperplanos medianeros" el n-paralelepípedo y seleccionar el vértice del "trozo" en el que queda el punto.
El algoritmo de Babai rebaja considerablemente el coste computacional, dado que no necesita recorrer todos los vértices del n-paralelepípedo y se basa en operaciones bastante rápidas desde el punto de vista del cálculo computacional.
Sin embargo, el algoritmo de Babai presenta un gran problema: solo en determinadas condiciones la solución que devuelve es la correcta.
Veamos esto con un ejemplo. Seguimos utilizando la misma base que en el ejemplo anterior, pero cambiamos el punto a "aproximar" (encontrar el vértice más cercano) por $R=(30, 2.7)$.
Los cálculos del algoritmo devuelven el vértice $(35, 3)$ como el más cercano al punto $R$.
Sin embargo, esto no es cierto. El vértice más cercano es claramente el $(30, 3)$.
Puede observarse en la representación gráfica que, tras trazar las medianas, el punto cae en el "trozo" del vértice $(35, 3)$ y por eso es la respuesta que devuelve el algoritmo de Babai. Pero no es el vértice más cercano.
Llegados a este punto lo razonable es descartar por completo este algoritmo porque ni tan siquiera devuelve la solución correcta.
Sin embargo, el algoritmo sí funciona con fiabilidad cuando la base es ortogonal (o "cerca" de ser ortogonal).
¿Y esto tiene alguna utilidad práctica? Habrá que esperar a las siguientes entradas para averiguarlo.
