Question: The traveling salesman problem studied in several chapters of this book, amounts to finding the shortest Hamiltonian path in an undirected graph, where the edges are provided with lengths.
- Reduce the Hamiltonian path problem to the traveling salesman problem, write a DNA computing algorithm to solve the TSP problem and describe how each of the steps can be performed using DNA strands and manipulation techniques.
- Discuss the computational complexity of your DNA solution to the TSP.