Ajuda na programação, respostas a perguntas / Algoritmo / Grade de ladrilhos com retângulos 2 x 1 e 2 x 2 - algoritmo, programação dinâmica, ladrilho, recorrência

Grade de ladrilhos com 2 x 1 e 2 x 2 retângulos - algoritmo, programação dinâmica, ladrilhos, recorrência

Não consegui escrever a relação de recorrência para uma pergunta como a abaixo.

Dada uma grade retangular, com dimensões de 4 x n, quantas maneiras existem para revestir completamente a grade com dominós 2 x 2 e 2 x 1?

Aqui, para retângulos 2 x 1, é muito bem feito, mas não consegui descobrir se os retângulos são 2 x 1 e 2 x 2: http://www.acmgnyr.org/year2007/h.c

Alguma ideia?

Por exemplo, para

4x1: 1 caminho

4x2: 11 maneiras

4x3: 29 maneiras

O código abaixo gera todas as possibilidades usando força bruta. Mas eu quero fazer isso usando programação dinâmica.

https://gist.github.com/4519601

Respostas:

2 para resposta № 1

Acho que você pode resolver isso usando um algoritmo de programação dinâmico.

Imagine representar a grade não como uma grade 4 x nde quadrados, mas como uma 4 tupla que representa as larguras de cada coluna individual. Cada vez que você coloca um ladrilho, você pode tentar colocá-lo em algum lugar de forma que um de seus quadrados toque o canto superior esquerdo do lado esquerdo da grade. O efeito disso é alterar a largura efetiva de cada uma das colunas. Por exemplo, dada esta grade 4 x 3:

. . .
. . .
. . .
. . .

Nós o codificaríamos como (3, 3, 3, 3). Se você colocasse um bloco de 2 x 2 no canto superior, você obteria o seguinte:

X X .
X X .
. . .
. . .

Isso seria codificado como (1, 1, 3, 3), uma vez que as duas linhas superiores agora são efetivamente muito menores.

Isso sugere uma recursiva inicial (ineficiente)algoritmo. Como seus casos básicos, o mundo (0, 0, 0, 0) tem apenas uma solução (ou seja, não fazer nada). Qualquer mundo onde não haja uma maneira legal de colocar um ladrilho que cubra o quadrado superior da linha mais à esquerda não tem solução. Caso contrário, para todos os movimentos possíveis, faça esse movimento, atualize a representação interna do mundo e adicione recursivamente em todas as soluções que você pode encontrar naquele mundo menor.

Isso é extremamente lento (exponencialmente), mas pode ser dramaticamente acelerado. Em particular, observe que o número de 4 tuplas possíveis é (n + 1)⁴. Isso significa que o número máximo de chamadas recursivas únicas é O (n⁴) Portanto, se você memorizar suas chamadas recursivas ou usar a programação dinâmica para computar as chamadas de trás para frente, você só precisa fazer um número polinomial de chamadas. A memorização deve ser muito fácil de adicionar a uma solução recursiva existente e a aceleração deve ser enorme.

Se você está procurando por um método mais matemáticomaneira precisa de resolver este problema, considere tentar escrever uma função geradora para este problema e usá-la para derivar uma solução de forma fechada. Depois de ter isso, não deve ser tão difícil avaliá-lo diretamente com muito mais eficiência do que a solução acima. Como não sou um especialista em geração de funções, não tenho certeza de como você faria isso .

Espero que isto ajude!

0 para resposta № 2

Dentro 4xn, n é par ou ímpar. E se n é mesmo, é só usar 2x2 dominó. Caso contrário, use 2x2 até n-1. Então use dois 2x1 dominó para terminar o 4x1 bloco restante. Ao responder, não segui seu link, pois presumo que a pergunta esteja suficientemente formulada e o link seja simplesmente sua resposta a um problema mais simples.

n = par