Volume 6, Issue 3, June 2017, Page: 25-35
A Novel Approach of the Shortest Path Problem Using P System
Einallah Salehi, Department of Computer Science, Malayer Branch, Islamic Azad University, Malayer, Iran
Received: Jun. 9, 2017;       Accepted: Jun. 30, 2017;       Published: Jul. 20, 2017
DOI: 10.11648/j.ijiis.20170603.11      View  2361      Downloads  109
Membrane Computing is inspired from biological cell activities as a new distributed parallel computational framework, which can be used for decreasing the time complexity of problems with high execution time. Since the usual way to reduce the time complexity of Artificial Intelligence (AI) problems is using parallel algorithms, Membrane Computing can be extensively applied. On the other hand, shortest path problem (SPP) is the most broadly method to solve the problems in AI. There have been a variety of algorithms presented, that could find a solution in a desirable time but usually are not accurate, or they are accurate but they are too slow. In Membrane Computing technique, the normal way for reducing the time complexity is using P system with active membranes that the number of membranes increases during the computation; thus, the time is traded against the space. This paper presents the first Membrane Computing technique for solving the SPP using P system with membranes division by a breadth first exploring on a grid. The theorems show the run times for breadth-first search and SPP are significantly reduced.
Breadth-First Search, Division Rule, P System, Shortest Path Problem, Time Complexity
To cite this article
Einallah Salehi, A Novel Approach of the Shortest Path Problem Using P System, International Journal of Intelligent Information Systems. Vol. 6, No. 3, 2017, pp. 25-35. doi: 10.11648/j.ijiis.20170603.11
Copyright © 2017 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Păun, G., Computing with Membranes. Journal of Computer and System Sciences, 2000. 61(1): p. 108-143.
Păun, G., Membrane computing: an introduction. 2012: Springer Science & Business Media.
Păun, G., P systems with active membranes: attacking NP complete problems. Journal of Automata, Languages and Combinatorics, 2001. 6(1): p. 75-90.
Krishna, S. N. and R. Rama, A variant of P systems with active membranes: Solving NP-complete problems. Romanian Journal of Information Science and Technology, 1999. 2(4): p. 357-367.
Mutyam, M. and K. Krithivasan, P Systems with Membrane Creation: Universality and Efficiency, in Machines, Computations, and Universality, M. Margenstern and Y. Rogozhin, Editors. 2001, Springer Berlin Heidelberg. p. 276-287.
Frisco, P., M. Gheorghe, and M. J. Pérez-Jiménez, Applications of Membrane Computing in Systems and Synthetic Biology. 2014: Springer.
Peng, H., et al., An automatic clustering algorithm inspired by membrane computing. Pattern Recognition Letters, 2015. 68: p. 34-40.
Chen, H., et al., On trace languages generated by (small) spiking neural P systems. Theoretical Computer Science, 2016.
Wang, J., P. Shi, and H. Peng, Membrane computing model for IIR filter design. Information Sciences, 2016. 329: p. 164-176.
Song, B., T. Song, and L. Pan, A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science, 2017. 27(1): p. 17-32.
Gutiérrez-Naranjo, M. and M. Pérez-Jiménez, Depth-First Search with P Systems, in Membrane Computing, M. Gheorghe, et al., Editors. 2011, Springer Berlin Heidelberg. p. 257-264.
Gutiérrez-Naranjo, M. A. and M. J. Pérez-Jiménez, Implementing local search with Membrane Computing. 2011.
Gutiérrez-Naranjo, et al. Solving the N-Queens puzzle with P systems. in 7th Brainstorming Week on Membrane Computing. 2009. Sevilla, España: Fénix Editora.
Michael J. Dinneen, Y. -B. K., and Radu Nicolescu, Edge- and node-disjoint paths in P systems, in Electronic Proceedings in Theoretical Computer Science 2010. p. 121-141.
Nicolescu, R. and H. Wu, BFS Solution for Disjoint Paths in P Systems, in Unconventional Computation, C. Calude, et al., Editors. 2011, Springer Berlin Heidelberg. p. 164-176.
Nicolescu, R. and H. Wu, New solutions for disjoint paths in P systems. Natural Computing, 2012. 11(4): p. 637-651.
Salehi, E., S. M. Shamsuddin, and K. Nemati, A Linear Time Complexity of Breadth-First Search Using P System with Membrane Division. Mathematical Problems in Engineering, 2013. 2013: p. 11.
Russell, S. J. and P. Norvig, Artificial Intelligence: A Modern Approach(2nd Edition) 2ed. 2002: Prentice Hall.
Even, S. and E. Guy, Graph algorithms. 2nd ed. 2012, Cambridge, NY: Cambridge University Press. xii, 189 p.
Díaz-Pernil, D., et al., A P-Lingua Programming Environment for Membrane Computing, in Membrane Computing, D. Corne, et al., Editors. 2009, Springer Berlin Heidelberg. p. 187-203.
Browse journals by subject