×

zbMATH — the first resource for mathematics

A genetic algorithm for the picture maze generation problem. (English) Zbl 1458.68144
Summary: A picture maze is a maze puzzle that reveals a hidden picture when the solution path is filled. The picture maze generation problem (PMGP) consists in generating a picture maze whose solution path draws the shape most similar to a given raster image. The PMGP can be formulated as the longest path problem (LPP) on grid graphs, and we propose a genetic algorithm (GA) for this problem. In our formulation, we optimize the start and exit positions simultaneously as well as the solution path. To construct an effective GA, we employ edge assembly crossover (EAX), which is known as a very effective crossover operator for the traveling salesman problem (TSP). However, because of the difference between the two problems, we adapt EAX to the PMGP in a novel manner. The proposed GA can generate satisfactory picture mazes in 17s for complicated raster images with sizes up to \(55 \times 105\).
MSC:
68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Björklund, A.; Husfeldt, T., Finding a path of superlogarithmic length, SIAM J. Comput., 32, 6, 1395-1402 (2003) · Zbl 1041.68066
[2] Bulterman, R. W.; van der Sommen, F. W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A. J.M.; Feijen, W. H.J., On computing a longest path in a tree, Inf. Process. Lett., 81, 2, 93-96 (2002) · Zbl 1032.68671
[3] Gabow, H. N., Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput., 36, 6, 1648-1671 (2007) · Zbl 1135.68044
[4] Gabow, H. N., Nie, S., 2008. Finding long paths, cycles and circuits. Proceedings of the 19th Annual International Symposium on Algorithms and Computation, S-H Hong. In: Nagamochi, H., Fukunaga, T. (Eds.), Lecture Notes in Computer Science 5369. Springer-Verlag, pp. 752-763. · Zbl 1183.05078
[5] Garey, M. R.; Johnson, D. S., Computers and Intractability: A guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[6] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math., 6, 2, 270-273 (1993) · Zbl 0773.05071
[7] Hamada, K., A picturesque maze generation algorithm with any given endpoints, J. Inf. Process., 21, 3, 393-397 (2013)
[8] In Japanese
[9] Lecture Notes in Computer Science 5734, Springer-Verlag · Zbl 1250.68128
[10] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamilton paths in grid graphs, SIAM J. Comput., 11, 4, 676-686 (1982) · Zbl 0506.05043
[11] Karger, D.; Motwani, R.; Ramkumar, G., On approximating the longest path in a graph, Algorithmica, 18, 421-432 (1993)
[12] Keshavarz-Kohjerdi, F.; Bagheri, A., An efficient parallel algorithm for the longest path problem in meshes, J. Supercomput., 65, 2, 723-741 (2013)
[13] Keshavarz-Kohjerdi, F.; Bagheri, A.; Asgharian-Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 210-217 (2010) · Zbl 1237.05115
[14] Kurokawa, T., Picture maze generation by successive insertion of path segment, Br. J. Math. Comput. Sci., 4, 24, 3444-3463 (2014)
[15] Mertzios, G. B.; Corneil, D. G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM J. Discrete Math., 26, 3, 940-963 (2012) · Zbl 1256.05237
[16] Mochizuki, S., 2006. Ukidashi meiro 1, gakken. In Japanese.
[17] Morgan Kaufmann
[18] Nagata, Y.; Kobayashi, S., A powerful genetic algorithm using edge assembling crossover for the traveling salesman problem, Inf. J. Comput., 25, 2, 346-363 (2013)
[19] Okamoto, Y., Uehara, R., 2009. How to make a picturesque maze. Proceedings of the 21th Canadian Conference on Computational Geometry, 137-140.
[20] Lecture Notes in Computer Science 7298, Springer-Verlag.
[21] Picture, This Mazes by Conceptis Puzzles (2005), Sterling Publishing
[22] Portugal, D.; Antunes, C. H.; Rocha, R., A study of genetic algorithms for approximating the longest path in generic graphs, Proceedings of the of the IEEE International Conference on Systems, Man and Cybernetics, 2539-2544 (2010), IEEE: IEEE Piscataway
[23] Scutellà, M. G., An approximation algorithm for computing longest paths, Eur. J. Operat. Res., 148, 3, 584-590 (2003) · Zbl 1035.90075
[24] Stern, R.; Kiesel, S.; Puzis, R.; Felner, A.; Wheeler, W., Max is more than min: Solving maximization problems with heuristic search, (Edelkamp, S.; Bartak, R., Proceedings of the Seventh Annual Symposium on Combinatorial Search (2014), AAAI Press), 4324-4330
[25] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Int. J. Found. Comput. Sci., 18, 5, 911-930 (2007) · Zbl 1202.68291
[26] In Japanese
[27] Zhang, W.-Q.; Liu, Y.-J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 5340-5350 (2011) · Zbl 1222.68089
[28] Zhanga, Z.; Li, H., Algorithms for long paths in graphs, Theoret. Comput. Sci., 377, 25-34 (2007) · Zbl 1117.68057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.