算法报告-旅行商问题模板

《算法设计与课程设计》

题 目：

班 级：

学 号：姓 名：指导老师：完成日期：成 绩： TSP问题多种算法策略 计算机技术14

旅行商问题的求解方法

摘要

旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。

关键字：旅行商问题；动态规划法；贪心法；回溯法；深度优先搜索策略 1引言

旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法、回溯法和深度优先搜索策略。 2正文

2.1动态规划法

2.1.1动态规划法的设计思想

动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。

2.1.2 TSP问题的动态规划函数

假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V'Vi，于是，TSP问

题的动态规划函数为：

d(i,V')mincikd(k,Vk)(kV')

d(k,)cki(ki)

2.1.3算法分析

（1）for (i=1; i

d[i][0]=c[i][0];

n-1（2）for (j=1; j

for (i=1; i

if (子集V[j]中不包含i)

对V[j]中的每个元素k，计算V[m] == V[j]-k;

d[i][j]=min(c[i][k]+d[k][m]);

（3）对V[2n-1 -1]中的每一个元素k，计算V[m] == V[2n-1 -1]-k;

n-1d[0][ 2 -1]=min(c[0][k]+d[k][m]);

n-1 （4）输出最短路径长度d[0][ 2 -1];

2.1.4时间复杂性

T(n)O(n2n)

动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。

2.2贪心法

2.2.1贪心法的设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。

2.2.2最近邻点策略求解TSP问题

贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。 最近邻点策略：从任意城市出发，每次在没有到过的城市中选择距离已选择的城市中最近的一个，直到经过了所有的城市，最后回到出发城市。

2.2.3算法分析

1．P={ };

2．V=V-{u0}; u=u0; //从顶点u0出发

3．循环直到集合P中包含n-1条边

3.1查找与顶点u邻接的最小代价边(u, v)并且v属于集合V；

3.2 P=P+{(u, v)};

3.3 V=V-{v};

3.4 u=v; //从顶点v出发继续求解

2.2.4时间复杂性

TO(n2)

但需注意，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。

2.3回溯法

2.3.1回溯法的设计思想

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

若已有满足约束条件的部分解，不妨设为（x1,x2,x3,„„xi），I

2.3.2 算法分析（回溯法+深度优先搜索策略）

因为是采用回溯法来做，肯定是递归，然后还需要现场清理。

要设置一个二维数组来标识矩阵内容，然后回溯还需要设计

一个二维标记数组来剪枝，设定一个目标变量，初始为无穷大，

后续如果有比目标变量值小的就更新。剪枝的条件就是如果走到当前节点的耗费值>=目标变量，就直接不再往下面走，向上走。

深度优先 = 递归

递归基:如果到达叶子节点的上一个节点，那么就进行是否更新的判断

递归步:如果没有到达叶子节点，就进行剪枝操作，判断能否进入下一个节点，如果能，更新最优值

2.3.3 关键实现（回溯法+深度优先搜索策略）

1 //递归基：如果已经遍历到叶子节点的上一层节点，i标识递归深度

if(i == g_n)

{

//判断累加和是否超过最大值,如果有0，应该排除;满足这个条件，才打印 if((g_iArr[pArr[i-1]][pArr[i]] != 0) && (g_iArr[pArr[g_n]][1] != 0) && (g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] + g_iArr[pArr[g_n]][1]

{

g_iResult = g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] + g_iArr[pArr[g_n]][1];

//用当前最优路径去更新最优路径，防止下一次没有

for(int k = 1 ; k

{

g_iBestPath[k] = pArr[k];

2 //递归步:判断能否进入子树，需要尝试每一个节点

else

{

//尝试不同的组合

for(int j = i ; j

{

//判断能否进入子树:如果当前值+下一个连线值的和

if( (g_iArr[pArr[i-1]][pArr[j]] != 0) && (g_iCurResult + g_iArr[ pArr[i-1] ][ pArr[j] ]

3 //交换i与j,则i为当前可以尝试的范围

//为完成后面k个元素的排列，逐一对数组第n-k~n个元素互换。数组第一个元素为1，生成后面n-1个元素的排列

//数组第一个元素与第二个元素互换，第一个元素为2，第2个元素为1，生成后面的n-1个元素的排列...

swap(&pArr[i],&pArr[j]);

//更新当前累加值,是i-1与i的

g_iCurResult += g_iArr[ pArr[i-1] ][ pArr[i] ];

//递归

backTrace(i+1,pArr);

//回溯，清空累加值；能够走到这里，说明上述结果不是最优解，需要向求解树上一层回退

g_iCurResult -= g_iArr[pArr[i-1]][ pArr[i] ];

swap(&pArr[i],&pArr[j]);

*/

2.3.4时间复杂性

T = O(n!), 该方法并没有有效的提高时间效率。

3结论

本文主要重点讨论了动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题算法，并附录给出了相应程序，并通过对比得到动态规划法和贪心法相对更有优势，下面对这两种方法进行详述和进一步对比。

3.1动态规划法思想

动态规划法中对于顶点元素生成的子集本文中用字符串形式存储，然后再用递归方法按照子集中元素个数从小到大开始赋值。因为后面元素个数较多的子集与前面比其元素个数少1的子集间有一定对应关系，所以用递归方式，可以简便很多。个人觉得这算本文的一大特色。另，在计算d[i][j] =min(c[i][k]+d[k][j-1])时，获得d[k][j-1]的过程比较困难，运用字符串后，我们就可以首先找到指定字

符，然后去掉该字符，返回剩余字符串，在与V[]逐个比较，找到与其相等的V[]中元素对应下标，此下标即为j-1；具体求解过程可参考附录源程序，有详细说明。在求解最佳路径所经过城市顺序时，本文是通过边查找d[i][j]边记录路径的，这样可以省掉很多麻烦，另，路径也是采用字符串形式的数组，数组规模与存储城市间距离的c[][]数组相同，由于很多元素均不需赋值，这样做可能会浪费内存空间，但是目前还没找到更好地求解方法。

3.2贪心法思想

贪心法中，由于贪心法相对动态规划法要简单很多，每次在查找最近城市时所得的顶点均为最后该法最佳路径所经过的城市编号，规模相对较小，容易确定，操作相对简单，所以本文用数组V[]存放最佳路径所经过的城市编号顺序相对来说方便很多。另外，本文用path[]整型数组存放所经路径的长度，最后相加即可得最短路径。

3.3两者比较

动态规划法相对贪心法来说虽然要精确些，但代码相对繁杂很多，对时间和空间要求很多，仅适用于城市数量较小的情况。贪心法虽然比较简单，实现起来比较容易，但不是很精确，当图中顶点个数较多并且各边的代价值分布比较均匀时，贪心法可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。

另外，动态规划法有一个明显的缺点，就是出发城市只能是第0个城市（城市从0开始编号），若出发城市改变，则必须以该城市为第0个城市顺序给其他城市编号，输入城市间距离。由于若出发城市任意，编码的难度大大增加，所以最后不得已放弃，但这大大地限制了程序的通用性。而对于贪心法，本文很好地避免了这个问题，一旦城市编号确定，可以从任意城市出发，这也是本文中贪心法优于动态规划法的一点。

3.4优点

本文程序优点，各个子函数功能分隔很明显，没有大量集中在一个函数里面，而是分成了几个不同功能的小函数，这样程序可阅读性提高。另外，程序中有详细注释，程序中变量取名都是根据变量的性质和所代表的含义命名的，也相应提高了程序的可读性。

对于动态规划法，城市个数可以在算法时间允许的范围内任意，于这点来说，通用性较好；对于贪心法，出发城市可以任意，城市个数也可以任意，通用性较好。

3.5 建议

当城市个数较少时，用动态规划法求出最优解；当城市个数较多并且各边的代价值分布比较均匀时，贪心法可以给出较好的近似解。

4参考文献

（1）《计算机算法分析与设计》第二版，王晓东编著，电子工业出版社

（2）Java语言与面向对象程序设计（第2版）印旻、王行言编著，清华大学出

版社

（3）求解TSP算法，周康、强小利、同小军、许进，计算机工程与应用

（4）《算法设计与分析》，王红梅编著，清华大学出版社

（5）《ACM/ICPC算法训练教程》，余立功主编，清华大学出版社

6附录

6.1动态规划法

6.1.1源代码 package Tsp;

import java.util.Scanner;

public class TSPDP {

// 初始化数组c[]，即顶点间距离 public void initialC() { } Scanner in = new Scanner(System.in); System.out.println("请输入城市个数：（ 注意根据实际情况城市个数不可小于1！）N = in.nextInt(); if (N

中

// 初始化顶点生成的子集的对外调用函数 public void initialV1() { } // 具体的初始化顶点生成的子集 // 本程序使用递归调用方法初始化V，并按照数字大小顺序排序。。另，子集使用字符型// 我们是按照子集中元素个数从小到大逐个添加的，后面的子集是前面对应子集加上一个public void initialV(int m, int len) {// m代表下一个即将初始化的V数组的元 if (m > (int) Math.pow(2, N - 1) - 1) return;// 如果全部顶点已初始化完成，则返回。 V = new String[(int) Math.pow(2, N - 1)];// 为V分配空间 initialV(0, 0); 形式存放的 元素组成的，故用递归 素的下标；len是最后一个初始化的元素的长度 if (m == 0) } initialV(m, V[m - 1].length());// 递归调用 V[m++] = "";// 初始化出发顶点，即V[0] int i = m - 1; while (i >= 0 && V[i].length() == len) // 找与最后一个初始化的V[m-1]子集内元素个数相同的集合，把指针i指i--; else { 向满足条件的集合 i++;// 把指针i指向满足条件的第一个集合 while (i

} // 判断自己V[j]中是否存在指定元素，即行号i boolean exclude(int i, int j) { } // 获得子集V[j]中除指定元素k外的元素，用字符串形式表示 public String getSubString(int k, int j) { } // 找出V[]中与str相同元素的下标号,即找出上一个子集 public int stringEqual(String str) { } // 求最小距离 public int min(int i, int j) { int k = 0;// 用于记录V[j]中元素个数 // if(str.equals(""))return 0; int i = 0; while (i

for (int i = 1; i c[i][v] + d[v][stringEqual(str)]) { } k++; min = c[i][v] + d[v][stringEqual(str)]; path[i][j] = path[v][stringEqual(str)] + i; // System.out.println("min" + str + stringEqual(str) + v); if (stringEqual(str) == -1) System.exit(0); int min = c[i][v] + d[v][stringEqual(str)];// 先把最小的距离赋值给从V[j]// System.out.println(min); // //stringEqual(str)表示返回与上面获得的字符串相同的V中元素的下标，即找path[i][j] = path[v][stringEqual(str)] + i; k++; String vStr = "" + V[j].charAt(k);// 铭记V[j].charAt(k)得到的是字符型，int v = Integer.parseInt(vStr);// 把位置k处的字符转换成整形 String str = getSubString(k, j);// 获得V[j]中除位置k处外的字符串 转换成整形后是字母对应的ASC码！！！！ 中第一个顶点出发的距离 上一个子集

} // 初始化后面的元素 int j = 1; for (; j

} } for (int i = str.length() - 2; i >= 0; i--) { } System.out.println("会有最短路径"); System.out.println("最短路径为：" + d[0][(int) Math.pow(2, N - 1) - 1]); System.out.print("->" + str.charAt(i)); // 主函数 public static void main(String[] args) { } TSPDP TSP = new TSPDP(); TSP.dynamic();// 求最短路径 TSP.print();//打印中间结果，测试和理解用 TSP.printShortestPath();// 输出最短路径

// 测试数据

/*

* 99999 3 6 7

* 5 99999 2 3

* 6 4 99999 2

* 3 7 5 99999

*/

6.1.2结果

（1）

（2）

（3）

（4）

6.2贪心法

6.2.1源代码

/*

* TSP：贪心法之最近邻点策略求解

*/

package Tsp;

import java.util.Scanner;

public class TSPGreedy {

大

// 初始化数组c[]，即顶点间距离 public void initialC() { Scanner in = new Scanner(System.in); System.out.println("请输入城市个数：（ 注意根据实际情况城市个数不可小于1！）N = in.nextInt(); if (N

} } System.out.println("请输入城市相邻城市间距离（城市从0开始编号，且出发城c = new int[N][N];// 为c分配空间 for (int i = 0; i

}

/* } } System.out.println("从" + V[i] + "->" + V[i + 1] + ",所经路程为：" + path[i]); shortestPath += path[i]; System.out.println("总路程为：" + shortestPath); public static void main(String[] args) { } TSPGreedy tg = new TSPGreedy(); tg.tspGreedy(); //tg.print();

* 99999 3 3 2 6

* 3 99999 7 3 2

* 3 7 99999 2 5

* 2 3 2 99999 3

* 6 2 5 3 99999

*/

6.2.2结果

(1)

(2)

(3)

(4)

6.3回溯法（回溯法+深度优先搜索策略）

6.3.1源代码

#include

#include

using namespace std;

const int MAXSIZE = 100;

const int MAX = 1000000000;

int g_iArr[MAXSIZE][MAXSIZE];//邻接矩阵

int g_iResult;//存放最优解

int g_iPath[MAXSIZE];//存放最优路径上

int g_n;//元素个数

int g_iCurResult;//当前累加路径和

int g_iBestPath[MAXSIZE];//还需要设置一个数组，用来保存最优解

void swap(int* pI,int* pJ)

{

}

void printResult(int n,int* pArr)

{

cout

cout

cout

}

//可以做成字符串全排列的性质track(int i,int* pArr,int* pResult),其中pArr是用于存放最优解的路径

void backTrace(int i,int* pArr)

{//递归基：如果已经遍历到叶子节点的上一层节点 for(int i = 1 ; i 1""

} if(i == g_n) { //判断累加和是否超过最大值,如果有0，应该排除;满足这个条件，才打印 if((g_iArr[pArr[i-1]][pArr[i]] != 0) && (g_iArr[pArr[g_n]][1] != 0) &g_iResult = g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] + (g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] + g_iArr[pArr[g_n]][1]

void process()

{

if(g_n

{

cout

}

cout

}

int main(int argc,char* argv[])

{

}

/*测试输入样例：

4

0 0 1 7

8 0 5 1

7 2 0 1

2 5 3 0

*/ process(); getchar(); return 0; //初始化 while(EOF != scanf("%d",&g_n)) //while(EOF !=(cin>>g_n)) { } cout>g_iArr[i][j];

6.3.2结果

(1)

(2)

(3)