| 基于树算法的TSP问题的一个界 |
| |
| 引用本文： | 杨宏,唐艳,叶笑飞. 基于树算法的TSP问题的一个界[J]. 物流技术, 2008, 27(11) |
| |
| 作者姓名： | 杨宏 唐艳 叶笑飞 |
| |
| 作者单位： | 1. 复旦大学,管理学院,上海,200433
2. 江西蓝天学院,江西南昌,330098 |
| |
| 摘 要： | 对于满足三角不等式的TSP问题,已经有了多种算法,对于我们已经知道的树算法而言,一般文献上都已经证明为一个3/2算法,但本文通过分析和证明,得出了该算法的一个更小界:3/2-3/2n。
|
| 关 键 词： | TSP(旅行商问题) 算法 上界 |
A Bound for Metric Traveling Salesman Problem under Christofides'Algorithm |
| |
| YANG Hong,TANG Yan,YE Xiao-fei. A Bound for Metric Traveling Salesman Problem under Christofides'Algorithm[J]. Logistics Technology, 2008, 27(11) |
| |
| Authors: | YANG Hong TANG Yan YE Xiao-fei |
| |
| Abstract: | For the metric TSP(Traveling Salesman Problem),there are many algorithms.It is known that the bound based on Christofides' algorithm is 3/2.However,the paper analyzes and proves an approximate ratio 3/2?3/2n for metric TSP under Christofides' algorithm. |
| |
| Keywords: | TSP algorithm bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
