算法设计大作业—求解Tsps问题.doc

基于贪心算法求解TSP问题 一TSP问题 TSP问题Travelling Salesman Problem即旅行商问题又译为旅行推销员问题货郎担问题是数学领域中著名问题之一假设有一个旅行商人要拜访n个城市他必须选择所要走的路径路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市路径的选择目标是要求得的路径路程为所有路径之中的最小值 TSP问题是一个组合优化问题该问题可以被证明具有NPC计