实验7 旅行商问题


实验时间

选做。

实验目的

综合运用所学知识,尝试以不同的算法设计策略解决同一个问题,加深对算法设计的理解。

问题描述

旅行商问题是一个非常经典的算法设计问题。这里描述的是旅行商问题的一个基本的版本:有N座城市,两两之间均有道路连接,某个旅行商要将这些城市遍历一次,每个城市都访问且仅访问一次,最后要回到出发点;要求给出一种遍历顺序,使得旅行商经过的路径总长度最短。
显然,旅行商问题的数学模型是有N个顶点的无向完全网(因为边上有权值),旅行商问题的解则是其中N条边所组成的一个简单回路(因为遍历不能重复访问)。我们怎样求解旅行商问题?可能有这几种策略:
1. 穷举法。列出所有长度为N的简单回路,从其中找出路径总长度最短的。
2. 迭代法。先随机生成一个长度为N的简单回路,再通过迭代找更短的。
3. 递归法。假设N-1时的旅行商问题能解,如何递推求出N时的旅行商问题的解?
4. 贪心法。请自己设计。
5. 回溯法。请自己设计。
6. 分枝定界法。请自己设计。
还有其他策略吗?

实验内容

请为旅行商问题设计至少3种算法。分析你设计的算法是否能够保证得到最优的结果,算法的时间、空间复杂度如何。
编程实现你设计的至少2种算法,随机生成测试数据,比较不同算法的输出结果和运行时间。
设计并实现5种以上(含5种)算法的同学可获得实验加分。