Problema de empacotamento de compartimento

A calculadora soluciona o problema de empacotamento de compartimento através de diferentes algoritmos heurísticos.

Esta página existe graças aos esforços das seguintes pessoas:

Timur

Timur

Julia Gomes

Criado: 2021-05-24 14:10:37, Ultima atualização: 2021-05-24 14:10:37
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.

Esta calculadora é sobre Problema de empacotamento.

Em outras palavras, existem recipientes de volume fixo e um conjunto de objetos de qualquer tamanho (claro, o volume de cada item individualmente é menor que o volume do recipiente). É necessário empacotar os itens no número mínimo de recipientes.

Há outro exemplo de "vida" - existe um conjunto de arquivos (por exemplo, filmes) de diferentes tamanhos. É necessário copiar todos esses filmes no menor número de DVDs. E assim por diante.

Este é um problema NP, o que significa que encontrar a solução ideal requer uma listagem completa. Entretanto, existem algoritmos heurísticos para encontrar soluções adequadas. Se você tiver sorte, será ideal :)

Aqui estão uma calculadora e algoritmos descritos abaixo. E a propósito, embora nos dados padrão algumas soluções sejam as mesmas, os algoritmos ainda são diferentes, e com outros dados as diferenças serão notáveis.

PLANETCALC, Problema de empacotamento de compartimento

Problema de empacotamento de compartimento

Conjunto de elementos para empacotamento

Itens por página:

Dígitos após o ponto decimal: 2
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
Número total de recipientes
 
Uso geral de recipientes (%)
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
Número total de recipientes
 
Uso geral de recipientes (%)
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
Número total de recipientes
 
Uso geral de recipientes (%)
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
Número total de recipientes
 
Uso geral de recipientes (%)
 



Vamos começar com o Algoritmo Next Fit.

Algoritmo Next Fit
Na maioria dos casos, o algoritmo é muito monótono e fornece os piores resultados de todos os algoritmos considerados.
A essência do algoritmo é a seguinte:

  1. Pegue um novo elemento.
  2. Pegue um novo recipiente.
  3. Coloque o elemento no recipiente.
  4. Pegue o próximo elemento.
  5. Se o elemento couber em um recipiente, vá para a etapa 3. Se o item não couber no recipiente, vá para a etapa 2.

Então, nós simplesmente colocamos os elementos em um recipiente e, se um deles não couber, pegamos um novo recipiente.
É possível desenvolver um algoritmo melhor, mas este possui um lado positivo - não necessita de verificação dos recipientes anteriores. Pode ser útil se, por exemplo, os recipientes vierem até nós em uma esteira transportadora.

Algoritmo First Fit
A essência do algoritmo é a seguinte:

  1. Pegue um novo elemento.
  2. Pegue um novo recipiente.
  3. Coloque o elemento no recipiente.
  4. Pegue o próximo elemento.
  5. Se o elemento couber em um recipiente, vá para a etapa 3. Se o elemento não couber no recipiente, verifique os outros recipientes em ordem. Se houver um recipiente com espaço suficiente, coloque o elemento dentro do recipiente e vá para a etapa 4, caso contrário, vá para a etapa 2.

Ou seja, coloque um elemento em um recipiente, e se o elemento não couber mais, tente encontrar um recipiente adequado entre os já parcialmente preenchidos. Se não conseguirmos encontrar um espaço, pegamos um novo recipiente.

Algoritmo Worst Fit
A essência do algoritmo é a seguinte:

  1. Pegue um novo elemento.
  2. Pegue um novo recipiente.
  3. Coloque o elemento no recipiente.
  4. Pegue o próximo elemento.
  5. Se o elemento couber em um recipiente, vá para a etapa 3. Se o elemento não couber em um recipiente, pegue um recipiente parcialmente cheio com o máximo de espaço livre. Se o elemento couber em um recipiente, coloque o item no recipiente e vá para a etapa 4, caso contrário, vá para a etapa 2.

Para resumir, coloque os elementos no recipiente e, se o item não couber mais, tente colocá-lo no recipiente menos cheio. Se isso falhar, pegamos um novo recipiente.

Algoritmo Best Fit
A essência do algoritmo é a seguinte:

  1. Pegue um novo elemento.
  2. Pegue um novo recipiente.
  3. Coloque o elemento no recipiente.
  4. Pegue o próximo elemento.
  5. Se o elemento couber em um recipiente, vá para a etapa 3. Se o elemento não couber em um recipiente, pegue um recipiente parcialmente cheio com um mínimo de espaço, mas ainda ajuste o item. Se houver tal recipiente, vá para a etapa 3; caso contrário, vá para a etapa 2.

Em resumo, coloque os elementos no recipiente, e se o item não estiver mais interferindo, tente colocá-lo em um recipiente mais cheio, mas que ainda tenha espaço suficiente para este item. Se falhar, pegamos um novo recipiente.

Além disso, devo mencionar uma variante com pré-classificação decrescente - First Fit Decrescente, Best Fit Decrescente, etc. Funciona do mesmo jeito, mas os elementos são escolhidos para começar com o maior. Portanto, eu revisei 8 algoritmos, mas a calculadora utiliza apenas 4 - todos eles são pré-classificados porque fornecem os melhores resultados.

URL copiado para a área de transferência
PLANETCALC, Problema de empacotamento de compartimento

Comentários