Project Paper: Tiling problem
Groep 11: Said Hattachi, Ismael el Hadad Hakim, Muttalip Küçük
Januari 2015
Abstract Dit artikel beschrijft een heuristiek waarmee een veld op een systematische wijze gevuld kan worden door een set met tegels. Dit probleem behoort tot de klasse van de verpakking problemen en staat bekend als NP-‐‑volledig. Er zijn verschillende manieren om dit probleem op te lossen. In dit artikel analyseert men de heuristiek met behulp van twee algoritmes die deze heuristiek op een totaal tegengestelde wijze gebruiken. Hiermee worden er conclusies getrokken waarmee men verdere onderzoeken mogelijk maakt.
Introductie Er is een gegeven veld wat gevuld dient te worden. Hiervoor is er een set met tegels geleverd die bestaat uit tegels met verschillende afmetingen. Er kunnen tegels tussen zitten die dezelfde afmetingen hebben, dus een tegel kan meerdere malen gebruikt worden indien die zit in de tegelset. Het idee is om de tegels zo in het veld te plaatsen dat het veld volledig gevuld is en er geen gaten tussen de tegels is. Hierbij mag er geen overlap zijn tussen de tegels. Ook is de oppervlakte van het te vullen veld gelijk aan de oppervlakte van de tegelset. Dit betekent dat elke tegel in de tegelset gebruikt dient te worden.
Probleembeschrijving Er zijn 125 problemen geleverd met elk een tegelset die de twee algoritmes op moeten lossen gebruik makend van de heuristiek. Deze problemen worden opgedeeld in vijf categorieën: namelijk: 15 tegels, 25 tegels, 35 tegels, 45 tegels en 55 tegels. Elk categorie representeert een schatting van het aantal tegels in de geleverde tegelset. Dit betekent dat problemen die tot de categorie “35 tegels“ behoren een tegelset hebben met ongeveer 35 tegels.
Probleemkarakteristieken Elke veld en tegel is twee dimensionaal met een bepaalde breedte en hoogte. Tijdens het oplossen van een probleem mag men gebruiken maken van het plaatsen, het verwijderen en het omdraaien van een tegel. Het omdraaien betekent indirect dat een tegel van m bij n ook gezien kan worden als een tegels van n bij m.
Aannames Voor het oplossen van de problemen worden de volgende aannames gemaakt. Elk probleem is op te lossen aangezien die geleverd wordt door de opdrachtgever. Elke set van tegels bevat minimaal een grootste tegel. De grootte van een tegel wordt bepaald door de oppervlakte. Indien er meerdere grootste tegels zijn, kiest men voor de tegel die de hoogste waarde heeft voor de breedte of hoogte. Stel dat er een
tegelset is met een 6x1 tegel en een tegel 3x2. Dan kan men op basis van de oppervlakte niet uitmaken welke de grootste tegel is, aangezien beide stenen een oppervlakte van 6 hebben. Dan beschouwt men de 6x1 tegel als de grootste tegel. De hoogste waarde voor de breedte is 6 en voor de hoogte is 3. Aangezien de hoogte waarde voor de breedte groter is dan die voor de hoogte, kies men voor de tegel die hoor bij deze hoogste waarde.
Heuristiek De heuristiek bestaat uit drie onderdelen: namelijk “Perfect fit”, “Partly fit” en “No fit”. Perfect fit betekent dat er een tegel bestaat die het te vullen veld geheel vult. Links in figuur 1 is er sprake van perfect fit, aangezien de 2x2 tegel het te vullen veld dat ook 2 bij 2 is geheeld vult. Partly fit betekent dat de breedte of hoogte van de tegel gelijk is aan de breedte of hoogte van het te vullen veld. In het midden van figuur 1 ziet men dat zowel de breedte als de hoogte van het te vullen veld gelijk is aan de breedte van de tegel. Dit is een voorbeeld van partly fit. Het rechtergedeelte van figuur 1 geeft een voorbeeld van No fit weer. Het te vullen veld is namelijk 2 bij 2 en de breedte noch hoogte van de tegel is niet gelijk 2. In beiden algoritmes die nader worden behandeld weegt Perfect fit het zwaarst, daarna Partly fit en daarna No fit. 2 2 2 2
2x2
2
2x1
1x1
2
Figuur 1. Respectievelijk van links naar rechts Perfect fit, Partly fit en No fit.
Algoritme 1 Algoritme 1 gaat van groot naar klein door de tegelset en kiest de grootste tegel. Vervolgens plaatst het deze tegel linksboven en tekent een horizontale en verticale lijn (links in figuur 2). Zo ontstaan er drie ruimtes: onder, rechts en rechtsonder (rechts in figuur 2). Dan berekent men de oppervlaktes van de ruimte onder en rechts. Als de oppervlakte van de ruimte van onder kleiner of gelijk is aan die van rechts, dan vult men eerst de ruimte onder. Daarna wordt de ruimte rechts en rechtsonder als één ruimte gezien en wordt deze samengevoegde ruimte gevuld (links in figuur 3). Indien de oppervlakte van de ruimte van onder groter is dan die van rechts, dan vult men eerst de ruimte rechts en dan de ruimtes onder en rechtsonder (rechts in figuur 3). Aangezien het vullen van de ruimtes een recursieve stap is, zal algoritme 1 zichzelf recursief aanroepen om de meegegeven ruimtes te vullen. Als de meegegeven ruimtes gevuld zijn, is dit het einde van algoritme 1. Zo niet, maakt het de tegel ongedaan, draait de tegel kwartslag en plaats het opnieuw
linksboven. Indien de ruimtes weer niet gevuld kunnen worden, zet het de tegel terug in de tegelset, pakt de volgende grootste steen en begint het opnieuw. Figuur 4 geeft deze stappenplan systematisch weer. Grootst Grootst e Rechts e tegel tegel Rechts-‐‑ Onder onder Figuur 2. Links de lijnen die ontstaan na het plaatsen van de grootste tegel, en rechts de drie ruimtes die daarna ontstaan. Grootste Grootste Rechts Rechts tegel tegel
Onder
Rechts-‐‑ onder
Onder
Rechts-‐‑ onder
Figuur 3. Links de ruimtes onder en de samengevoegde ruimtes rechts en rechtsonder. Rechts de ruimtes rechts en de samengevoegde ruimtes onder en rechtsonder.
1. 2. 3.
Ga van groot naar klein door tegelset en kies grootste tegel Plaats tegel linksboven If oppervlakte van onder <= oppervlakte van rechts Vul onder, en vul rechts en rechtsonder als één geheel Else Vul rechts, en vul onder en rechtsonder als één geheel 4. Maak tegel ongedaan, flip tegel als eerder niet geflipt en ga terug naar 2 5. Zet tegel terug in tegelset, en ga terug naar 1 Figuur 4. Stappenplan van algoritme 1
Algoritme 2 Algoritme 2 werkt hetzelfde als algoritme 1 op één cruciaal verschil na. Algoritme 1 vult eerst de kleinere oppervlakte en vult daarna de rest (stap 3 in figuur 4). Algoritme 2 daarentegen vult eerst de grotere oppervlakte en vult daarna de rest. Dus het stappenplan van algoritme 2 ontstaat als men bij stap 3 in figuur 4 het “kleiner of gelijk aan”-‐‑teken (<=) verandert in een “groter dan”-‐‑teken (>). De gevolgen van deze “kleine” verandering worden nader besproken.
Resultaten Zowel algoritme 1 als algoritme 2 zijn geprogrammeerd in JAVA en hebben geprobeerd om de 125 problemen op te lossen. Om elk probleem op te lossen hebben beide algoritme maximaal 5 minuten. Indien de 5 minuten zijn overschreven wordt dit gerekend als “niet-‐‑opgelost”. Dit doen we om de tijdsduur voor het oplossen ook te laten meetellen bij het beoordelen. Oplossingen die men vind na langer dan 5 minuten worden gerekend tot onacceptabele oplossingen. Algoritme 1 lost 119 van de 125 op (95,2%) en algoritme 2 lost 94 van de 125 problemen op (75,2%). Dit is een verschil van precies 20 procent, wat gelijk staat een geheel categorie. Figuur 5 geeft het aantal opgeloste problemen weer per categorie. Het is te zien dat beide algoritme ongeveer gelijk scoren bij de eerste twee categorieën. Daarna blijft algoritme 1 ongeveer gelijk, terwijl algoritme 2 steeds slechter presteert naarmate de grootte van de tileset toeneemt. Figuur 6 geeft de gemiddelde tijdsduur weer van de opgeloste problemen per categorie. Weer is te zien dat naarmate de grootte van tileset toeneemt, de tijdsduur om een probleem op te lossen voor algoritme 2 behoorlijk omhoog gaat. De tijdsduur van algoritme 1 om een probleem op te lossen gaat iets omhoog wat begrijpelijk is, aangezien de tileset groter wordt. Ook hier zien we dat algoritme 2 het slechter presteert dan algoritme 1. Met figuur 6 kan ook worden verklaard waarom algoritme 2 bij de laatste categorie zo weinig problemen oplost. Dat komt waarschijnlijk doordat het oplossen bij de grotere tileset de tijdslimiet bereikt wordt.
Conclusie Het is overduidelijk dat deze heuristiek beter werkt met algoritme 1 dan met algoritme 2. Het eerst vullen van de kleinere ruimtes scoort beter dan het eerst vullen van grotere ruimtes. Dit komt omdat er minder combinaties mogelijk zijn om een kleinere ruimte te vullen dan om een grotere ruimte te vullen. Dus men komt er bij algoritme 1 eerder achter zodra een ruimte niet te vullen is en er recursie moet optreden. Bij algoritme 2 zijn er meer combinaties om een grotere ruimte te vullen, dus het heeft langer de tijd nodig om te beoordelen of dat gegeven ruimte te vullen is.
Aantal opgeloste problemen 25 20 Aantal opgeloste problemen
15 Algoritme 1
10
Algoritme 2 5 0
15 tegels 25 tegels 35 tegels 45 tegels 55 tegels Categorie
Figuur 5. Vergelijking van het aantal opgelost problemen per categorie door algoritme 1 en 2.
Tijdsduur 120 100 80 Tijdsduur in seconden 60
Algoritme 1
40
Algoritme 2
20 0
15 tegels 25 tegels 35 tegels 45 tegels 55 tegels Categorie
Figuur 6. Vergelijking van de gemiddelde tijdsduur van de opgeloste problemen per categorie door algoritme 1 en 2.
