论文研究 旅行商问题的N维空间联通图算法与分析.pdf

旅行商问题（Traveling Salesman Problem，TSP）是组合优化中典型的NP难问题之一。和现有算法的基于局部分析或通过反复迭代逐步达到满意解的方式不同，作者首次提出了在N维欧氏空间Rn中求解TSP问题的N维空间联通图算法（Rn-Connectivity Map Algorithm，nDCM Algorithm）。该算法根据R2中n点（v1（x11，x12），v2（x21，x22），…，vn（xn1，xn2））之间的距离关系（dist2ij）n×n，将它们转换Rn中的点（v1（x11，x12，…，x1n），v2（x21，x22，…，x2n），…，vn（xn1，xn2，…，xn