贪心法求解TSP问题
一目的
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。
二需求分析
1、问题描述
TSP（Traveling Salesman Problem ）是指：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
2、解法分析
采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。
3、功能要求
输入城市的数量和城市间的距离，要求输入的为整数。结果为输出最短路径和遍历的最短距离，要求为整数。
三概要设计
1、为便于查找离某顶点最近的邻接点，采用邻接矩阵存储该图
算法描述如下：
(1).任意选择某个顶点i作为出发点；
(2).执行下述过程，直到所有顶点都被访问：
(3).i=最后一个被访问的顶点；
(4).在顶点i的邻接点中查找距离顶点i最近的未被访问的邻接点j；
(5).访问顶点j；
(6).从最后一个访问的顶点直接回到出发点i。
2、最近邻点策略
从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市，具体求解过程举例如下：
3、程序设计组成框图:
TSP 输入城市的数量与各城市之间的距离
循环遍历找到与起始城市最近的城市，用flag[]保存该城市序号，用min[]保存最短路径
输出flag[],得到最佳路径
用sum+=min[]求出最短路径
4、流程图：
5、方法与数据解释：
public void initDistance()
方法作用：存储个城市间的距离，及城市的数目。
public void sum()
方法作用：求各个城市间的最短路径和，并且记录下最佳的旅行路径。
每次都要起初的最小距离min[i] = 99999去和临近的城市去比较距离
min[i] >= distance[flag[k]][j]，这样min[i]肯定会被覆盖，此时再根据for（j++）循环逐次比较，得出最小的min[i]，用flag[k+1]去记下这个城市的编号。再用for循环，输出最佳路径flag[]。
public static void main(String[] args) {}
方法作用：主函数，在主函数中调用各种方法。
cityNum：城市数量；
distance[][]：储存的各个城市之间的距离；
min[]：最短路径；
flag[] ：城市编号。
四详细设计
import java.util.Scanner;
public class Tsp {
int cityNum;
int[][] distance = new int[10][10];
int min[] = new int[10];
int flag[] = new int[10];
public void initDistance(){
System.out.println("请输入城市的数目");
Scanner input = new Scanner(System.in);
cityNum = input.nextInt();
for (int i = 0; i < cityNum; i++)
{
for (int j = 0; j < cityNum; j++)
{
System.out.println("请输入第" + i + "城市到第" + j + "城市之间的距离");
distance[i][j] = input.nextInt();
}
}
int count = 0;
for (int i = 0; i < cityNum; i++)
{
for (int j = 0; j < cityNum; j++)
{
System.out.print(distance[i][j]);
count++;
if (count % cityNum == 0)
{
System.out.println();
}
}
}
}
public void sum() {
int k = 0;
int x = 0;
flag[0] = 0;
for (int i = 0; i < cityNum - 1; i++)
{
min[i] = 99999;
for (int j = 0; j < cityNum; j++)
{
if (min[i] >= distance[flag[k]][j])
{
min[i] = distance[flag[k]][j];
flag[k + 1] = j;
}
}
k++;
x = 0;
//对称的点变成99999，防止往回遍历。
while ((k - x) != 0)
{
distance[flag[k]][flag[k - x - 1]] =99999;
x++;
}
}
System.out.println("最优路径：");
for (int i = 0; i < cityNum; i++)
{
System.out.print(flag[i]);
}
System.out.println(flag[0]);
int sum = 0;
for (int m = 0; m < cityNum - 1; m++)
{
sum = sum + min[m];
}
sum = sum + distance[flag[0]][flag[cityNum - 1]];
System.out.println("最优路径长度为：" + sum);
}
public static void main(String[] args) {
Tsp tsp = new Tsp();
tsp.initDistance();
tsp.sum();
}
}
五调试分析
在输入数据的时候，如果当城市的序号相同时输入了0，结果就会发生错误，因为在循环体中的if语句判断后便将0作为最优路径存入了min[]中并把该城市序号存入flag[]，就没有得到正确的结果。
六测试结果
七用户使用说明
当程序开始运行后，程序会提示用户输入相应的数据，首先是TSP问题中城市的数量，当输入完毕后程序会提示用户输入每一个城市之间的距离，当城市的序号相同时则输入99999，输入完毕后程序将会将最优路径以数字顺序的形式显示出来。
八课程设计总结
当我拿到题目时我并不知道什么是贪心法，什么是TSP问题，后来在我上网查阅资料后方理解了它的含义以及它与数据结构之间的关系，然后开始思索怎么实现它，要怎么比较出最短的距离然后把它们累加起来并且怎么做到遍历每个节点且不重复，防止它们往回遍历，然后开始写程序，其中要用到数组，多次for循环和if判断，逻辑思维要清晰才能避免错误。通过本次课程设计，我数据结构有了更深刻的了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。