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.
Problema de empacotamento de compartimento
Conjunto de elementos para empacotamento
| | | ||
|---|---|---|---|
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:
- Pegue um novo elemento.
- Pegue um novo recipiente.
- Coloque o elemento no recipiente.
- Pegue o próximo elemento.
- 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:
- Pegue um novo elemento.
- Pegue um novo recipiente.
- Coloque o elemento no recipiente.
- Pegue o próximo elemento.
- 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:
- Pegue um novo elemento.
- Pegue um novo recipiente.
- Coloque o elemento no recipiente.
- Pegue o próximo elemento.
- 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:
- Pegue um novo elemento.
- Pegue um novo recipiente.
- Coloque o elemento no recipiente.
- Pegue o próximo elemento.
- 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.
Calculadoras similares
- • Solucionador de Problemas de Empacotamento de Compartimento 2D
- • Combinatória. Gerador de permutação de N a M com repetições.
- • Combinatória. Gerador de permutação de N a M sem repetições.
- • Combinatória. Gerador de combinações.
- • Quantos círculos de raio r cabem em um círculo maior de raio R
- • seção Matemática ( 134 calculadoras )
Comentários