The Travelling Salesman Problem in cP Systems

Abstract

The Travelling Salesman Problem (TSP) is a long-standing and well-known NP-hard problem, concerned with computing the lowest cost Hamiltonian cycle on a weighted graph. Many solutions to the problem exist, including some from the perspective of P Systems, almost all of which have combined membrane computing with other approaches for approximate solution algorithms. A recent paper presented a brute-force style P Systems solution to the TSP, exploiting the ability of P Systems to reduce time complexity in exchange for space complexity, but the resultant system had a relatively high number of rules.