Cortes elipsoidais para duas soluções
Partindo do princípio que soluções são vetores binários de tamanho fixo que sempre possuem N bits igual a um, os cortes elipsoidais podem ser extendidos facilmente a partir do conceito de uma elipse. Uma elipse possui dois focos (representados aqui por duas soluções) e os pontos da elipse são aqueles que estão em uma distância fixa D = R1+R2, onde R1 = distância do primeiro foco (primeira solução) e R2 = distância do segundo foco (segunda solução). Dada nossa representação de uma solução como um vetor de bits, a medida de distância entre duas soluções usada será a distancia de Hamming, ou seja, o número de bits diferentes entre as soluções - por exemplo 0011 e 0101 tem distância 2. E fácil perceber que, devido a restrição de N bits setados em 1, não existirão distancias ímpares.
Vamos exemplificar como funcionam os cortes elipsoidais, dadas duas soluções A e B de tamanho fixo 6 e que devem possuir sempre 3 bits setados:
A = 001011
B = 101010
Vamos começar gerando a elipse determinada pela distância D = 4. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 2. As soluções que satisfazem essa igualdade são as seguintes:
C = 101001 (onde D(A) = 2 e D(B) = 2)
D = 100011 (onde D(A) = 2 e D(B) = 2)
Agora vamos gerar a elipse determinada pela distância D = 6. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 3. As soluções que satisfazem essa igualdade são as seguintes:
E = 1X1X00 (onde D(A) = 2 e D(B) = 4)
F = 0X1X01 (onde D(A) = 2 e D(B) = 4)
G = 1X0X10 (onda D(A) = 4 e D(B) = 2)
H = 0X0X11 (onde D(A) = 4 e D(B) = 2)
Nestas soluções, usamos dois valores 'X' para indicar que um dos 'X' será 0 e o outro 'X' será 1. Cada uma das soluções anteriores representa, portanto, duas soluções, uma com o primeiro 'X' igual a 0 e o segundo igual a 1 e outra com o primeiro 'X' igual a 1 e o segundo igual a 0.
Agora vamos gerar a elipse determinada pela distância D = 8. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 4. As soluções que satisfazem essa igualdade são as seguintes:
I = 1X0X01 (onde D(A) = 4 e D(B) = 4)
J = 010110 (onde D(A) = 6 e D(B) = 2)
K = 011100 (onda D(A) = 2 e D(B) = 6)
Agora vamos gerar a elipse determinada pela distância D = 10. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 5. As soluções que satisfazem essa igualdade são as seguintes:
L = 110100 (onde D(A) = 6 e D(B) = 4)
M = 010101 (onde D(A) = 4 e D(B) = 6)
A elipse formada por D = 0 só existiria se R1+R2 fosse igual a zero, ou seja, as duas soluções fossem iguais. A elipse formada por D = 2 é trivial, contem somente as soluções A e B. A elipse formada por D = 12 exigiria uma solução que tem 3 bits setados completamente diferentes dos bits setados em A e B - nesse exemplo, esse conjunto é vazio.
Dadas duas soluções $A$ e $B$, encontrar as soluções $X$ que estão na elipsóide com distancia $D$ pode ser escrito como:
(1)Algumas observacoes:
- $N_1$ representa os indices dos bits da solucao $A$ que possuem valor 1.
- O primeiro termo representa a distancia de $X$ ate $A$ e o segundo representa a distancia de $X$ ate $B$. A distancia de Hamming e calculada somando o numero de elementos diferentes ($N$ menos os elementos que sao um em ambas as solucoes) e multiplicando por dois. Por exemplo, 0011 e 0101 tem 1 elemento em comum, o calculo seria $2(2-1)$, ou seja, a distancia entre eles e dois.
- Essa equacao pode ser extendida para encontrar solucoes mais proximas de $A$ e $B$ ou mais distantes, bastando trocar o sinal do corte para $\leq$ ou $\geq$. E facil perceber que o parametro $D$ pode ser usado para representar a liberdade (ou "folga") da nova solucao em relacao as duas solucoes originais.
Visualizando a vizinhanca
Como as solucoes sao vetores binarios de dimensao N, e dificil visualizar as vizinhancas elipsoidais. Algumas imagens que podem ajudar:
(COLOCAR O PLOT DAS ELIPSES)
Cortes elipsoidais para multiplas soluções
Uma extensao natural dos cortes descritos na secao anterior seria extende-los para multiplas soluções. Um corte elipsoidal de distancia no máximo $D$ gerado a partir de um conjunto de $K$ soluções $S = {S_a, S_b, S_c, ..., S_k}$ pode ser descrito como:
(2)Por exemplo, se tivermos tres soluções com N = 3:
A = 001011
B = 101010
C = 111000
Podemos usar a equacao acima para calcular a distancia de uma solucao qualquer para o elipsoide formado pelas tres solucoes A, B e C. Por exemplo E = 100110 tem distancia igual a 10 - ou seja, ele esta na vizinhanca elipsoidal de valor 10. Podemos entao usar o valor de $D/2$ na equacao acima como uma folga $F$, temos entao o seguinte corte, que pode ser aplicado para qualquer conjunto de soluções:
(3)Visualizando a vizinhanca
