Encontre os cantos

8

Como encontrar os cantos do cubo da unidade em mais próximo de um ponto no cubo? Use a métrica L1, para que em 4d | - 0000 | = , | - 0001 = ( x 0 à direita) e assim por diante.R d x x x i x x 3 + x 2 + x 1 + ( 1 - x 0 )d+1Rdx
xxixx3+x2+x1+(1x0)
x0

Para uma formulação alternativa, primeiro vire xi > 1/2 e classifique, de modo que 0xd1 x1x0 1/2; por simetria, um algoritmo para este caso pode fazer qualquer x no cubo.
Defina c12x , 1cd1 c1c00 .
Então nós queremos d+1cantos com o menor c canto.

Em 4d, por exemplo, com xi diminuindo 1/2 .. 0 como acima, os 5 cantos mais próximos podem 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

No entanto, em 5d, 6d ... as árvores de cantos crescentes parecem (para mim) cada vez mais bagunçadas.
Heurísticas para a aproximação mais próxima seria boa.

Denis
fonte
O que quebra na abordagem direta? Assume-se que cada um dos cantos do cubo é em e x [ 0 , 1 ] d . Arredonde cada coordenador para o número inteiro mais próximo para obter o ponto mais próximo p e gere d mais "pontos mais próximos" adicionando a cada coordenada de , independentemente. {0,1}dx[0,1]dpdp1mod2p
Daniel Apon 23/12/12
@Daniel Apon, em 3d com 0 <= x2 <= x1 <= x0 <= 1/2 ou 1> = c2> = c1> = c0> = 0 como acima, os 4 cantos mais próximos podem ser 000 001 010 100 como você sugere, mas também pode ser um rosto 000 001 010 011. (O cubo 3d inteiro se divide em 8 + 6 pedaços, 8 cantos mais adjacentes e 6 faces).
Denis
2
Aqui está outra maneira de declarar esse problema: dada uma coleção de números não negativos, encontre os subconjuntos de custo mínimo (onde o custo de um conjunto é a soma dos números nele). n + 1nn+1
Neal Young
Sim, esse é o mínimo c. canto acima - subconjunto de custo mínimo é um nome melhor, adicione-o ao título / tags?
31412 Denis

Respostas:

8

TempoO(d3logd)

lema: Corrija qualquer . Depois, há um conjunto contendo cantos de que estão mais próximos de e que está conectado (o que significa que o subgrafo do hipercubo induzido por está conectado). S d + 1 { 0 , 1 } d x S Sx[0,1]dSd+1{0,1}dxSS

Prova. Primeiro considere o caso em que não tem coordenadas iguais a .1 / 2x1/2

Dado qualquer canto em , inverter uma coordenada de não aumentará a distância de até se . S a j a a x | a j - x j | 1 / 2aSajaax|ajxj|1/2

Considere quaisquer dois cantos em que diferem em pelo menos uma coordenada e suponha ao WLOG que e . Se , virar em indica outro ponto em (porque diminui a distância de a ). Ou, se , em seguida, lançando em dá um ponto no . Repetindo este processo para cada uma diferindo de coordenadas em e dá um caminho que liga eS j um j = 0 b j = 1 x j < 1 / 2 b j b S b x x j > 1 / 2 um j um S um b um b Sa,bSjaj=0bj=1xj<1/2bjbSbxxj>1/2ajaSabab dentro .S

Se tiver coordenadas iguais a , então, ao escolher , quebre laços entre pontos equidistantes, dando precedência para aqueles com mais coordenadas zero. Então o mesmo argumento funcionará. QED1 / 2 Sx1/2S

Pelo lema, você pode usar um Dijkstra-como algoritmo para encontrar . Comece com um canto mais próximo de ( com se ). Então repetidamente adicionar ao um canto que está mais próximo entre aqueles que são adjacentes a algum ponto em . Pare quando pontos foram adicionados. x um um j = 0 x j1 / 2 S x S d + 1Sxaaj=0xj1/2SxSd+1

Ingenuamente (usando um min-heap para encontrar o próximo ponto mais próximo de em cada iteração), acho que existem iterações , e cada iteração requer trabalho de para gerar os vizinhos do nó adicionado ( cada um dos quais tem representação do tamanho ), fornecendo o tempo de execução .d + 1 O ( d 2 ) d d O ( d 3 log d )xd+1O(d2)ddO(d3logd)

TempoO(d2logd)

Representam cada canto implicitamente como um par , onde é um hash do conjunto de índices tal que , e é a distância de para . A partir de um determinado canto , os pares para todos os cantos vizinhos podem ser gerados em tempo (total). Isso reduz o tempo de execução para .( h , d ) h i a i = 1 d x a a O ( d ) O ( d 2 log d )a(h,d)hiai=1dxaaO(d)O(d2logd)

Mais rápido?

Para facilitar a discussão, vamos reformular o problema da seguinte maneira. Dada uma sequência de números não negativos , encontre os subconjuntos de custo mínimo dos números, em que o custo de um subconjunto é a soma dos números nele. y 1y 2y d d + 1dy1y2ydd+1 (Para ver a conexão com o problema anterior, pegue ; então cada subconjunto dos corresponde a um canto do hipercubo, ondeY y i a ( y ) a i ( y ) y iY Y x a ( y )yi=|xi1/2|Yyia(y)ai(y) é 1 se ( e y iY ) ou (xi1/2yiY e); e o custo deé a distância dea.)xi>1/2yiYYxa(y)

Aqui está uma idéia geral para um algoritmo mais rápido. Talvez alguém possa descobrir como fazê-lo funcionar.

Defina um gráfico direcionado implícito em que cada nó é um subconjunto dos 's. O nó inicial é o conjunto vazio. Represente os nós implicitamente como pares que é o hash do subconjunto é o custo. Para cada subconjunto Y , defina os subconjuntos vizinhos de alguma forma, de modo que (i) se Y Y ' for uma aresta direcionada, o custo ( Y ' ) custo ( Y ) e (ii) para qualquer subconjunto Y ' , haverá um aresta direcionada Y Y y i ( h , c ) h cYyi(h,c)hcYYY(Y)(Y)YYYde algum subconjunto que custo ( Y ) custo ( Y ) . Em seguida, execute Dijkstra's neste gráfico implícito, começando no nó inicial.Y(Y)(Y)

Escolha as arestas (de alguma forma) para que (i) e (ii) se mantenham, e a soma dos graus dos nós mais baratos é O ( d ) . (Isso é sempre possível, por exemplo, considerar as arestas como as de uma árvore de caminho mais curto enraizada no início.) Mas pode-se definir um gráfico desse tipo sem o conhecimento a priori da árvore de caminho mais curto? Nesse caso, isso pode levar a um algoritmo de tempo (?).d+1O(d)O(dlogd)

Neal Young
fonte
Obrigado Neal. Alguém pode melhorar a expansão de cantos do tipo Dijkstra? Os conjuntos de possíveis cantos d + 1 mais próximos após a normalização (virar x para <= 1/2 e classificar) parecem crescer muito lentamente com d.
Denis
Editei a resposta para discutir o tempo de execução mais explicitamente.
Neal Young
E a resposta de David mostra como reduzi-lo a . O(dlogd)
Neal Young
8

É equivalente pedir, entre um conjunto de itens com peso não negativo, os subconjuntos d + 1 do peso total mínimo. Pode-se formar todos os subconjuntos dos itens em uma árvore, na qual o pai de um subconjunto é formado removendo o item mais pesado (com os vínculos quebrados arbitrariamente, mas consistentemente); as soluções d + 1 formarão uma subárvore desta árvore conectada em sua raiz (o conjunto vazio).dd+1d+1

Assim, pode-se pesquisar nessa árvore os menores itens por uma forma do algoritmo de Dijkstra, na qual mantemos uma fila de subconjuntos de prioridades e os removemos em ordem de prioridade. Começamos com o primeiro item selecionado sendo o conjunto vazio. Em seguida, em cada etapa, mantemos como invariante do algoritmo uma fila de prioridade contendo o próximo filho não selecionado para cada subconjunto já selecionado. Quando selecionamos um conjunto S , o removemos da fila de prioridade e adicionamos à fila de prioridade dois novos subconjuntos: seu primeiro filho (o conjunto formado pela adição do próximo elemento mais pesado que o elemento mais pesado em S ) e seu próximo irmão (o conjunto formado removendo o elemento mais pesado em S e adicionando o mesmo próximo elemento mais pesado).d+1SSS

Após classificar os itens por seus pesos, é fácil representar cada conjunto implicitamente (como seu elemento mais pesado, mais um ponteiro para seu conjunto pai), manter o peso total de cada conjunto e encontrar o primeiro filho e o próximo irmão necessários pelo algoritmo em tempo constante por conjunto. Portanto, o tempo total é dominado pela classificação inicial e pelas operações da fila de prioridade, que levam o tempo total .O(dlogd)

Mesmo isso pode ser melhorado, se os itens já estiverem classificados por seus pesos. Visualize a relação "primeiro filho" e "próximo irmão" do algoritmo anterior como filhos esquerdo e direito em uma árvore binária de subconjuntos. Essa árvore é ordenada por pilha (aumento total de peso de pai para filho), para que possamos aplicar um algoritmo para encontrar os nós de peso mínimo em uma árvore binária ordenada por pilha [GN Frederickson. Um algoritmo ideal para seleção em um min-heap. Information and Computation, 104: 197-214, 1993]. O tempo total, após a etapa de classificação, é O ( d ) .d+1O(d)

David Eppstein
fonte
Concordo com a solução de David: a árvore binária que ele descreve é ​​suficiente para alcançar todos os conjuntos, dando tempo a . O(dlogd)
Neal Young
0

Na prática, os pesos costumam ser distribuídos uniformemente, aproximadamente ~ 1 2 3 Então, uma heurística simples é para começar:

os bits únicos , por exemplo, 10000000 01000000 00000001d
combinações de bits baixos 00000011 00000101 00000110 00000111ln2d
combinações de poucos bits dos próximos , por exemplo, 00001001 00001010 00001100. O melhor d + 1 desses candidatos funciona muito bem na prática, pelo menos para d pequeno .ln2d
d+1d

Denis
fonte