Analysis of state space search algorithms
Núñez Cárdenas, Felipe de Jesús
2015
A.J. Bagnall, Z.V. Zatuchna, On the Classification of Maze Problems, Applications of Learning Classifier Systems, Studies in, Bull, Springer, pp. 307-37, 2005. Applications of Learning Classifier Systems, Studies in, Bull, Springer, pp. 307-316, 2005.Tomas M. V.T. ?Generation and Expansion of Mazes, Master Thesis, CITIS-UAEH, Pachuca de Soto,Hidalgo, Mexico, December 2007.Dijkstra E. W.., A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, Vol. 1, pp.269-271, 1959.Even S., Chapter 3: Depth-First Search, Technion Israel Institute of Technology January 1, 2003.Goodrich M. T. and Tamassia R. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., Section 13.7.1: Kruskal's Algorithm, pp.632, 2006.Harell D., ?Graph Drawing by High-Dimensional Embedding?, Journal of Graph Algorithms and Applications, http://jgaa.info/ vol. 8, no. 2, pp. 195?214 (2004).Johonsonbaugh R., ?Discrete Mathematics?, Prentice Hall, 6th Edition, 2005.Molina V. J., Torres P. C., Restrepo P. C., "Artificial intelligence techniques for solving mazes of unknown structure", Scientia et Technica Year XIV, No 39, Universidad Tecnologica de Pereira, ISSN: 012221701, 2008.Moore E. F., "The Shortest Path Through a Maze", Annals of Computation Laboratory of Harvard University,Harvard University Press, vol. 30, pp. 285-292,1959.Nayfeth B., Cellular Automata for Solving Mazes, Doctor Dobb?s Journal, February 1993.Palma M. and Roque M. Morales, Artificial Intelligence: Techniques, Methods and Applications, Mc Graw Hill, 2008, chapter 8.Rubin F., The Lee Path Connection Algorithm, IEEE, Vol. c-23, No. 9, September 1974.Sedgewick R., Algorithms (Third edition) in Java Parts Graph Algorithms With Java, consulting by Machael Schildlowsky, 2003.Sheldon A. B., A Modification of Lee's Algorithm, IEEE, Transactions on Electronic Computers, February, 1967.Tamassia M. T. and Goodrich R..,Data Structures and Algorithms in JAVA, 2nd Edition, CECSA, 2002.Waite M. and Lafore R., Data Structures & Algorithms in JAVA, Signature Series, 1998Weiss M. A., Data Structures in JAVA, compatible with JAVA 2, Pearson Addison Wesley, 2000.http://www.policyalmanac.org/games/articulo1.htm. Accessed on: 14/01/2014
Abstract
A description of the search algorithms applied in grid and graph type problems, with the objective of finding a path connecting two points within a search space, is made. The behavior of the following algorithms is visualized graphically: DFS, BFS, Nayfeth and S Star. These algorithms are used in path planning and route optimization in artificial intelligence. Likewise, an internal representation of the associated graph that has a labyrinth is made.
