Combinatorial Optimization

Combinatorial Optimization

1. TSP Using Dynamic Programming

2. TSP Without Dynamic Programming

3. Sparse Graphs For 2 cities

4. With Dynamic Programming

5. Without Dynamic Programming

6. Dense Graphs For 6 cities

7. With Dynamic Programming

8. Without dynamic Programming

9. Conclusion When we have a limited set of targets to meet, Tsp using Dynamic Programming is efficient. But when we have a considerable more number of targets this concept is not much useful.

10. Various scenarios

11. Connected Graph

12. Complete Graph

13. Discrete Optimization". Elsevier. Jump up Jump up Cook, William. "Optimal TSP Tours". University of Waterloo. Fredman , M. L.; Willard, D. E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences Karger , David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery Applegate, D. L.; Bixby, R. M.; Chvátal , V.; Cook, W. J. (2006), The Traveling Salesman Problem Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem", J. Assoc. Comput . Mach.