Problema com a altura máxima de empilhamento

8

O seguinte problema foi estudado antes? Se sim, quais abordagens / algoritmos foram desenvolvidos para resolvê-lo?

Problema ("Problema na altura máxima de empilhamento")

Dado polígonos, encontre seu arranjo estável e sem sobreposição que maximize sua altura de empilhamento em um piso fixo sob a influência da gravidade.n


Exemplo

Três polígonos:

insira a descrição da imagem aqui

e três de seus infinitos arranjos estáveis ​​e sem sobreposição, com diferentes alturas de empilhamento:

insira a descrição da imagem aqui


Esclarecimentos

  • Todos os polígonos têm massa uniforme e densidade igual
  • O atrito é zero
  • A gravidade está agindo em todos os pontos na direção descendente (ou seja, os vetores de força são todos paralelos)
  • Uma configuração não é considerada estável se repousar sobre um ponto de equilíbrio instável (por exemplo, o triângulo verde nas figuras não pode se equilibrar em nenhum de seus vértices, mesmo que a massa à esquerda e à direita do ponto de equilíbrio seja igual)
  • Para esclarecer ainda mais o ponto acima: Um polígono é considerado instável ("tombamento"), a menos que repouse em pelo menos um ponto estritamente à esquerda e em pelo menos um ponto estritamente à direita do centro de gravidade (essa definição simplifica bastante a simulação e em particular, torna desnecessária a integração de posições etc., com o objetivo de avaliar se um arranjo é estável ou não.
  • O problema em sua forma "física" é um problema contínuo que só pode ser resolvido aproximadamente na maioria dos casos. Para obter um problema discreto que pode ser resolvido algoritmicamente, restrinja os vértices dos polígonos e sua colocação na disposição às redes adequadas.


Notas

  • Abordagens de força bruta de qualquer tipo são claramente inviáveis. Mesmo com restrições estritas no posicionamento de polígonos dentro da rede (como fornecer uma região limitada "espaço da rede"), a complexidade simplesmente explode por mais do que alguns polígonos.
  • Os algoritmos iterativos devem trazer heurísticas muito inteligentes, pois é fácil construir arranjos em que a remoção de qualquer polígono resulta na configuração instável e esses arranjos são inacessíveis por algoritmos que dependem de cada etapa intermediária ser estável.
  • Como o problema cheira pelo menos NP - mas é mais provável que EXPTIME - completo no número total de vértices, até as heurísticas seriam de considerável interesse. Uma coisa que dá esperança é o fato de a maioria dos humanos reconhecer que o terceiro arranjo no exemplo é ideal.
algorithms time-complexity optimization computational-geometry heuristics
fonte
Para essa definição de "instável" (embora possivelmente não seja mais precisa), pode-se, em princípio, resolver o problema exatamente pela eliminação do quantificador de campos fechados reais .
@ RickyDemer: Eu realmente gostaria de entender isso, mas, embora tenha olhado o jornal e siga os pontos principais, não vejo a conexão. Você poderia me dar mais algumas dicas? Uma ligação entre o problema de empilhamento e a álgebra certamente parece intrigante.
1
Isso pode ser porque eu vinculei incorretamente a um procedimento de decisão e não a um algoritmo de eliminação do quantificador . Este artigo é uma referência muito melhor para o que eu estava falando. Também encontrei um artigo sobre alguns casos quadráticos que podem ser suficientes quando as coordenadas dos vértices são todas racionais.
:) Também encontrei mais material ligando explicitamente a geometria computacional à eliminação do quantificador. Agora entendo o que você quis dizer com "embora possivelmente não seja para os mais precisos"; de fato, parece impossível estender esses métodos puramente formais à física "real", onde restrições complexas, como equações diferenciais, entram em jogo. No entanto, obrigado pelo interessante ângulo de ataque, passarei algum tempo estudando-o.

Respostas:

1

Embora eu não conheça nenhum algoritmo específico para esse problema, você pode abordar isso de um método bastante eficiente, dividindo-o em partes separadas.

Eu começaria encontrando a rotação para cada forma individual que fornece uma altura máxima, mantendo uma orientação de balanceamento válida (é: não em um ponto como o triângulo). Se uma forma tem várias alturas iguais, eu usaria a configuração que fornece a maior área de superfície em cima dela. Depois de ter isso, você poderá descobrir como empilhar melhor cada objeto em uma mansão capaz de ser equilibrada.

GEMISIS
fonte
4
É muito fácil construir exemplos em que essa abordagem leva a uma solução abaixo do ideal. Por exemplo, considere um paralelogramo obtido cortando um retângulo muito longo (para torná-lo estável apenas se descansar no lado comprido) mais um triângulo que corresponde ao seu ângulo de cisalhamento. Individualmente, com sua abordagem, você seria forçado a girar o paralelogramo para que ele fique do lado mais comprido, mas o triângulo pode apoiá-lo para que fique "em pé" (observe que o problema do atrito zero pode ser facilmente superado adicionando um pequeno recanto no paralelogramo que permite que o triângulo "se encaixe").
Isso é verdade, eu não tinha pensado nisso. Uma solução para isso pode ser verificar formas que possam ser usadas como suporte para o objeto, mas que nem sempre oferecem uma altura ideal. Você ainda pode tentar isso e comparar com várias configurações totais a melhor altura, pois isso ainda deve ser melhor do que uma força bruta.
GEMISIS
Aqui também se depara com problemas significativos, a saber, quando não é um objeto que suporta outro, mas uma pilha de objetos com a altura certa para suportar um objeto muito grande em pé. Os algoritmos para verificar tudo o que se torna arbitrariamente complexo. Dito isto, concordo que deve ser possível obter um tempo de execução "melhor que a força bruta" com algumas eliminações sensíveis.