An Improved Dynamic Programming Algorithm for Bitonic TSP
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.
dynamic programming bitonic TSP optimal substructure space complexity
LI Jian
Foundation Department The PLA Foreign Languages University Luoyang, China
国际会议
太原
英文
24-27
2013-04-06（万方平台首次上网日期，不代表论文的发表时间）