Python: Ajuster des formes géométriques dans une matrice de tableau?

Au cours des derniers jours, je pensais à une solution pour un problème d'IA. Le problème ressemble à ceci:Python: Ajuster des formes géométriques dans une matrice de tableau?

Je veux déterminer un arrangement pour quelques formes géométriques données (qui ne dépassent pas la taille de la planche donnée) sur une planche carrée de taille donnée, de manière à ce que la planche soit uniforme couvert et les formulaires ne se chevaucheront pas. Je veux appliquer Depth first search/Greedy meilleure première recherche, mais il est difficile de trouver une représentation correcte des formes et du tableau pour le traverser. Je suis nouveau sur python, ce qui le rend un peu plus difficile. Aucune suggestion?

exemple visuel:

Source

2016-05-22 user3293380

Pouvez-vous poster un exemple? –

@RosaGronchi Vous pourriez imaginer quelque chose comme un jeu de tetris. Vous auriez quelques formes exactement comme celles de tetris, que vous pourriez utiliser l'une après l'autre pour les additionner les unes sur les autres. Vous pouvez également faire pivoter les formulaires ... – user3293380

https://en.wikipedia.org/wiki/Tessellation? –

Ce que vous décrivez est une variation sur le rectangle/raccord carré. Des versions du problème existent où les cellules inutilisées doivent être minimisées pour un placement optimal des figures, alors que d'autres versions, comme celle que vous décrivez, exigent que la totalité du tableau soit couverte uniformément. Ce sont des problèmes de «placement parfait des carrés/rectangles».

Les moyens typiques pour résoudre ces problèmes impliquent l'utilisation de domaines entiers finis représentant les variables des rectangles et un ensemble de contraintes assurant que les placements géométriques sont valides (ie ne pas franchir les bordures du panneau, ne pas chevaucher entre eux mutuellement, ..).

Source

2016-05-22 09:47:09 SND

Disons que les cases remplies sur la carte ont la valeur 1 et celles vides ont la valeur 0. Je pensais à avoir le tableau initial comme une matrice et de construire pour l'autre un formulaire matrice de sorte que lorsque j'ajoute le formulaire au tableau, je ne reçois pas les valeurs> 1 (qui représentent un chevauchement). Mais ce n'est pas encore clair comment je traverserais la matrice en utilisant DFS/GBFS. – user3293380

Ajout d'images pour faciliter la compréhension – user3293380

C'est en effet un bon moyen de modéliser ce problème, car chaque cellule "sait" combien de figures peuvent se chevaucher avec elle, couvrant uniformément chaque cellule devient facile. Jetez un coup d'œil au document [this] (http://4c.ucc.ie/~hsimonis/shikaku.pdf) en utilisant ECLiPSe comme langage de programmation, il pourrait vous être utile/utile. En ce qui concerne la recherche, vous avez le choix entre une recherche partielle (comme expliqué dans l'article: calculer au préalable tous les emplacements pour réduire l'espace de recherche final) ou effectuer une recherche en plaçant simultanément les chiffres. Bien sûr, les deux ont leurs avantages et leurs inconvénients. – SND

Python: Ajuster des formes géométriques dans une matrice de tableau?

Répondre

Questions connexes