Problema de empacotamento de compartimento

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

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