Es, de hecho, un problema de difícil solución. Pero no en la dimensión 2.
A partir de una determinada base (un conjunto de independiente de vectores) de un número entero de celosía, usted está tratando de encontrar un menor distinto de cero), vector de la red. Este es el más corto de vector problema (SVP), y de dimensiones más grandes, de hecho, es NP-duro.
El problema es que usted podría conseguir un corto vector de un extraño entero combinación de los vectores de la base, como la forma en que interactúan unos con otros es muy difícil de predecir (especialmente en las grandes dimensiones).
En dimensiones mayores que dos, hay, de hecho, no hay mejor forma conocida de generar un corto vector de enumerar todos los posibles vectores en una esfera. Hay maneras de evitar que se genere demasiadas vectores, pero la complejidad es aún exponencial. El algoritmo LLL es un polinomio de aproximación que explota la idea básica de intentar crear más corto vectores de trabajo en sólo dos vectores en un tiempo (una generalización de la 2-dimensional caso), pero sólo le da un relativly corto vector (mejor prueba le da un factor de $2^{O(n)}$ el tamaño :().
En la dimensión dos , sin embargo, el algoritmo LLL (Llamado algoritmo de Lagrange, a veces erróneamente atribuido a Gauss, una generalización del algoritmo de euclides.) le da una base de la rejilla hecha de la más corta y la segunda más corta (independiente), vector de la red en el polinomio de tiempo.
Breve historia en la dimensión 2 : desde el más grande del vector de la base, agregar/quitar es la más corta como para hacer que sea más corto. Enjuague y repita. (funciona de la misma manera como el algoritmo de euclides para encontrar el pgcd de dos enteros)
Ejemplo : de$\displaystyle \binom{5}{5}$$\displaystyle \binom{14}{13}$.
quitar dos veces $\displaystyle \binom{5}{5}$$\displaystyle \binom{14}{13}$, formando $\displaystyle \binom{4}{3}$. como un entero combinación, este nuevo vector está en el interior de su red.
su nuevo vectores $\displaystyle \binom{5}{5}$$\displaystyle \binom{4}{3}$. Quitar el último de los antiguos, y usted consigue $\displaystyle \binom{1}{2}$.
ahora usted tiene $\displaystyle \binom{1}{2}$$\displaystyle \binom{4}{3}$. Quitar el ex dos veces desde el último, y obtener $\displaystyle \binom{2}{-1}$.
ahora usted tiene $\displaystyle \binom{2}{-1}$$\displaystyle \binom{1}{2}$. Usted no puede hacer ninguna de ellas más cortos mediante la adición/eliminación de la otra. El algoritmo LLL en la dimensión 2 (llamado el Lagrange o algoritmo de Gauss) nos dice que esos son los vectores más cortos en la red (no dependientes).
Todo esto se hace generalmente mediante el uso unitario de transformación (multiplicación por entero celosías de determinante $\pm 1$) en la rejilla de la base (a $n\times n$ de la matriz). Aquí hicimos :
$$ \left(\begin{array}{cc} 5&14 \\5 &13\end{array}\right) \left(\begin{array}{cc}1 & -2\\ 0&1\end{array}\right)\left(\begin{array}{cc}1 &0 \\-1 &1\end{array}\right)\left(\begin{array}{cc}1 & -2\\ 0&1\end{array}\right)=\left(\begin{array}{cc} 1&2 \\ 2&-1\end{array}\right) $$
la base original está a la izquierda, y cada paso es una de la multiplicación de matrices (de izquierda a derecha). El resultado final está a la derecha. Generalmente se $\left(\begin{array}{cc}0 &1 \\ 1&0\end{array}\right)$ matrices para el intercambio entre los dos vectores (de esa manera el más corto es el de la izquierda), pero he quitado los que están aquí, para mayor claridad.
Para grandes dimensiones, la cosa se pone fea. No podía encontrar nada agradable para el caso de 2 dimensiones, así que vamos a ir :
Interior de trabajo :
Tiene dos vectores $u$$v$, ordenado por longitud euclidiana. Se define el coeficiente de $\mu=\dfrac{u\cdot v}{\|u\|^2}$. que el coeficiente de $\mu$ representa la relación de la longitud de la proyección de la $v$ $u$ (ver foto de abajo). A continuación, haciendo que el vector $v$ tan corto como sea posible se hace mediante la eliminación de $\lceil \mu \rfloor \times u$$v$. Tenemos un nuevo vector de $v$ de tal manera que uno de los siguientes casos :
![after size-reduction]()
el nuevo $\mu$$\left[-\dfrac{1}{2};\dfrac{1}{2}\right]$, lo que significa que el $v$ vector está en el interior de las dos barras verticales. Esto se llama tamaño reducido.
En el lado izquierdo el vector $v$ está dentro del círculo de radio de $\|u\|$, lo que significa que $v$ es ahora más corto de $u$. Por lo tanto, el intercambio de posición de $u$ $v$ rendimiento $|\mu|>\dfrac{1}{2}$ (se puede ver mediante la proyección de $u$$v$)
En el lado derecho, sin embargo, $v$ está fuera del círculo (el Lovasz condición se dice que ser verificada) y por lo tanto el intercambio de los lugares de $u$ $v$ no producir nada. La base se dijo LLL reducido, y $u$ es el menor distinto de cero vector de la red.
Prueba :
vamos a decir que no. Hay $x$ $y$ enteros ($x\neq 0$) tal que $xu+yv$ es más corto de $u$.
$$
\begin{aligned}
\|xu+yv\|^2 &= x^2\|u\|^2+2xy(u\cdot v)+y^2\|v\|^2\\
&= x^2\|u\|^2+2\mu xy \|u\|^2+y^2\|v\|^2\\
&\geq (x^2+2\mu xy +y^2)\|u\|^2\\
&\geq (x^2- |xy| +y^2)\|u\|^2
\end{aligned}
$$
Cualquiera de las $x^2$ o $y^2$ es mayor que $|xy|$. Por lo tanto, $(x^2- |xy| +y^2)$ es mayor que $\min(x^2;y^2)$. Si que es mínimo $0$, $xu+yv$ es un entero distinto de cero combinación de $u$ o $v$, y por lo tanto mayor que $u$ (contradicción). Si no es así, a continuación, $(x^2- |xy| +y^2)>0$ y obtenemos una contradicción.
Por lo tanto, $u$ es el más corto de vector.
Para la liga de la leche en mayor dimensión, la misma de dos vectores en un momento, la selección de los dos vectores a través de un proceso similar a una especie de burbuja : una vez que un par de vectores es hacer llegar a la siguiente vector, y se mueve hacia abajo cada vez que cambiamos de vectores. Para el $\mu$ coeficiente de utilizar la de Gram-Schmidt Orthogonalisation.
