Quantas combinações de k pixels vizinhos existem em uma imagem?

Question

Sou péssimo em matemática, então eu não posso descobrir isso:quantas combinações de k pixels vizinhos existem em uma imagem?Combinações de k pixels de n * n total de pixels na imagem, mas com a restrição de que eles devem ser vizinhos, para cada k de 2 até n * n.Eu preciso a soma de todos os valores de k para um programa que deve levar em conta que muitos elementos em um conjunto que é o raciocínio sobre.

Vizinhos são 4-conectados e não wrap-around.

Answer 1

Uma vez que você obtenha o número de formas distintas para um blob de pixels de tamanho k ( Aqui está uma referência ) então se trata de duas coisas:

• quantas maneiras em sua imagem você pode colocar este blob?
• Quantos destes são os mesmos para que você não conte com dupla (por causa de simetrias)?

Obter uma resposta exata é um enorme trabalho computacional (você está olhando para mais de 10 ^ 30 formas distintas para K= 56 - Imagine se k= 10.000), mas você pode ser bom o suficiente para o que você precisaAo encaixar para os primeiros 50 valores de k.

(Nota: A referência no artigo da Wikipedia cuida das duplicatas com a sua definição de A_K.)

Answer 2

Parece que você está trabalhando em um problema que pode ser mapeado para Markovianos Passeios.

Se eu entendi sua pergunta, você está tentando contagem de caminhos de comprimento k, como este:

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

em uma estrutura semelhante a um tabuleiro de xadrez, e você deseja conectar-se apenas na vertical e horizontal vizinhos.

Eu acho que você quiser os caminhos para ser auto-evitando, o que significa que um pixel não deve ser percorrido duas vezes em um pé (ou seja, sem loops).Esta condição levar a um problema clássico chamado de Serras (Auto Evitando Passeios).

Bem, agora as más notícias:O problema está aberto!Ninguém resolveu ainda.

Você pode encontrar uma boa introdução para o problema aqui, começando na página 54 (ou página 16, a contagem é confusa, pois os números de página são de repetição em doc).Mas todo o papel é muito interessante e de fácil leitura.Ele consegue explicar o conhecimento matemático, o histórico de casos e a importância científica de markovianos cadeias de alguns slides.

Espero que isso ajude ...para evitar o problema.

Answer 3

Se você estava planejando iterar sobre todos os possíveis Polyominos , tenho medo de vocêestarei esperando muito tempo.Do local da Wikipédia sobre Polóminos, vai ser pelo menos O (4.0626 ^ n) e provavelmente mais perto de O (8 ^ n).No período n= 14, a contagem será mais de 5 bilhões e muito grande para se encaixar em um int.Por tempo n= 30, a contagem será mais de 17 quintila e você não será capaz de encaixá-lo em um longo.Se todos os governos mundiais reuniram seus recursos para iterar através de todos os polominos em um ícone de 32 x 32, eles não seriam capazes de fazê-lo antes que o sol seja supernova.

Agora isso não significa o que você quer fazer é intratável.É provável que quase todo o trabalho que você faz em um polominal foi feito em parte dos outros.Pode ser uma tarefa divertida Faça uma velocidade exponencial usando programação dinâmica.O que você está tentando realizar?