Implementação

A maior dificuldade do método está na quantidade de memória que o algoritmo necessita. Precisa-se armazenar, para cada subproblema, a quantidade de retângulos empacotados, o tipo de solução utilizado e o ponto de divisão (informação complementar ao tipo de solução). Em [26], esses dados foram armazendos usando uma estrutura de dados chamado PHORMA (Perfect Hashed Order Restricted Multidimensional Array) [24,12]. Essa estrutura de dados usa dígrafos para indexar as peças.

Seja $p$ e $q$ as cardinalidades dos conjuntos ${c \le L \vert c= \alpha l + \beta w, com \alpha, \beta \in I\!\!N}$ e ${c \le W \vert c= \alpha l + \beta w, com \alpha, \beta \in I\!\!N}$ respectivamente. Como, por definição, $L \ge W$, então $p \ge q$. Na nossa implementação armazenamos esse dados em 3 vetores de tamanho $p^4$ cada um.

Para ter acesso direto aos dados precisamos, dado um subproblema $L(I,J,i,j)$, calcular o índice dos vetores onde seus dados estão armazenados. Para isto, fizemos uma função bijetora $\alpha : I\!\!N\mapsto I\!\!N^4$ que serve para associar cada $L(I,J,i,j)$ a um índice $k$. Seja $m$ o tamanho da largura do retângulo maior. Então definimos essa função bijetora como:

$\alpha(k) = ((k/m^3) \mbox{ mod }m, (k/m^2) \mbox{ mod }m, (k/m) \mbox{ mod }m, k \mbox{ mod }m),$

$\alpha ^{-1}(I,J,i,j) = (((I \times m)+J) \times m+i) \times m+j,$

onde $a\mbox{ mod }b$ é o resto da divisão de $a$ por $b$.

Usando PHORMA, reduz-se a quantidade de memória necessária para resolver os problemas, mas em compensação demora mais comparando com a nossa implementação. Com a nossa implementação, tivemos alguns problemas devido à grande quantidade de memória que o algoritmo necessitava para resolver alguns problemas. Note que não são usadas todas as posições dos vetores que armazenam os dados (veja Tabela na Seção ).