O problema de empacotamento
Numa mudança de casa, enche um caixote atrás do outro e pergunta-se se uma ordem mais inteligente teria precisado de menos. Esse é o problema de empacotamento, e é conhecido por ser difícil: até os computadores só encontram o menor número de caixas para entradas grandes com uma pesquisa engenhosa. Ainda assim, regras simples ficam surpreendentemente perto.
O problema
Dados objetos com tamanhos e caixas que levam todas a mesma quantidade, ponha cada objeto numa caixa sem que nenhuma transborde, usando o menor número possível de caixas. Os tamanhos podem representar pesos, comprimentos, durações ou tamanhos de ficheiros. Parece um passatempo para uma tarde de chuva, mas é NP-difícil: não se conhece nenhum método que encontre rapidamente o menor número de caixas para qualquer entrada.
Regras rápidas
O Next Fit enche uma caixa até o objeto seguinte já não caber, depois começa uma caixa nova e nunca volta atrás. O First Fit mantém todas as caixas abertas e põe cada objeto na primeira caixa com espaço. O Best Fit põe cada objeto na caixa mais cheia que ainda tem espaço. As três decidem logo, o que é útil quando os objetos chegam um a um e têm de ser colocados imediatamente.
Ordenar primeiro
Os objetos grandes são os difíceis, porque precisam de muito espaço livre. Ordenar os objetos do maior para o menor e depois usar o First Fit ou o Best Fit põe os grandes nas caixas enquanto ainda estão vazias, e os pequenos preenchem os espaços. O First Fit Decreasing nunca usa mais de 11/9 do menor número de caixas, mais uma constante, contra 1,7 vezes do First Fit com objetos não ordenados.
Um exemplo
Considere caixas de tamanho 10 e os objetos 2, 3, 2, 1, 3, 4, 5, 6, 7 e 7, que somam 40. O First Fit põe 2, 3, 2 e 1 na primeira caixa e 3 e 4 na segunda, e depois 5, 6, 7 e 7 precisam cada um de uma caixa só para si: 6 caixas. Com os objetos ordenados do maior para o menor, o First Fit Decreasing faz 7 + 3, 7 + 3, 6 + 4 e 5 + 2 + 2 + 1: 4 caixas cheias, o que coincide com o limite inferior de 40 / 10 = 4.
Encontrar o menor número de caixas
Para poucos objetos, a resposta exata pode ser encontrada por programação dinâmica sobre subconjuntos: para cada conjunto de objetos, o menor número de caixas e a última caixa mais vazia que o contêm, construídos a partir dos conjuntos com menos um objeto. Isso leva cerca de 2ⁿ·n passos para n objetos. Instâncias maiores resolvem-se com branch and bound ou programação inteira, e o limite inferior indica quão longe do melhor pode estar um empacotamento.
Onde é usado
Carregar camiões e contentores, cortar tubos ou rolos de papel a partir de comprimentos padrão com o mínimo de desperdício (o problema de corte), distribuir máquinas virtuais por servidores e arrumar ficheiros em discos são todos problemas de empacotamento. Em duas e três dimensões, com caixotes em vez de números, o problema é ainda mais difícil.
Perguntas frequentes
Qual é a diferença entre empacotamento online e offline?
Online, cada objeto tem de ser colocado assim que chega, sem conhecer os restantes; o Next Fit, o First Fit e o Best Fit funcionam assim. Offline, todos os objetos são conhecidos de antemão, por isso podem ser ordenados primeiro, como faz o First Fit Decreasing.
Quão perto do melhor fica o First Fit Decreasing?
Usa no máximo 11/9 do menor número de caixas mais 6/9 de uma caixa, um limite que György Dósa provou ser exato em 2007. Em entradas típicas, costuma ser ótimo ou ficar a uma caixa do ótimo.
O empacotamento é o mesmo que o problema da mochila?
Estão relacionados, mas são diferentes. A mochila enche um só saco com os objetos mais valiosos; o empacotamento põe todos os objetos no menor número possível de sacos. Os métodos exatos de empacotamento funcionam muitas vezes resolvendo, uma e outra vez, problemas parecidos com o da mochila.
Porque é que a aplicação só aceita 12 objetos?
Porque a resposta exata analisa cada conjunto de objetos, e 12 objetos já formam 4096 conjuntos. As regras rápidas aguentariam milhares de objetos, mas o desenho e a comparação com a resposta exata não.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o empacotamento