The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems

• Autorzy: Cooper James , Nicolescu Radu

Identyfikatory

DOI

10.3233/FI-2019-1760

• Języki publikacji: EN

Abstrakty

EN

The Hamiltonian Cycle Problem (HCP) and Travelling Salesman Problem (TSP) are long-standing and well-known NP-hard problems. The HCP is concerned with finding paths through a given graph such that those paths visit each node exactly once after the start, and end where they began (i.e., Hamiltonian cycles). The TSP builds on the HCP and is concerned with computing the lowest cost Hamiltonian cycle on a weighted (di)graph. Many solutions to these problems exist, including some from the perspective of P systems. For the TSP however, almost all these papers have combined membrane computing with other approaches for approximate solution algorithms, which is surprising given the plethora of P systems solutions to the HCP. A recent paper presented a brute-force style P systems solution to the TSP with a time complexity of O(n²), exploiting the ability of P systems to reduce time complexity in exchange for space complexity, but the resultant system had a fairly high number of rules, around 50. Inspired by this paper, and seeking a more concise representation of an exact brute-force TSP algorithm, we have devised a P systems algorithm based on cP systems (P systems with Complex Objects) which requires five rules and takes n + 3 steps. We first provide some background on cP systems and demonstrate a fast new cP systems method to find the minimum of a multiset, then describe our solution to the HCP, and build on that for our TSP algorithm. This paper describes said algorithms, and provides an example application of our TSP algorithm to a given graph and a digraph variant.

Słowa kluczowe

EN

cP systems; Hamiltonian cycle problem; P systems; prolog terms and unification; travelling salesman problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 2-3
• Strony: 157--180
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Cooper James

• Department of Computer Science, University of Auckland, Auckland, New Zealand

autor

Nicolescu Radu

• Department of Computer Science, University of Auckland, Auckland, New Zealand

Bibliografia

• [1] Martín-Vide C, Păun G, Pazos J, Rodríguez-Patón A. Tissue P systems. Theoretical Computer Science. 2003;296(2):295-326. doi:10.1016/S0304-3975(02)00659-X.
• [2] Pan L, Alhazov A. Solving HPP and SAT by P systems with active membranes and separation rules. Acta Informatica. 2006;43(2):131-145. doi:10.1007/s00236-006-0018-8.
• [3] Song T, Wang X, Zheng H. Time-Free Solution to Hamilton Path Problems Using P Systems with d-Division. Journal of Applied Mathematics. 2013;2013:1-7. doi:10.1155/2013/975798.
• [4] Chen H, He Z. A uniform solution to HPP in terms of membrane computing. In: International Conference on Artificial Intelligence and Computational Intelligence, AICI 2009. vol. 5855 LNAI. Shanghai, China: Springer Berlin Heidelberg; 2009. p. 59-68. doi:10.1007/978-3-642-05253-8_7.
• [5] Tagawa H, Fujiwara A. Solving SAT and Hamiltonian cycle problem using asynchronous P systems. IEICE Transactions on Information and Systems. 2012; E95-D(3):746-754. doi:10.1587/transinf.E95.D.746.
• [6] Xue J, Liu X. Solving directed Hamilton path problem in parallel by improved SN P system. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2013;7719 LNCS:689-696. doi:10.1007/978-3-642-37015-1_60.
• [7] Jiménez MJP, Jiménez Á R, Caparrini FS. Complexity Classes in Cellular Computing with Membranes. Natural Computing. 2003 sep;2(3):265-285. doi:10.1023/A:1025449224520.
• [8] Mutyam M, Krithivasan K. P Systems with Membrane Creation: Universality and Efficiency. Machines, Computations, and Universality: Third International Conference, MCU 2001 Chişinău, Moldova, May 23-27, 2001, Proceedings. 2001;2055:276-287. doi:10.1007/3-540-45132-3_19.
• [9] Smith SL, Imeson F. GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem. Computers & Operations Research. 2017;87:1-19. doi:10.1016/j.cor.2017.05.010.
• [10] Ezugwu AES, Adewumi AO. Discrete Symbiotic Organisms Search Algorithm for Travelling Salesman Problem. Expert Systems with Applications. 2017;doi:10.1016/j.eswa.2017.06.007.
• [11] Cook WJ. In Pursuit of the Traveling Salesman; Mathematics at the Limits of Computation. Princeton University Press; 2012. Available from: http://www.jstor.org/stable/j.ctt7t8kc.
• [12] Applegate DL, Bixby RE, Chvatl V, Cook WJ. The Traveling Salesman Problem; A Computational Study. Princeton University Press; 2006. Available from: http://www.jstor.org/stable/j.ctt7s8xg.
• [13] Nishida TY. Membrane Algorithms. Membrane Computing: 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers. Berlin, Heidelberg: Springer Berlin Heidelberg; 2006. p. 55-66. doi:10.1007/11603047_4.
• [14] Manalastas P. Membrane Computing with Genetic Algorithm for the Travelling Salesman Problem. Theory and Practice of Computation: 2nd Workshop on Computation: Theory and Practice, Manila, The Philippines, September 2012, Proceedings. Tokyo: Springer Japan; 2013. p. 116-123. doi:10.1007/978-4-431-54436-4_9.
• [15] He J, Xiao J, Shao Z. An adaptive membrane algorithm for solving combinatorial optimization problems. Acta Mathematica Scientia. 2014;34(5):1377-1394. doi:10.1016/S0252-9602(14)60090-4.
• [16] Zhang G, Cheng J, Gheorghe M. A membrane-inspired approximate algorithm for traveling salesman problems. Romanian Journal of Information Science and Technology. 2011;14(1):3-19. Available from: https://www.researchgate.net/publication/264882106_A_membrane-inspired_approximate_algorithm_for_traveling_salesman_problems.
• [17] Song X, Wang J. An Approximate Algorithm Combining P Systems and Active Evolutionary Algorithms for Traveling Salesman Problems. International Journal of Computers, Communications & Control. 2015;10(1):89-99. doi:10.15837/ijccc.2015.1.1567.
• [18] He J, Zhang K. A Hybrid Distribution Algorithm Based on Membrane Computing for Solving the Multiobjective Multiple Traveling Salesman Problem. Fundamenta Informaticae. 2015;136(3):199-208. doi:10.3233/FI-2015-1151.
• [19] Chen HZ, Lu JY, Wang YX. An approximate algorithm based on membrane computing for traveling salesman problems. Journal of Harbin Institute of Technology (New Series). 2011;18(SUPPL. 1):347-354.
• [20] Guo P, Dai Y. A P System for Travelling Salesman Problem. In: Proceedings of the 18th International Conference on Membrane Computing (CMC18). International Membrane Computing Society; 2017. p. 147-165. Available from: http://computing.brad.ac.uk/cmc18/files/CMC18-Proceedings.pdf.
• [21] Păun G. P Systems with Active Membranes: Attacking NP Complete Problems. Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland; 1999. Available from: https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/.
• [22] Păun G. 2. In: Păun G, editor. Prerequisites. Membrane Computing: An Introduction. Berlin, Heidelberg: Springer Berlin Heidelberg; 2002. p. 7-50. doi:10.1007/978-3-642-56196-2_2.
• [23] Song B, Zhang C, Pan L. Tissue-like P systems with evolutional symport/antiport rules. Information Sciences. 2017 feb;378:177-193. doi:10.1016/j.ins.2016.10.046.
• [24] Nicolescu R. Most Common Words A cP Systems Solution. In: Gheorghe M, Rozenberg G, Salomaa A, Zandron C, editors. Membrane Computing: 18th International Conference. Bradford, UK: Springer International Publishing; 2018. p. 214-229. doi:10.1007/978-3-319-73359-3.
• [25] Păun G, Rozenberg G. One. In: Păun G, Rozenberg G, Salomaa A, editors. An Introduction to and an Overview of Membrane Computing. The Oxford Handbook of Membrane Computing. New York, NY, USA: Oxford University Press; 2009. p. 1-27.
• [26] Nicolescu R, Ipate F, Wu H. Programming P Systems with Complex Objects. Membrane Computing: 14th International Conference, CMC 2013, Chişinău, Republic of Moldova, August 20-23, 2013, Revised Selected Papers. Berlin, Heidelberg: Springer Berlin Heidelberg; 2014. p. 280-300. doi:10.1007/978-3-642-54239-8_20.
• [27] Nicolescu R, Wu H. Complex Objects for Complex Applications. Romanian Journal of Information Science and Technology. 2014;17(1):46-62.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).