| Peer-Reviewed

A Novel Approach of the Shortest Path Problem Using P System

Received: 9 June 2017     Accepted: 30 June 2017     Published: 20 July 2017
Views:       Downloads:
Abstract

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.

Published in International Journal of Intelligent Information Systems (Volume 6, Issue 3)
DOI 10.11648/j.ijiis.20170603.11
Page(s) 25-35
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2017. Published by Science Publishing Group

Keywords

Breadth-First Search, Division Rule, P System, Shortest Path Problem, Time Complexity

References
[1] Păun, G., Computing with Membranes. Journal of Computer and System Sciences, 2000. 61(1): p. 108-143.
[2] Păun, G., Membrane computing: an introduction. 2012: Springer Science & Business Media.
[3] Păun, G., P systems with active membranes: attacking NP complete problems. Journal of Automata, Languages and Combinatorics, 2001. 6(1): p. 75-90.
[4] 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.
[5] 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.
[6] Frisco, P., M. Gheorghe, and M. J. Pérez-Jiménez, Applications of Membrane Computing in Systems and Synthetic Biology. 2014: Springer.
[7] Peng, H., et al., An automatic clustering algorithm inspired by membrane computing. Pattern Recognition Letters, 2015. 68: p. 34-40.
[8] Chen, H., et al., On trace languages generated by (small) spiking neural P systems. Theoretical Computer Science, 2016.
[9] Wang, J., P. Shi, and H. Peng, Membrane computing model for IIR filter design. Information Sciences, 2016. 329: p. 164-176.
[10] 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.
[11] 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.
[12] Gutiérrez-Naranjo, M. A. and M. J. Pérez-Jiménez, Implementing local search with Membrane Computing. 2011.
[13] 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.
[14] 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.
[15] 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.
[16] Nicolescu, R. and H. Wu, New solutions for disjoint paths in P systems. Natural Computing, 2012. 11(4): p. 637-651.
[17] 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.
[18] Russell, S. J. and P. Norvig, Artificial Intelligence: A Modern Approach(2nd Edition) 2ed. 2002: Prentice Hall.
[19] Even, S. and E. Guy, Graph algorithms. 2nd ed. 2012, Cambridge, NY: Cambridge University Press. xii, 189 p.
[20] 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.
Cite This Article
  • APA Style

    Einallah Salehi. (2017). A Novel Approach of the Shortest Path Problem Using P System. International Journal of Intelligent Information Systems, 6(3), 25-35. https://doi.org/10.11648/j.ijiis.20170603.11

    Copy | Download

    ACS Style

    Einallah Salehi. A Novel Approach of the Shortest Path Problem Using P System. Int. J. Intell. Inf. Syst. 2017, 6(3), 25-35. doi: 10.11648/j.ijiis.20170603.11

    Copy | Download

    AMA Style

    Einallah Salehi. A Novel Approach of the Shortest Path Problem Using P System. Int J Intell Inf Syst. 2017;6(3):25-35. doi: 10.11648/j.ijiis.20170603.11

    Copy | Download

  • @article{10.11648/j.ijiis.20170603.11,
      author = {Einallah Salehi},
      title = {A Novel Approach of the Shortest Path Problem Using P System},
      journal = {International Journal of Intelligent Information Systems},
      volume = {6},
      number = {3},
      pages = {25-35},
      doi = {10.11648/j.ijiis.20170603.11},
      url = {https://doi.org/10.11648/j.ijiis.20170603.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijiis.20170603.11},
      abstract = {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.},
     year = {2017}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - A Novel Approach of the Shortest Path Problem Using P System
    AU  - Einallah Salehi
    Y1  - 2017/07/20
    PY  - 2017
    N1  - https://doi.org/10.11648/j.ijiis.20170603.11
    DO  - 10.11648/j.ijiis.20170603.11
    T2  - International Journal of Intelligent Information Systems
    JF  - International Journal of Intelligent Information Systems
    JO  - International Journal of Intelligent Information Systems
    SP  - 25
    EP  - 35
    PB  - Science Publishing Group
    SN  - 2328-7683
    UR  - https://doi.org/10.11648/j.ijiis.20170603.11
    AB  - 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.
    VL  - 6
    IS  - 3
    ER  - 

    Copy | Download

Author Information
  • Department of Computer Science, Malayer Branch, Islamic Azad University, Malayer, Iran

  • Sections