O algoritmo pode ser usado para embalar retângulos de tamanhos diferentes para o menor retângulo possível de uma forma bastante ideal?
https://stackoverflow.com/questions/1213394
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho um monte de objetos retangulares que eu precisa para embalar no menor espaço possível (as dimensões deste espaço deve ser potências de dois).
Eu estou ciente de vários algoritmos de embalagem que irá embalar os itens tão bem quanto possível em um determinado espaço, no entanto, neste caso, eu preciso do algoritmo para trabalhar para fora como grande que o espaço deve ser bem.
Por exemplo, digamos Eu tenho as seguintes rectângulos
- 128 * 32
- 128 * 64
- 64 * 32
- 64 * 32
Eles podem ser acondicionados em um 128 * 128 espaço
_________________ |128*32 | |________________| |128*64 | | | | | |________________| |64*32 |64*32 | |_______|________|
No entanto, se houver também um 160 * 32 e um 64 * 64 um que seria necessário um 256 * 128 espaço
________________________________ |128*32 |64*64 |64*32 | |________________| |_______| |128*64 | |64*32 | | |_______|_______| | | | |________________|___ | |160*32 | | |____________________|___________|
O que algoritmos existem que são capazes de embalar um monte de retângulos e determinar o tamanho necessário para o recipiente (para uma potência de 2, e dentro de um determinado tamanho máximo para cada dimensão)?
Solução
A solução primeira passagem rápida e suja é sempre um grande para começar, como uma comparação, se nada mais.
colocação Greedy de grande a pequeno.
Coloque o maior retângulo restante em sua área lotada. Se ele não pode caber em qualquer lugar, coloque-o em um lugar que se estende a região do pacote tão pouco quanto possível. Repita até que você terminar com o menor retângulo.
Não é perfeito em tudo, mas é fácil e boa linha de base. Seria ainda embalar o seu exemplo original perfeitamente, e dar-lhe uma resposta equivalente para o segundo também.
Outras dicas
desta página sobre o projeto ARC para um levantamento de soluções, há um trade-off entre a implementação complexidade / hora e otimização, mas há uma grande variedade de algoritmos para escolher.
Aqui está um extrato dos algoritmos:
-
Primeiro-Fit decrescente Altura (FFDH) algoritmo
FFDH embala o Segue-R (em altura não crescente) no primeiro nível, em que R se encaixa. Se nenhum nível pode acomodar R, um novo nível é criado.
complexidade de tempo de FFDH: O (n · log n)
. proporção aproximação: FFDH (I) <= (17/10) · OPT (I) 1; o assintótica obrigado de 17/10 é apertado. -
Next-Fit decrescente Altura (NFDH) algoritmo
NFDH embala o Segue-R (em altura não crescente) sobre o nível de corrente se encaixa R. Caso contrário, o nível atual é "fechada" e um novo nível é criado.
complexidade de tempo: O (n · log n)
. proporção aproximação: NFDH (I) <= 2 · OPT (I) 1; o assintótica ligados de 2 é apertado. -
Best-Fit decrescente Altura (BFDH) algoritmo
BFDH embala o Segue-R (em altura não crescente) sobre o nível, entre aqueles que podem acomodar R, para que o espaço horizontal residual é o mínimo. Se nenhum nível pode acomodar R, um novo nível é criado. -
Inferior esquerdo (BL) Algoritmo
BL primeiros itens do pedido de largura não crescente. BL embala o próximo item tão perto do fundo como vai se encaixar e, em seguida, o mais próximo à esquerda como ele pode ir sem sobreposição com qualquer item embalado. Note não que BL é um algoritmo de embalagem orientada para nível.
complexidade de tempo: O (n ^ 2)
. proporção aproximação: BL (I) <= 3 · OPT (I). -
Up-Down (UD) de Baker algoritmo
UD usa uma combinação de BL e uma generalização do NFDH. A largura da tira e os itens são normalizados de modo que a tira é da unidade de largura. ordens UD os itens não largura crescente e, em seguida, divide os itens em cinco grupos, cada um com uma largura no intervalo (02/01, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. a tira é também dividida em cinco regiões R1, ···, R5. Basicamente, alguns itens de largura no intervalo (1 / i + 1, 1 / i], para 1 <= i <= 4, são embalados a região Ri por BL. desde BL deixa um espaço de largura crescente de cima para baixo no lado direito da faixa, UD leva esta vantagem por primeiro embalagem do produto de Rj para j = 1, ···, 4 (em ordem) de cima para baixo. Se não existe tal espaço, o produto é embalado em Ri por BL. Finalmente, os itens de tamanho, no máximo, 1/5 são embalados para os espaços em R1, ···, R4 pelo (generalizada) NFDH algoritmo. Mais uma vez, se não houver espaço nestas regiões, que o artigo é embalado utilizando a R5 NFDH.
proporção aproximação: UD (I) <= (5/4) · OPT (I) + (53/8) H, onde H é a altura máxima dos itens; o assintótica obrigado de 5/4 está apertado. -
reversa-fit (RF) algoritmo
RF também normaliza a largura da tira e os artigos de modo a que a tira é da unidade de largura. RF primeiro empilha todos os itens de maior largura de 1/2. itens restantes são classificados em altura não crescente e vai ser embalado acima da altura alcançada por aqueles H0 maior do que 1/2. Então RF repete o seguinte processo. Grosso modo, pacotes RF itens da esquerda para a direita com a sua parte inferior ao longo da linha de altura H0 até que não haja mais espaço. Em seguida, embala itens da direita para a esquerda e de cima para baixo (inverso chamado de nível) até que a largura total é de pelo menos 1/2. Em seguida, a nível reverso é deixado cair para baixo até que (pelo menos) um deles toca algum item abaixo. O drop-down é de alguma forma repetida.
rácio de aproximação:. RF (I) <= 2 · OPT (I) -
algoritmo
Steinberg algoritmo de Steinberg, denotado como H no papel, estima um limite superior da altura H necessária para embalar todos os itens tais que se prove que os itens de entrada pode ser embalada num rectângulo de largura W e a altura H. Eles então definir sete procedimentos (com sete condições), cada um para dividir um problema emdois menores e resolvê-los de forma recursiva. Foi mostrou que nenhum satisfaz problema tratável uma das sete condições.
proporção aproximação:. H (I) <= 2 · OPT (I) -
algoritmo de Split-Fit (SF) SF divide itens em dois grupos, L1 com maior largura de 1/2 e L2 no máximo 1/2. Todos os itens de L1 são primeiramente embalados por FFDH. Em seguida, eles são organizados para que todos os itens com largura de mais de 2/3 são inferiores aqueles com largura de, no máximo, 2/3. Isto cria um rectângulo R do espaço com uma largura de 1/3. Restantes itens na L2 são então embalado para R e o espaço acima aqueles embalados com L1 usando FFDH. Os níveis criados em R são considerados inferiores aos criada acima a embalagem de L1.
proporção aproximação: SF (I) <= (3/2) · OPT (I) + 2; o assintótica obrigado de 3/2 está apertado. -
algoritmo
Sleator O algoritmo do Sleater consiste em quatro etapas:-
Todos os itens de maior largura de 1/2 são embalados em cima da outra na parte inferior da faixa. h0 Suponha que é a altura da resultando embalagem Toda a embalagem posterior irá ocorrer acima h0.
-
itens restantes são ordenados por altura não crescente. Um nível de artigos são embalados (para aumentar a não-fim altura) da esquerda para a direita ao longo da linha de altura h0.
-
Uma linha vertical é então tirada no meio para cortar a tira em duas metades iguais (nota esta linha pode cortar um artigo que é embalado parcialmente na metade direita). Desenho de dois segmentos de linha horizontal de comprimento uma metade, um outro lado da metade esquerda (chamado de linha de base à esquerda) e uma através da metade direita (chamado de linha de base para a direita) o mais baixo possível de modo a que as duas linhas não atravessar todo o artigo.
-
Escolha a linha de base para a esquerda ou direita, que é de uma altura menor e embalar um nível de itens na metade correspondente da tira até o próximo item é muito grande.
Uma nova linha de base é formado e Passo (4) é repetido com a linha de base mais baixa até que todos os artigos são embalados.
complexidade de tempo: O (n · log n)
. A relação de aproximação do algoritmo de Sleator é de 2,5, que é apertado. -
Tenha um olhar em problemas de embalagem . Eu acho que o seu cai sob 'packing bin 2D. Você deve ser capaz de aprender muito com soluções para isso e outros problemas de embalagem.
Veja também: Embalagem dados de imagem retangular em uma textura quadrado <. / a>
Há uma extensa literatura sobre esse problema. Uma boa heurística gulosa é retângulos lugar de maior área para o menor na primeira posição disponível para a parte inferior e à esquerda do recipiente. Pense de gravidade puxando todos os itens para baixo para o canto inferior esquerdo. Para uma descrição deste google "Chazelle inferior esquerdo embalagem".
Para soluções óptimas, as técnicas state-of-the-art pode embalar mais de 20 retângulos em poucos segundos. Huang tem um algoritmo que separa o problema de encontrar o menor delimitador caixa delimitadora do problema de decidir se deve ou não um conjunto de retângulo pode caber em uma caixa delimitadora de um tamanho específico. Você dá seu programa um conjunto de retângulos, e diz-lhe o menor caixa delimitadora encerrando obrigados a embalá-los.
Para o seu caso, o loop externo deve iteração do menor caixa delimitadora o possível para cima (com a largura e altura sucessivamente aumentando em potências de dois). Para cada uma destas caixas delimitadoras, teste para ver se você pode encontrar uma embalagem para seus retângulos. Você vai ter um monte de "não" como resposta, até que a primeira resposta "sim", que será garantido para ser a solução ideal.
Para o circuito interno de seu algoritmo - o que respostas "sim" ou "não" a uma caixa delimitadora de tamanho específico, eu iria procurar a referência Huang e apenas implementar seu algoritmo. Ele inclui uma série de otimizações no topo do algoritmo básico, mas você só precisa realmente a carne básica e batatas. Desde que você quer lidar com rotações, em cada ponto de ramificação durante a sua pesquisa, simplesmente tentar ambos rotações e recuar quando ambas as rotações não resultam em uma solução.
Estou bastante certo de que este é um problema NP-duro, então, para uma solução ideal, você teria que implementar um algoritmo de retrocesso que tenta todas as combinações possíveis.
A boa notícia é que, devido à necessidade de embalar 2D retângulos em um espaço 2D limitado, você pode podar um monte de possibilidades logo no início, por isso não pode ser tão ruim assim.
O que você precisa é de https://github.com/nothings/stb/blob/master/stb_rect_pack.h
Exemplo:
stbrp_context context;
struct stbrp_rect rects[100];
for (int i=0; i< 100; i++)
{
rects[i].id = i;
rects[i].w = 100+i;
rects[i].h = 100+i;
rects[i].x = 0;
rects[i].y = 0;
rects[i].was_packed = 0;
}
int rectsLength = sizeof(rects)/sizeof(rects[0]);
int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];
stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);
for (int i=0; i< 100; i++)
{
printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}
A solução geral é não-trivial (falar matemática para completamente **** ing impossível)
Geralmente as pessoas usam um algoritmo genético para tentar combinações possíveis, mas você pode fazer razoavelmente bem por Justing colocando a maior forma em primeiro lugar e, em seguida, tentar lugares diferentes para a próxima maior e assim por diante.
Eu estou usando o de:
Ele implementa o algoritmo de guilhotina e exige como dimensão uma entrada e tenta otimizar o outro (você também pode definir um máximo com uma pequena mudança no código). Talvez se você tentar energia diferente dos dois valores que ele vai trabalhar para você.
Não é o ideal de qualquer maneira, mas é pequeno, portátil (.h apenas), e não tem nenhuma outra dependência diferente de C ++ e STL.
