Nessa seção aplicamos a nossa implementação do algoritmo L nos dezesseis problemas apresentados em [26]. Esses problemas são considerados problemas difíceis de resolver.
A nossa implementação do algoritmo L foi feita em C. Abaixo estão as configurações das três máquinas usadas para resolver os problemas:
As Figuras ()-() ilustram as soluções obtidas pelo algoritmo.
Na Tabela apresentamos, para cada problema, o tempo gasto para resolver o problema em cada uma das máquinas descritas acima (tempo gasto com a função Resolve, portanto sem contar o tempo gasto para as inicializações, alocamento de memória e a função DesenhaSolucao).
Observe que significa que dado um retângulo de dimensão conseguimos empacotar n retângulos de dimensões .
Em algumas máquinas nem todos os problemas foram resolvidos, pois a memória da máquina não foi suficiente.
Na Tabela apresentamos a quantidade de posições alocadas pelo vetor solucao e quanto foi usado dele. Note que nesses 16 problemas, não usamos mais que 3% do vetor.
|