An Improved Dynamic Programming Algorithm for Bitonic TSP
- 10.2991/isccca.2013.7How to use a DOI?
- dynamic programming, bitonic TSP, optimal sub-structure, space complexity
This paper puts forward an improved dynamic programming algorithm for bitonic TSP and it proves to be correct. Divide the whole loop into right-and-left parts through analyzing the key point connecting to the last one directly; then construct a new optimal sub-structure and recursion. The time complexity of the new algorithm is O(n2) and the space complexity is O(n); while both the time and space complexities of the classical algorithm are O(n2). Experiment results showed that the new algorithm not only reduces the space requirement greatly but also increases the computing speed by 2-3 times compared with the classical algorithm.
- © 2013, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Jian Li PY - 2013/02 DA - 2013/02 TI - An Improved Dynamic Programming Algorithm for Bitonic TSP BT - Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA 2013) PB - Atlantis Press SP - 24 EP - 27 SN - 1951-6851 UR - https://doi.org/10.2991/isccca.2013.7 DO - 10.2991/isccca.2013.7 ID - Li2013/02 ER -