Tegelen rechthoek met tegels van vaste grootte

Ik heb geworsteld met het vinden van een handige oplossing voor het volgende probleem:

Suppose we have a wall of a given size and 4 types of tiles of sizes 4 x 2, 2 x 2, 2 x 1, 1 x 1. There are certain rectangular regions inside the perimeter of the wall which can not be tiled (i.e. holes). There is also a special type of tile which has a variable dimension A x B with A < 1. This is used to pad the tiling to the margin of the rectangle, if needed.

Zoek een betegeling van de muur die de volgende beperkingen respecteert:

  1. Tegels van dezelfde grootte kunnen niet onder elkaar worden geplaatst, met dezelfde uitlijning (dus tegels die op een rij eronder verschijnen, moeten zodanig worden verschoven dat er geen tussenruimte is die eruit ziet als een kruising tussen aangrenzende tegels van dezelfde size)
  2. Er wordt een minimumaantal tegels gebruikt
  3. Tegels die de grenzen van de rechthoek overschrijden, worden bijgesneden tot aan de marge; de aldus geproduceerde onvolledige tegel zal in kleinere tegels worden gebroken; dit kan eventueel het gebruik van een speciale tegel inhouden die altijd naast de marge van de rechthoek of de marge van een gat moet zitten, waar de situatie zich ook voordoet

Dit is wat ik tot nu toe heb geprobeerd:

  1. Ik heb algoritmen onderzocht om dit op te lossen met behulp van domino-tegels, maar de meeste mensen lijken er niet om te geven dat het tegelproces geen gaten kan produceren die op een kruis lijken waar tegels samenkomen. Ook lijkt het probleem voor mij een beetje anders, omdat er meer soorten tegels zijn en het ook lijkt dat de rechthoek niet precies hoeft te worden gevuld (het is mogelijk dat kleine ruimtes in de buurt van de marges blijven die worden gevuld met speciale tegels )
  2. Ik heb geprobeerd alle mogelijke tilings te genereren met behulp van een branch and bound-techniek met state node snoeien, zodat alleen die toestanden waar tegels die de beperkingen niet doorbreken worden toegevoegd, worden onderzocht, maar dit is zeker niet schaalbaar.
  3. Ik heb ook gekeken naar verpakkingsalgoritmen, maar voor zover ik weet, kan dit leiden tot een bepaalde betegeling met kleine, tot stilstand gekomen spaties die in het pand van de muur kunnen blijven.

Het is mogelijk dat ik iets over het hoofd heb gezien of niet genoeg inzicht heb gehad tijdens het verkennen van de bovenstaande technieken.

Met al deze gezegd, hebben jullie tips of suggesties over een manier om dit te benaderen, wat resultaten oplevert?

Dit is een voorbeeld van een betegeling die de beperkingen 1 en 3 respecteert, maar niet optimaal is

3

1 antwoord

Heb je de optimale tegelwerk nodig, of ben je bereid om genoegen te nemen met "redelijk goed"? Het vinden van de optimale oplossing is waarschijnlijk buitengewoon moeilijk. Intuïtief zou ik de volgende heuristiek suggereren:

1. Pretend there are no holes in the wall, tile with large tiles.

2. Remove all tiles which intersect with holes.

3. current_size = largest

4. For each empty space: tile as much as possible with current_size

5. current_size = the size just below current_size

6. return to 4
0
toegevoegd
Het probleem met deze aanpak is de complexiteit van het invullen van de resterende grootte. Men moet de eerste plaatsing vinden zodat er geen kruisjes (+) worden gevormd. Dit hangt natuurlijk af van de manier waarop je je eerste betegeling hebt gedaan. Er kunnen situaties zijn waarin een dergelijke betegeling niet mogelijk is vanwege de manier waarop u uw eerste betegeling hebt gemaakt. Er zijn ook situaties waarbij de gaten dicht bij elkaar liggen, waardoor u ze beschouwt als een gezamenlijke behuizing die de zoekruimte vergroot.
toegevoegd de auteur filipcampeanu, de bron