A Novel Approach of the Shortest Path Problem Using P System

Einallah Salehi

doi:doi:10.11648/j.ijiis.20170603.11

| Peer-Reviewed

A Novel Approach of the Shortest Path Problem Using P System

Einallah Salehi

Published in International Journal of Intelligent Information Systems (Volume 6, Issue 3)

Received: 9 June 2017 Accepted: 30 June 2017 Published: 20 July 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Einallah Salehi

Department of Computer Science, Malayer Branch, Islamic Azad University, Malayer, Iran

Download PDF

Sections

Plain Text BibTeX RIS

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