Problema do empacotamento
Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Junho de 2017) |
No problema de bin packing (ou problema do empacotamento), objetos de diferentes volumes devem ser embalados em um número finito de bandejas ou recipientes de volume V de uma forma que minimize o número de recipientes utilizados. Na teoria da complexidade computacional, este é um problema de combinatória NP-difícil.[1] O problema de decisão (decidir se um determinado número de pacotes é o ideal) é NP-completo.[2]
Existem muitas variações deste problema, tais como empacotamento 2D (2D packing), empacotamento linear (linear packing), empacotamento por peso (packing by weight), empacotamento por custo (packing by cost), e assim por diante. Eles tem muitas aplicações, tais como o enchimento de recipientes, carregamento de caminhões com peso com capacidade restrita, criação de arquivo de backup (cópias de segurança) em mídia.
O problema do empacotamento também pode ser visto como um caso especial do problema de corte de estoque (cutting stock problem). Quando o número de pacotes é restrito a 1 e cada item é caracterizado por um volume e um valor, o problema de maximização do valor dos itens que podem caber na lixeira é conhecida como a problema da mochila.
Apesar do fato de que o problema do empacotamento tem uma complexidade computacional uma NP-difícil, as melhores soluções para grandes instâncias do problema pode ser produzido com algoritmos sofisticados. Além disso, muitas heurísticas foram desenvolvidas: por exemplo, o algoritmo de first fit fornece uma solução rápida, mas muitas vezes não ideal, envolvendo colocar-se cada item para a primeira posição que couber. Ele requer custo de tempo Θ(n log n), onde n é o número de elementos a ser empacotados. O algoritmo pode ser tornado mais eficaz se primeiramente ordenar a lista de elementos em ordem decrescente (às vezes conhecida como o algoritmo first-fit decrescente), embora isso ainda não garante uma solução ótima, e para longas listas pode aumentar o tempo de execução do algoritmo. Sabe-se, contudo, que existe sempre pelo menos um ordenamento de itens que o first-fit produzir uma solução ótima.[3]
Um variante do bin packing que ocorre na prática é quando os itens podem compartilhar o espaço quando empacotados em uma caixa. Especificamente, um conjunto de itens pode ocupar menos espaço quando embaladas em conjunto do que a soma de seus tamanhos individuais. Esta variante é conhecida como VM packing[4] desde quando máquinas virtuais (VMs) são embaladas em um servidor, o total de sua memória gerenciada pode diminuir devido às páginas compartilhadas pelas VMs as quais precisam ser armazenados apenas uma vez. Se os itens podem dividir o espaço de maneiras arbitrárias, o problema do empacotamento é difícil, mesmo de forma aproximada. No entanto, se o compartilhamento de espaço se encaixa em uma hierarquia, como é o caso de compartilhamento de memória em máquinas virtuais, o problema do empacotamento pode ser eficientemente aproximado.
Declaração Formal
[editar | editar código-fonte]Dado um conjunto de pacotes (bins) de um mesmo tamanho e uma lista de itens com tamanhos para empacotar, encontre um número inteiro de bins e uma -partição do conjunto tal que A solução é ótimo se possui um . O valor de para uma solução ótima é denotado como OPT abaixo. Uma possível formula mesclada de programação linear com inteiros é:
minimize | |
subject to | |
onde se pacote for usado e e então é colocado no pacote .[5] ±https://pt.wikipedia.org/w/index.php?title=Problema_do_empacotamento&action=edit§ion=1 {{hushijkam/kmkna<lozxpk>paoocpalp´lpçll/lock</focautl>
Algoritmo de first-fit
[editar | editar código-fonte]Este é um algoritmo de aproximação muito simples, o algoritmo guloso. O algoritmo processa os itens em ordem arbitrária. Para cada item, ele tenta colocar o item no primeiro pacote que pode acomodá-lo. Se nenhum pacote é encontrado, ele abre um novo pacote e coloca o item dentro deste novo pacote.
É bastante simples para mostrar este algoritmo, obtém-se um fator de aproximação de 2, isto é, o número de pacotes utilizados por este algoritmo não é mais do que duas vezes o número ideal. Em outras palavras, é impossível para 2 pacotes estarem preenchidos no máximo pela metade, pois tal possibilidade implica que em algum ponto, exatamente um pacote foi no máximo cheio até a metade e um nov foi aberto para acomodar um item de tamanho de no máximo V/2. Mas desde que o primeiro tem, pelo menos, um espaço de V / 2, o algoritmo não abrirá um novo pacote para qualquer item cujo tamanho é de, no máximo, V / 2. Só depois de o pacote encher-se com mais do que o V / 2, ou se um item com um tamanho maior do que o V / 2 chega, o algoritmo pode abrir uma nova posição.
Assim, se temos B bandejas, pelo menos B − 1 bandejas estão cheias mais que a metade do total. Portanto, . Porque é um limite inferior do valor ideal OPT, temos que B − 1 < 2OPT e, portanto, B ≤ 2OPT.[6] Veja a análise abaixo para uma melhor aproximação dos resultados.
Prova alternativa:
Suponha que o algoritmo guloso retorna mais de 2 OPT pacotes. Se tomarmos quaisquer dois pacotes sucessivos, juntos, eles devem conter, pelo menos, V de itens (caso contrário, apenas um pacote seria o suficiente para estes itens). Desde que nós temos, no mínimo, OPT pares mais pacotes extra, nós, em conjunto, teríamos mais do que OPT V itens, que seria uma contradição.
Algoritmos de Aproximação
[editar | editar código-fonte]As estratégias best fit e o first fit estão entre os mais simples algoritmos heurísticos para resolver o problema do empacotamento. Eles foram provados que não utilizam mais de 11/9 OPT 1 pacotes (onde OPT é o número de posições dadas pela solução ótima).[7] O mais simples destes, a estratégia First Fit Decrescente(FFD), onde opera primeiramente ordenando os itens a serem inseridos em ordem decrescente por seus tamanhos e, em seguida, inserir cada item para o primeiro pacote na lista com espaço suficiente restante. Às vezes, no entanto, não se tem a opção de classificar a entrada, por exemplo, quando nos deparamos com um problema online de empacotamento. Em 2007, foi comprovado que o limite 11/9 OPT 6/9 para a FFD é Grande-O.[8] MFFD[9] (uma variante do FFD) não usa mais do que 71/60 OPT 1 pacotes[10] (i.e. delimitada por cerca de 1.18 OPT, em comparação com cerca de 1,22 OPT por FFD). Em 2013, Sgall e Dósa deu um limitante superior para a estratégia first-fit (FF), mostrando que ele nunca precisa mais do que 17/10 OPT posições, para qualquer entrada.
É NP-difícil para distinguir se OPT é 2 ou 3, assim, para todo ε > 0, problema do empacotamento é difícil de aproximar cerca de 3/2 − ε. (Se tal aproximação, existe, pode determinar se n inteiros não negativos pode ser particionado em dois conjuntos com a mesma soma em tempo polinomial. No entanto, esse problema é conhecido por ser NP-difícil.) Consequentemente, o problema do empacotamento não tem um esquema de tempo polinomial de aproximação (APMS), a menos que P = NP. Por outro lado, para qualquer 0 < ε ≤ 1, é possível encontrar uma solução usando não mais do que (1 ε)OPT 1 pacote em tempo polinomial. Este tipo de aproximação é conhecida como assintótico PTAS.[11][12]
Algoritmo exato
[editar | editar código-fonte]Martello e Toth[13] desenvolveram um algoritmo exato para o 1-D problema do empacotamento, chamado de MTP. Uma alternativa mais rápida é a algoritmo Conclusão de Pacotes (Bin Completion) proposto por Korf, em 2002,[14] e, mais tarde, melhorado;[15] este segundo livro relata o tempo médio para resolver um milhão de ocorrências, com 80 itens em um 440 MHz Sun Ultra com 10 workstation foi de 31 ms.
Outra melhoria foi apresentada por Schreiber e Korf em 2013.[16] A novo e melhorado algoritmo Conclusão de Pacotes é mostrado para ser de até cinco ordens de magnitude mais rápido que Conclusão de Pacotes antigo sobre problemas não-triviais com 100 itens, e supera o BCP (branch-and-cut-and-price) algoritmo por Belov e Scheithauer em problemas que têm menos de 20 pacotes como a solução ideal. Qual o algoritmo tem o melhor desempenho depende das propriedades do problema, como o número de itens, o número ideal de pacotes, o espaço não utilizado na solução ótima e precisão de valores.
Veja também
[editar | editar código-fonte]- Se o número de caixas é para ser fixo ou restrito, e o tamanho das caixas é para ser o mínimo, este é um problema diferente, que é equivalente ao problema de programação com múltiplos processadores
- Guilhotina problema
- Subconjunto soma problema
Referencias
[editar | editar código-fonte]- ↑ Korte, Bernhard; Vygen, Jens (2006). «Bin-Packing». Combinatorial Optimization: Theory and Algorithms. Col: Algorithms and Combinatorics 21. [S.l.]: Springer. pp. 426–441. ISBN 978-3-540-25684-7. doi:10.1007/3-540-29297-7_18
- ↑ Barrington, David Mix (2006). «Bin Packing»
- ↑ Lewis 2009
- ↑ Sindelar, Sitaraman & Shenoy 2011, pp. 367–378
- ↑ Martello & Toth 1990, p. 221
- ↑ Vazirani 2003, p. 74.
- ↑ Yue 1991, pp. 321–331.
- ↑ Dósa 2007, pp. 1–11.
- ↑ Garey & Johnson 1985, pp. 65–106.
- ↑ Yue & Zhang 1995, pp. 318–330.
- ↑ Vazirani 2003, pp. 74–76.
- ↑ Fernandez de la Vega & Lueker 1981, pp. 349–355
- ↑ Martello & Toth 1990, pp. 237–240.
- ↑ Korf 2002
- ↑ R. E. Korf (2003), An improved algorithm for optimal bin packing.
- ↑ Schreiber & Korf 2013
Bibliografia
- Korf, Richard E. (2002), A new algorithm for optimal bin packing. (PDF), consultado em 8 de julho de 2016, cópia arquivada (PDF) em
|arquivourl=
requer|arquivodata=
(ajuda) 🔗 - Vazirani, Vijay V. (2003), Approximation Algorithms, ISBN 3-540-65367-8, Berlin: Springer
- Yue, Minyi (outubro 1991), «A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) 1, ∀L for the FFD bin-packing algorithm», Acta Mathematicae Applicatae Sinica, ISSN 0168-9673, 7 (4): 321–331, doi:10.1007/BF02009683
- Dósa, György (2007), «The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I) 6/9», in: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ISBN 978-3-540-74449-8, Springer Berlin / Heidelberg, ISSN 0302-9743, 4614/2007, pp. 1–11, doi:10.1007/978-3-540-74450-4
- Xia, Binzhou; Tan, Zhiyi (2010), «Tighter bounds of the First Fit algorithm for the bin-packing problem», Discrete Applied Mathematics, ISSN 0166-218X, 158 (15): 1668–1675, doi:10.1016/j.dam.2010.05.026
- Garey, Michael R.; Johnson, David S. (1985), «A 71/60 theorem for bin packing*1», Journal of Complexity, 1: 65–106, doi:10.1016/0885-064X(85)90022-6
- Yue, Minyi; Zhang, Lei (julho 1995), «A simple proof of the inequality MFFD(L)≤71/60 OPT(L) 1,L for the MFFD bin-packing algorithm», Acta Mathematicae Applicatae Sinica, ISSN 0168-9673, 11 (3): 318–330, doi:10.1007/BF02011198
- Fernandez de la Vega, W.; Lueker, G. S. (dezembro 1981), «Bin packing can be solved within 1 ε in linear time», Springer Berlin / Heidelberg, Combinatorica, ISSN 0209-9683, 1 (4): 349–355, doi:10.1007/BF02579456
- Lewis, R. (2009), «A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing», Computers and Operations Research, 36 (7): 2295–2310, doi:10.1016/j.cor.2008.09.004
- Martello, Silvano; Toth, Paolo (1990), «Bin-packing problem» (PDF), Knapsack Problems: Algorithms and Computer Implementations, ISBN 0471924202, Chichester, UK: John Wiley and Sons
- Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
- David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
- Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Two-Dimensional Bin Packing Problems". In V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization, Wiley/ISTE, p. 107-129
- Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
- Benkő A., Dósa G., Tuza Z. (2010) Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, Pages 298-302.
- Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), «Sharing-Aware Algorithms for Virtual Machine Colocation», Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367–378
- Schreiber, Ethan L.; Korf, Richard E. (2013), Improved Bin Completion for Optimal Bin Packing and Number Partitioning (PDF), ISBN 978-1-57735-633-2, IJCAI '13, Beijing, China: AAAI Press, pp. 651–658, consultado em 8 de julho de 2016, cópia arquivada (PDF) em
|arquivourl=
requer|arquivodata=
(ajuda) 🔗
Ligações externas
[editar | editar código-fonte]- PHP Class to pack files without exceeding a given size limit
- An implementation of several bin packing heuristics in Haskell, incluindo FFD e MFFD.
- Visualization of heuristics for 1D and 2D bin packing
- Cutting And Packing Algorithms Research Framework, incluindo o número de algoritmos de Bin Packing e os dados dos testes.
- A simple on-line bin-packing algorithm
- Optimizing Three-Dimensional Bin Packing
- Fpart : open-source command-line tool to pack files (C, BSD-licensed)
- Bin Packing and Cutting Stock Solver Algorithm