Abstract
The objective is to find a Cellular Automata (CA) rule that is able to cover a 2d array of cells by a minimum number of so-called “Domino Tiles”. The aimed patterns are called min patterns. Two probabilistic CA rules were designed using templates, small matching patterns. For each of the 12 domino tile pixels a template is declared. If no template is matching then a noise is injected in order to drive the evolution to a valid (full covering) pattern. The First Rule shows the basic mechanism of searching coverings. It evolves very fast stable sub–optimal coverings, starting from a random configuration. The Second Rule is designed in a way that it can find min patterns with a high expected value. The longer the evolution time, the more probably a min pattern appears.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Snyder, L.V.: Covering Problems. In: Foundations of location analysis, 2011, pp. 109–135. Springer, Boston, MA (2011)
Hakimi, S.L.: Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Op. Res. 13, 462–475 (1965)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs, Pure and applied mathematics 208, Dekker (1998)
Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R.: Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Comput. Op. Res. 33, 3520–3534 (2006)
Richter, S., Helmert, M., Gretton, C.: A stochastic local search approach to vertex cover. In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS (LNAI), vol. 4667, pp. 412–426. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74565-5_31
Mousavian, A., Rezvanian, A., Meybodi, M.R.: Cellular learning automata based algorithm for solving minimum vertex cover problem. In: 22nd Iranian Conference on Electrical Engineering (ICEE), pp. 996–1000 (2014)
Church, R.L., ReVelle, C.S.: Theoretical and computational links between the p-median, location set-covering, and the maximal covering location problem. Geogr. Anal. 8(4), 406–415 (1976)
Mehrez, A.: Facility Location Problems, Review, Description, and Analysis. Geogr. Res. Forum 8, 113–129 (2016)
Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discret. Comput. Geom. 26(4), 573–590 (2001)
Hoffmann, R., Désérable, D., Seredyński, F.: A probabilistic cellular automata rule forming domino patterns. In: Malyshkin, V. (ed.): PaCT 2019. LNCS, vol. 11657. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25636-4
Hoffmann, R., Seredyński, F.: Covering the space with sensor tiles. In: Gwizdałła, T.M., Manzoni, L., Sirakoulis, G.C., Bandini, S., Podlaski, K. (eds.) Cellular Automata. ACRI 2020. Lecture Notes in Computer Science, vol. 12599, pp. 156–168. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-69480-7_16
Hoffmann, R., Désérable, D., Seredyński, F.: A cellular automata rule placing a maximal number of dominoes in the square and diamond. J. Supercomput. 77(8), 9069–9087 (2021). https://doi.org/10.1007/s11227-020-03549-8
Achasova, S., Bandman, O., Markova, V., Piskunov, S.: Parallel Substitution Algorithm: Theory and Application. World Scientific, Singapore, New Jersey, London, Hong Kong (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Hoffmann, R., Désérable, D., Seredyński, F. (2021). Minimal Covering of the Space by Domino Tiles. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2021. Lecture Notes in Computer Science(), vol 12942. Springer, Cham. https://doi.org/10.1007/978-3-030-86359-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-030-86359-3_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86358-6
Online ISBN: 978-3-030-86359-3
eBook Packages: Computer ScienceComputer Science (R0)