Testes dos programas

No topo das tabelas está o nome do pacote retirado de http://elib.zib/de/steinlib. A notação é a mesma usada no sítio.

Os algoritmos são:
A3R: Árvores 3-Restritas
A3RZ:  Árvores 3-Restritas Original de Zelikovsky
GR3: Ganho Relativo (k=3)
GR4: Ganho Relativo (k=4)

Para os conjuntos de instâncias B e I080 foi feito um gráfico do custo relativo, que indica quão maior que o ótimo são as árvores produzidas pelos algoritmos para cada instância. O gráfico mostra o custo relativo médio e máximo.

Legenda das células:
 

X

    Menor custo da instância
 

X

    Valor ótimo

X

  Pior Custo relativo do conjunto para um algoritmo


B
Nome   |V|    |E|    |T|  A3R  A3RZ GR3 GR4  Opt
 b01 50  63  9  84 82 82 82 82
 b02 50  63  13  88 83 83 84 83
 b03 50  63  25  139 139 139 139 138
 b04 50  100  9  60 59 59 59 59
 b05 50  100  13  62 62 62 62 61
 b06 50  100  25  125 125 125 125 122
 b07 75  94  13  118 111 111 111 111
 b08 75  94  19  108 106 104 104 104
 b09 75  94  38  223 221 221 221 220
 b10 75  150  13  97 96 93 93 86
 b11 75  150  19  91 88 88 88 88
 b12 75  150  38  176 174 174

174

 174
 b13 100  125  17  178 175 175 175 165
 b14 100  125  25  246 238 238 238 235
 b15 100  125  50  324 318 318 318 318
 b16 100  200  17  133 130 130 130 127
 b17 100  200  25  135 133 132 132 131
 b18 100  200  50  220 218 218

218

 218

Gráfico do Custo Relativo Médio e Máximo de B

 

I080
Nome   |V|    |E|    |T|  A3R A3RZ GR3 GR4   Opt 
 i080-001 80  120  6  1987 1987 1987 1987 1787
 i080-002 80  120  6  1704 1607 1607 1607 1607
 i080-003 80  120  6  1903 1713 1713 1713 1713
 i080-004 80  120  6  2067 2052 2052 2052 1866
 i080-005 80  120  6  2002 1801 1801 1906 1790
 i080-011 80  350  6  1502 1498 1498 1498 1479
 i080-012 80  350  6  1662 1654 1484 1491 1484
 i080-013 80  350  6  1576 1555 1488 1488 1381
 i080-014 80  350  6  1588 1577 1569 1569 1397
 i080-015 80  350  6  1505 1504 1504 1504 1495
 i080-021 80  3160  6  1442 1259 1259 1180 1175
 i080-022 80  3160  6  1439 1255 1255 1261 1178
 i080-023 80  3160  6  1440 1283 1283 1251 1174
 i080-024 80  3160  6  1431 1251 1251 1251 1161
 i080-025 80  3160  6  1436 1242 1242 1248 1162
 i080-031 80  160  6  1761 1761 1667 1667 1570
 i080-032 80  160  6  2275 2275 2275 2200 2088
 i080-033 80  160  6  1989 1899 1899 1899 1794
 i080-034 80  160  6  1781 1775 1775 1775 1688
 i080-035 80  160  6  2053 2053 2053 2053 1862
 i080-041 80  632  6  1470 1375 1375 1358 1276
 i080-042 80  632  6  1473 1461 1461 1458 1287
 i080-043 80  632  6  1486 1382 1382 1406 1295
 i080-044 80  632  6  1513 1389 1389 1389 1366
 i080-045 80  632  6  1457 1443 1443 1384 1310
 i080-101 80  120  8  2789 2787 2787 2787 2608
 i080-102 80  120  8  2699 2504 2504 2504 2403
 i080-103 80  120  8  2791 2784 2784 2680 2603
 i080-104 80  120  8  2879 2677 2677 2676 2486
 i080-105 80  120  8  2203 2203 2203 2203 2203
 i080-111 80  350  8  2369 2261 2077 2077 2051
 i080-112 80  350  8  2181 1974 1974 1980 1885
 i080-113 80  350  8  2091 2084 2084 2084 1884
 i080-114 80  350  8  2193 2184 2191 1985 1895
 i080-115 80  350  8  2161 1956 1956 1956 1868
 i080-121 80  3160  8  2007 1644 1637 1561 1561
 i080-122 80  3160  8  1997 1713 1713 1561 1561
 i080-123 80  3160  8  2014 1658 1658 1654 1569
 i080-124 80  3160  8  2010 1665 1665 1555 1555
 i080-125 80  3160  8  2005 1721 1638 1638 1572
 i080-131 80  160  8  2467 2463 2463 2463 2284
 i080-132 80  160  8  2295 2295 2295 2295 2180
 i080-133 80  160  8  2388 2272 2272 2272 2261
 i080-134 80  160  8  2292 2092 2092 2092 2070
 i080-135 80  160  8  2182 2108 2108 2108 2102
 i080-141 80  632  8  2058 1944 1944 1869 1788
 i080-142 80  632  8  2061 2056 2056 1881 1708
 i080-143 80  632  8  2151 2129 2129 1776 1767
 i080-144 80  632  8  2070 2048 2048 1880 1772
 i080-145 80  632  8  2086 1950 1950 1982 1762
 i080-201 80  120  16  5255 4953 4953 4953 4760
 i080-202 80  120  16  4760 4670 4670 4676 4650
 i080-203 80  120  16  5190 4994 4895 4895 4599
 i080-204 80  120  16  5479 4781 4878 4781 4492
 i080-205 80  120  16  5166 4680 4680 4859 4564
 i080-211 80  350  16  4419 3984 3984 3845 3631
 i080-212 80  350  16  4406 4117 4117 3924 3677
 i080-213 80  350  16  4415 4095 4095 3858 3678
 i080-214 80  350  16  4411 4182 4182 3936 3734
 i080-215 80  350  16  4431 4037 4037 3966 3681
 i080-221 80  3160  16  4265 3356 3356 3357 3158
 i080-222 80  3160  16  4260 3442 3447 3442 3141
 i080-223 80  3160  16  4270 3438 3438 3279 3156
 i080-224 80  3160  16  4275 3441 3521 3352 3159
 i080-225 80  3160  16  4260 3291 3291 3360 3150
 i080-231 80  160  16  5338 4626 4833 4746 4354
 i080-232 80  160  16  5068 4470 4472 4380 4199
 i080-233 80  160  16  4726 4302 4436 4271 4118
 i080-234 80  160  16  4675 4374 4374 4374 4274
 i080-235 80  160  16  4843 4740 4740 4560 4487
 i080-241 80  632  16  4383 3817 3817 3812 3538
 i080-242 80  632  16  4383 3960 3960 3905 3458
 i080-243 80  632  16  4358 4044 4044 3878 3474
 i080-244 80  632  16  4365 3766 3766 3826 3466
 i080-245 80  632  16  4335 4079 4079 3993 3467
 i080-301 80  120  20  6099 5816 5816 5940 5519
 i080-302 80  120  20  6530 6131 6139 6131 5944
 i080-303 80  120  20  6275 5887 5887 6076 5777
 i080-304 80  120  20  5991 5878 5878 5878 5586
 i080-305 80  120  20  6735 6151 6314 6464 5932
 i080-311 80  350  20  5578 4994 5084 4901 4554
 i080-312 80  350  20  5585 5251 5251 5005 4534
 i080-313 80  350  20  5610 5098 5098 5033 4509
 i080-314 80  350  20  5532 5065 4983 4835 4515
 i080-315 80  350  20  5554 5170 5078 5078 4459
 i080-321 80  3160  20  5382 4461 4461 4277 3932
 i080-322 80  3160  20  5364 4039 4039 4039 3937
 i080-323 80  3160  20  5382 4218 4218 4123 3946
 i080-324 80  3160  20  5380 4352 4352 4193 3932
 i080-325 80  3160  20  5400 4295 4374 4221 3924
 i080-331 80  160  20  5852 5740 5826 5650 5226
 i080-332 80  160  20  6000 5669 5669 5669 5362
 i080-333 80  160  20  6063 5741 5741 5848 5381
 i080-334 80  160  20  5879 5569 5569 5664 5264
 i080-335 80  160  20  5725 5321 5500 5390 4953
 i080-341 80  632  20  5536 4591 4594 4593 4236
 i080-342 80  632  20  5533 4853 4853 4882 4337
 i080-343 80  632  20  5486 4911 4911 4848 4246
 i080-344 80  632  20  5557 4411 4857 4504 4310
 i080-345 80  632  20  5480 4761 4577 4656 4341

Gráfico do Custo Relativo Médio e Máximo de I080

 

X
Nome   |V|    |E|    |T|  A3R  A3RZ GR3 GR4  Opt

berlin52

 52  1326  16  1044 1044 1044 1044 1044
brasil58 58   1653  25  13665 13665 13665 13665 13655