Experimentos Numéricos

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:

• xingu: AMD Athlon 1.1 Gb, 256 Mb de memória.
• jacuzzi: Pentium 3 600 MHz, 512 Mb de memória.
• sutra: AMD Athlon 1.5 Gb, 3.5 Gb de memória.

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 $P_n=(L,W,l,w)$ significa que dado um retângulo de dimensão $(L,W)$ conseguimos empacotar n retângulos de dimensões $(l,w)$.

Table: Tempo (em segundos) gasto para resolver os dezesseis problemas difíceis.

	xingu	jacuzzi	sutra
$P_{53} = ( 43, 26, 7, 3)$	4,867	7,867	3,583
$P_{57} = ( 49, 28, 8, 3)$	14,450	23,617	10,783
$P'_{69} = ( 57, 34, 7, 4)$	26,067	42,400	19,433
$P''_{69} = ( 63, 44, 8, 5)$	29,567	48,200	22,033
$P_{71} = ( 61, 35, 10, 3)$	68,683	110,250	51,283
$P_{75} = ( 67, 37, 11, 3)$	120,683	190,700	89,667
$P'_{77} = ( 61, 38, 10, 3)$	104,783	167,650	78,033
$P''_{77} = ( 61, 38, 6, 5)$	36,367	59,217	27,167
$P_{81} = ( 67, 40, 11, 3)$	181,433	287,267	136,250
$P'_{82} = ( 74, 49, 11, 4)$	268,767	425,817	201,633
$P''_{82} = ( 93, 46, 13, 4)$	-	504,033	238,717
$P'_{96} = (106, 59, 13, 5)$	-	1023,320	482,033
$P''_{96} = (141, 71, 13, 8)$	-	-	203,533
$P_{97} = ( 74, 46, 7, 5)$	112,783	179,900	84,017
$P_{99} = ( 86, 52, 9, 5)$	387,250	612,500	289,717
$P_{100} = (108, 65, 10, 7)$	-	346,100	159,117

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.

Table: Uso do vetor alocado para resolver os dezesseis problemas difíceis.

	tamanho	posições	porcentagem
	do vetor	usadas	usada do vetor
$P_{53} = ( 43, 26, 7, 3)$	2085136	20457	0,981%
$P_{57} = ( 49, 28, 8, 3)$	3418801	47008	1,375%
$P'_{69} = ( 57, 34, 7, 4)$	5764801	71614	1,242%
$P''_{69} = ( 63, 44, 8, 5)$	6250000	75923	1,215%
$P_{71} = ( 61, 35, 10, 3)$	7890481	143698	1,821%
$P_{75} = ( 67, 37, 11, 3)$	11316496	210270	1,858%
$P'_{77} = ( 61, 38, 10, 3)$	7890481	188729	2,392%
$P''_{77} = ( 61, 38, 6, 5)$	7311616	90449	1,237%
$P_{81} = ( 67, 40, 11, 3)$	11316496	275432	2,434%
$P'_{82} = ( 74, 49, 11, 4)$	12960000	356428	2,750%
$P''_{82} = ( 93, 46, 13, 4)$	33362176	433080	1,298%
$P'_{96} = (106, 59, 13, 5)$	47458321	694109	1,463%
$P''_{96} = (141, 71, 13, 8)$	100000000	395713	0,396%
$P_{97} = ( 74, 46, 7, 5)$	15752961	188579	1,197%
$P_{99} = ( 86, 52, 9, 5)$	25411681	470589	1,852%
$P_{100} = (108, 65, 10, 7)$	45212176	331070	0,732%