Embalagem com retângulo em Python

5

Estou trabalhando em um projeto que envolve o empacotamento de vários retângulos em um retângulo maior (a caixa delimitadora). Os retângulos não podem se sobrepor uns aos outros ou com os limites da caixa delimitadora. Os retângulos podem girar, aumentando o espaço de estados para n! * 2^n para problemas de n retângulos.

Estou tentando escrever um programa em Python que 'solucione' esses problemas, por exemplo, ele deve encontrar todas as soluções possíveis, considerando um conjunto de retângulos e uma caixa delimitadora. Estou usando um algoritmo de busca em profundidade agora, mas sinto que estou perdendo muitas otimizações para acelerar meu programa. Meu algoritmo funciona da seguinte maneira:

  1. Eu tenho uma lista com valores representando as alturas das colunas na caixa delimitadora maior, inicializada para todos os 0s.
  2. Eu procuro o primeiro ponto vazio na caixa delimitadora, que é representada pela coluna com o menor valor.
  3. Se o retângulo atual couber nesse ponto, eu 'posiciono' o retângulo aumentando a altura das colunas à direita pela altura do retângulo.
  4. Repita 2 e 3 até que não haja mais retângulos adequados e volte para outras possíveis soluções.

No código (pseudo-), parece com isto:

def solve(rectangles):

    # Solution found
    if rectangles is empty:
        add_to_solutions()
        return

    position = find_first_empty_spot()
    for rectangle in rectangles:
        for r in [rectangle, rectangle.rotated()]:
            if rectangle fits at given position:
                place_rectangle_in_bounding_box(r)
                remove r from rectangles
                solve(remaining_rectangles)
                remove_rectangle_from_bounding_box(r)

Os fundamentos do meu algoritmo estão corretos ou faltam algumas melhorias (óbvias)? Seria ótimo resolver problemas de tamanhos de até 20 retângulos, mas meu algoritmo atual levaria muito tempo para resolvê-los.

E: estou tentando encontrar "todas" possíveis soluções para o problema, não posso parar depois de encontrar uma solução "a", portanto, muitas heurísticas encontradas na literatura não são aplicáveis.

    
por Koen 04.05.2015 / 11:20
fonte

1 resposta

2

O problema que você está perguntando é um problema bem conhecido que tem uma infinidade de aplicações: Por exemplo, a tarefa de minimizar o desperdício de material na produção de móveis: Certas peças (sua lista de retângulos) devem ser cortadas de tábuas de compensado em um determinado tamanho (seu retângulo delimitador). Como você já deve ter descoberto, encontrar todas as soluções possíveis é um problema combinatório NP-difícil .

Por isso, na indústria, geralmente não insistimos em encontrar todas as soluções possíveis, mas usamos um algoritmo de aproximação que pode Claro que nem sempre entregar a melhor solução possível. Então, atualmente, a melhor resposta que posso dar à sua pergunta é apontar para este BPP exemplo aqui ilustrando o uso de um solucionador de código aberto Pacote Python OpenOpt .

De minha compreensão, seu desejo de enumerar todas as soluções possíveis é impossível de ser cumprido em um tempo aceitável, mesmo para um número moderado de 20 retângulos. Se isso não for verdade, também estou ansioso para conhecer e aprender.

    
por 15.05.2015 / 14:22
fonte