数据结构课程设计贪心法求解TSP问题

1、数据结构课程设计贪心法求解TSP问题一 目的 利用数据结构课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C+语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。二 需求分析1、问题描述TSP（Traveling Salesman Problem ）是指：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。2、 解法分析 采用贪心

2、法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。要求这时遍历各城市的距离为最短距离。3、 功能要求 输入城市的数量和城市间的距离，要求输入的为整数。结果为输出最短路径和遍历的最短距离，要求为整数。三 概要设计1、 为便于查找离某顶点最近的邻接点，采用邻接矩阵存储该图算法描述如下：(1).任意选择某个顶点i作为出发点；(2).执行下述过程，直到所有顶点都被访问：(3).i=最后一个被访问的顶点；(4).在顶点i的邻接点中查找距离顶点i最近的未被访问的邻接点j；(5).访问顶点j； (6).从最后一个访问的顶点直接回到出发点

3、i。2、 最近邻点策略 从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市，具体求解过程举例如下：3、 程序设计组成框图:输入城市的数量与各城市之间的距离 循环遍历找到与起始城市最近的城市，用flag保存该城市序号，用min保存最短路径 TSP 输出flag,得到最佳路径 用sum+=min求出最短路径4、 流程图：开始输入城市的个数cityNum和城市间的距离noj+mini>dj? i+distance=99999 yesmini=djyesj<cityNum?noflagi=jsum+=miniyesi<cityNum?no输出

4、最短路径flagi和输出最短距sum5、 方法与数据解释：public void initDistance()方法作用：存储个城市间的距离，及城市的数目。public void sum() 方法作用：求各个城市间的最短路径和，并且记录下最佳的旅行路径。每次都要起初的最小距离mini = 99999去和临近的城市去比较距离 mini >= distanceflagkj，这样mini肯定会被覆盖，此时再根据for（j+）循环逐次比较，得出最小的mini，用flagk+1去记下这个城市的编号。再用for循环，输出最佳路径flag。 public static void main(String

5、args) 方法作用：主函数，在主函数中调用各种方法。 cityNum：城市数量； distance：储存的各个城市之间的距离； min：最短路径； flag ：城市编号。四 详细设计 import java.util.Scanner; public class Tsp int cityNum;int distance = new int1010;int min = new int10;int flag = new int10; public void initDistance()System.out.println("请输入城市的数目");Scanner input =

6、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 + "城市之间的距离");distanceij = input.nextInt();int count = 0;for (int i = 0; i < cityNum; i+) for (int j = 0

7、; j < cityNum; j+) System.out.print(distanceij);count+;if (count % cityNum = 0) System.out.println();public void sum() int k = 0;int x = 0;flag0 = 0;for (int i = 0; i < cityNum - 1; i+) mini = 99999;for (int j = 0; j < cityNum; j+) if (mini >= distanceflagkj) mini = distanceflagkj;flagk

8、+ 1 = j;k+;x = 0;/对称的点变成99999，防止往回遍历。while (k - x) != 0) distanceflagkflagk - x - 1 =99999; x+; System.out.println("最优路径：");for (int i = 0; i < cityNum; i+) System.out.print(flagi);System.out.println(flag0);int sum = 0;for (int m = 0; m < cityNum - 1; m+) sum = sum + minm;sum = sum +

9、 distanceflag0flagcityNum - 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问题，后来在我上网查阅资料后方理解了它的含义以及它与数据结构之间的关系，然后开始思索怎么实现它，要怎么比较出最短的距离然后把它们累加起来并且怎么做到遍历每个节点且不重复，防止它们往回遍历