Research On P System For Solving HCP And TSP Problems

Membrane computing(also known as P system)is a new branch of natural computing,which is a new computational model abstracted from natural cells.Since Romanian professor Gheorghe P?un proposed the concept of membrane computing,membrane computing has gained much attention and research around the world.Compared with the traditional computer based on Von Neumann model,the highly parallel characteristics of membrane computing,makes the membrane computing greatly exceeds the traditional computer,thus membrane computing has a great advantage on solving NP-complete problems.Hamiltonian cycle problem and traveling salesman problem are two of the most classic NP-hard problem in graph theory.Although they have been proposed for a long time,we still can not solve them in polynomial time.As a branch of natural computing,membrane computing has a high degree of parallelism,however,there are few studies on these two problems.Therefor,this paper studies the P system to solve the Hamiltonian cycle problem and traveling salesman problem,not only expands the scope of the use of P system in the field of graph theory,but also has a certain research value on the practical application of P system.Based on the analysis and research of the Hamiltonian cycle problem and traveling salesman problem,this paper designed two P system for solving these two graph theory problem.The research work of this paper is summarized as follows:(1)According to characteristics of the Hamiltonian cycle problem,this paper designs a specific algorithm for solving Hamiltonian cycle problem,which lays the foundation for the realization of the P system.(2)According to characteristics of the traveling salesman problem,this paper designs a specific algorithm for solving traveling salesman problem,which lays the foundation for the realization of the P system.(3)Three P system components are designed to solve hamiltonian path problem,hamiltonian cycle problem and travelling salesman problem.(4)According to these P system components,it designed a P system which can solve the all solutions of Hamiltonian cycle problem,and an specific example and a computer simulation program to validate the effectiveness and feasibility of the P system.(5)According to these P system components,it designed a P system which can solve the all solutions of traveling salesman problem,and an specific example and a computer simulation program to validate the effectiveness and feasibility of the P system.In this paper,the research of the P system on the Hamiltonian cycle problem and the traveler salesman problem not only extends the research on the graph theory in the P system,but also provides a reference for the use of the P system to solve other NP-hard problems.