Ciclo de construção em retângulo

Eu tenho que construir um ciclo com comprimento fixo que inclua exatamente cantos dentro do retângulo x .$n$$k$$w$$h$

Por exemplo:
$w = 5\\h=3$

$n = 12\\k = 6$

Eu já descobri que preciso de pelo menos cantos e o número de cantos e o número de elementos que não sejam cantos precisam ser números pares.$4$

Depois, escrevo um algoritmo recursivo que é executado em complexidade de tempo exponencial, mas tenho uma forte sensação de que isso pode ser feito muito mais rapidamente.

O problema é que eu não sei qual quadrado definitivamente estará no ciclo, então eu executo meu algoritmo nos primeiros campos para cobrir todas as chances, mas estou ciente de que procuro em algumas ramificações várias vezes.$\frac w2$

Descobri também que, se o ciclo existir, começará com canto em (0, 0) ou canto em (0, 1)

Alguém tem uma idéia de como acelerar essa coisa?

Tenha um bom dia!

seu problema me parece inerentemente exponencial para encontrar todas as soluções. um esboço aproximado para mostrar que é criar um grande número de objetos com aparência semelhante. os objetos são os mesmos em translação e rotação. eles (aparentemente?) também podem ser redimensionados. portanto, em um sentido aproximado, não há como "acelerar" se você já possui um algoritmo de tempo exponencial. você pede um algoritmo melhor, mas também pede idéias gerais. Aqui estão algumas idéias / sugestões.

• você abstraiu o problema, mas pode ajudar a retroceder e descrever o pano de fundo que o inspirou. é de algum campo em particular? as chances são de que há trabalhos que estudam a área geral.

• parece que está no NP porque é fácil verificar soluções. pense em resolvê-lo em termos de NP. Um problema canônico nessa área é o problema da satisfação . muitos problemas foram convertidos para ele e os solucionadores SAT são "avançados" para resolver problemas de NP. Os solucionadores de SAT podem descobrir e lidar com as simetrias intrínsecas no problema não tecnicamente "eficientemente" (no sentido de tempo P garantido), mas da "maneira mais eficiente conhecida" com base em heurísticas, "melhores práticas" e décadas de pesquisa em otimização / teoria. considere traduzi-lo para o SAT e estudá-lo dessa maneira.

• se você quiser ter uma idéia geral do comportamento do algoritmo, execute-o em diferentes escalas e faça um gráfico do número de soluções para encontrar propriedades básicas de dimensionamento.

• se você quiser apenas uma solução, tente uma abordagem probabilística em que defina uma forma inicial simples, como quadrado / retângulo e altere-a aleatoriamente até que se aproxime de seus requisitos. veja, por exemplo, heurística . algoritmos genéticos também são bons para isso. você pode codificar a forma em termos de codificação genética.

• imagine uma forma triangular com 2 lados retos em ângulo reto e depois uma terceira diagonal e com qualquer número de cantos necessário. não é um uso "eficiente" do espaço, pois possui uma grande área aberta, mas atende aos seus critérios e pode ser criado em qualquer escala com um número arbitrário de cantos. você não especificou nenhum critério para minimizar ou maximizar o espaço dentro ou fora. então talvez isso seja um pouco mal restrito, como indicado.

• realmente acho que isso pode precisar ser melhor descrito. você está tocando em quadrados apenas nos quadrados das arestas e os quadrados tocando nos quadrados das arestas? o que você quer dizer com "cantos"? cantos do seu objeto? quadrados de canto no retângulo? você dá apenas um exemplo; portanto, sua descrição é um tanto ambígua ou sujeita a erros de interpretação em uma inspeção mais detalhada.