The traveling salesman problem involves finding the shortest route visiting a set of locations. For 20 addresses, the number of possible routes exceeds 60 quadrillion, illustrating the combinatorial explosion where computational complexity grows factorially with each added point.
Traditional algorithms, such as the Held-Karp approach, solve this efficiently by storing intermediate results. On a standard laptop, Held-Karp solves a 12-point route in 17 milliseconds, whereas brute-force search takes 42 seconds. The performance gap widens significantly as the number of points increases.
A 2009 study by Baumgardner et al. explored using E. coli as a biological computer to solve Hamiltonian path problems. The method uses plasmids as data storage and Hin-recombinase enzymes to shuffle DNA segments representing graph edges, while fluorescent proteins act as indicators for valid solutions.
While biological computing offers logarithmic time scaling due to exponential bacterial reproduction, it faces physical constraints. Solving a 20-city route would require 4 cubic meters of bacterial culture, whereas a standard Python script solves the same problem in 22 seconds.
The exponential growth of a bacterial population requires a proportional increase in resources like nutrients. Although the time complexity appears logarithmic, the physical volume of the required biological system grows exponentially, making it impractical for larger datasets compared to silicon-based computing.
