首页 > 代码库 > TSPLIB简介与简易解析器实现
TSPLIB简介与简易解析器实现
背景知识
TSP即Travelling SalesmanProblem(旅行商人问题)的简称。是数学领域中的著名问题之一。有n个城市,一个旅行商人要从其中某一个城市出发,唯一走遍所有的城市,再回到他出发的城市,求最短的路线。这个问题对快递业等行业也非常具有现实意义,当然现实中的TSP一般是动态的,要更为复杂。TSP可以分为两类,一类是对称TSP(Symmetric TSP),另一类是非对称TSP(Asymmetric TSP)。区别就在于都市a到b和都市b到a的cost是否相等,相等的就是对称TSP。这里我们讨论的都是对称TSP。大家应该能想象的到,所有的TSP问题都可以用一个Graph来描述,当然这篇文章主要不是为了讨论TSP本身,具体的定义就从略了,大家可以自行查找。
TSP已经被证明是个NP Hard问题。目前有许多算法能够用来解决TSP,比如大家熟悉的动态规划,以及诸如蚁群算法的各种进化算法。为了评价这些算法的性能,德国Heidelberg University 的Gerhard Reinelt在上世纪90年代在其研究室的主页上公开了一套TSPLIB(以TSP为主的问题库),因其在之后被TSP方面的几篇重要论文所采用,渐渐成为评价TSP算法公认的BENCHMARK。
链接:http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
TSPLIB文件格式
TSPLIB是一个包含了TSP及其相关问题的问题库。其中的文件都具有.tsp后缀。
关于这些文件的使用,有一篇专门的解说论文(https://docs.google.com/file/d/0B4zUGKjaO9uERU1RZDNuRkg3TW8/edit)。但是解说并不是特别详细,另外很多同学也不知道这篇论文的存在,我在这里还是稍微说明一下。
一个典型的TSPLIB文件,如eil51.tsp,具有如下的格式:
NAME : eil51
COMMENT : 51-city problem (Christofides/Eilon)
TYPE : TSP
DIMENSION : 51
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 37 52
2 49 49
3 52 64
4 20 26
5 40 30
…
50 56 37
51 30 40
EOF
NAME就是该文件的名字。
COMMENT是对这个问题的附加说明。
TYPE描述了问题的类型,因为TSPLIB中还包含了一些其他类型的问题,但是这里我们只关注TSP类型。
DIMENSION描述了城市的数量。
EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型,这里是我们最为熟悉的2D欧几里得距离。
NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号,X坐标,Y坐标的顺序。
但是需要注意的是,EDGE_WEIGHT_TYPE并不是只有EUC_2D一种,而是有13种之多。各种类型有对应的距离计算方法,如曼哈顿距离,地理距离等,这里我就不一一列举了,论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT,这种类型和其他的区别较大,城市间的距离是显式给出的,无需再计算。以gr17.tsp为例:
NAME: gr17
TYPE: TSP
COMMENT: 17-city problem (Groetschel)
DIMENSION: 17
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
0633 0 257 390 0 91 661 228 0 412 227
169383 0 150 488 112 120 267 0 80 572 196
77351 63 0 134 530 154 105 309 34 29 0
259555 372 175 338 264 232 249 0 505 289 262
476196 360 444 402 495 0 353 282 110 324 61
208292 250 352 154 0 324 638 437 240 421 329
297314 95 578 435 0 70 567 191 27 346 83
4768 189 439 287 254 0 211 466 74 182 243
105150 108 326 336 184 391 145 0 268 420 53
239199 123 207 165 383 240 140 448 202 57 0
246745 472 237 528 364 332 349 202 685 542 157
289426 483 0 121 518 142 84 297 35 29 36
236390 238 301 55 96 153 336 0
EOF
需要注意的是,如果EDGE_WEIGHT_TYPE类型为EXPLICIT,那么就没有NODE_COORD_SECTION项,而是对应的EDGE_WEIGHT_FORMAT与EDGE_WEIGHT_SECTION,EDGE_WEIGHT_FORMAT指明了数据以何种形式呈现,这里的LOWER_DIAG_ROW代表着下三角矩阵。也就是说EDGE_WEIGHT_SECTION所列出的数据应当这么看,
0
633 0
257 390 0
91 661 228 0
…
城市1到城市2的距离就是633,任何城市到自己本身的距离都为0。另外除了下三角矩阵还有全矩阵,上三角矩阵等。
另外,tsp文件对空格的数量和最终的EOF并没有严格的要求,因此每个文件在格式上都可能有些微妙的区别,这就为解析器的实现提出了一些小小的挑战。好在我们还有正则表达式可以比较轻松的解决这些问题。
解析器实现
无论是什么算法,真正需要的信息只有城市规模的维度和各个城市间的距离,如何解析tsp文件获得这些信息,正是我们关心的。下面我给出一个C#实现的简易解析器,只为了说明问题,代码本身还有很多可以优化重构的地方。
using System; using System.Collections.Generic; using System.Text; using System.Text.RegularExpressions; using System.IO; namespace TspFileParser { class Program { public static class TspParser { public static void ParseTspFile(string fileName, out int[,] distMatrix) { //string[] lines = {}; string typePattern = @"\nTYPE\s?:\s?(?<type>\w+)"; string dimPattern = @"DIMENSION\s?:\s?(?<dimension>\d+)"; string wtypePattern = @"EDGE_WEIGHT_TYPE\s?:\s?(?<wtype>\w+)"; string formatPattern = @"EDGE_WEIGHT_FORMAT\s?:\s?(?<ftype>\w+)"; //string pattern = @"(^TYPE\s*:\s*(?<type>\w+))|(DIMENSION\s*:\s*(?<dimension>\d+))|(EDGE_WEIGHT_TYPE\s*:\s*(?<wtype>\w+))"; //map dimension int dim = 0; string text = default(string); try { // lines = File.ReadAllLines(fileName); text = File.ReadAllText(fileName); } catch(DirectoryNotFoundException /*DirctNot*/) { Console.WriteLine("Directory is incorrect!"); } catch (FileNotFoundException /*fileNot*/) { Console.WriteLine("File not found!"); } Match problemType = Regex.Match(text, typePattern); if (problemType.Groups["type"].Value != "TSP") throw new Exception("Not a tsp file!");//not handled Match dimension = Regex.Match(text, dimPattern); Match weightType = Regex.Match(text, wtypePattern); string[] textSplit = text.Split(new Char[] {' ', '\n'}); dim = Convert.ToInt32(dimension.Groups["dimension"].Value); distMatrix = new int[dim, dim]; switch (weightType.Groups["wtype"].Value) { case"EXPLICIT": { Match formatType = Regex.Match(text, formatPattern); switch(formatType.Groups["ftypes"].Value) { //symmetrical full matrix case"FULL_MATRIX": { int startPos = 0; for (int i = 0; i < textSplit.Length; ++i) { if (textSplit[i] == "EDGE_WEIGHT_SECTION") { startPos = i; } } for (int j = 0, n = 0; j < dim; ++j) { for (int i = 0; i < dim; ++i) { ++n; distMatrix[i, j] = text[startPos + n]; } } break; } //lower digram matrix case"LOWER_DIAG_ROW": { int startPos = 0; for (int i = 0; i < textSplit.Length; ++i) { if (textSplit[i] == "EDGE_WEIGHT_SECTION") { startPos = i; } } for (int j = 0, n=0; j < dim; ++j) { for (int i = 0; i <=j; ++i) { ++n; distMatrix[i, j] = text[startPos + n]; } } break; } default: break; } break; } case "EUC_2D": { int startPos = 0; //array to store the cordinate of every city Tuple<int, int>[] cityCord = new Tuple<int, int>[dim]; //find the start index of cordinate region for(int i=0; i<textSplit.Length; ++i) { if( textSplit[i] == "NODE_COORD_SECTION") { startPos = i; } } //extract cordinates for (int n=0, i = startPos; n<dim; ++n ) { //plus 2 to jump over the index before cordinate i = i + 2; int x = Convert.ToInt32(textSplit[i]); ++i; int y = Convert.ToInt32(textSplit[i]); cityCord[n] = new Tuple<int, int>(x, y); } //compute distance for (int i = 0, startj = 0; i < dim; ++i) { for (int j = startj; j < dim; ++j) { distMatrix[i, j] = (int)Math.Sqrt((cityCord[i].Item1 - cityCord[j].Item1) * (cityCord[i].Item1 - cityCord[j].Item1) + (cityCord[i].Item2 - cityCord[j].Item2) * (cityCord[i].Item2 - cityCord[j].Item2)); distMatrix[j, i] = distMatrix[i, j]; } ++startj; } break; } default: break; } } } static void Main(string[] args) { //TspParser parser = new TspParser(); Console.WriteLine("Please input the path of Tsp file"); int[,] distance; TspParser.ParseTspFile(Console.ReadLine(),out distance); Console.ReadKey(); } } }
这里我们只有一个静态类和一个静态方法。静态方法ParseTspFile有两个参数,fileName是tsp文件的路径与名称,out int[,] distMatrix则是用来保存城市间距离的二维数组。先将整个文件读入为一个string,然后用4种pattern分别捕获字段TYPE, DIMENSION, EDGE_WEIGHT_TYPE, EDGE_WEIGHT_FORMAT之后的内容。正则表达式本身并不复杂,相信大家应该能看明白,需要注意的地方是空格和换行的匹配。捕获到的TYPE类型用于判断文件是否是个tsp类型文件,DIMENSION用于确定数组的大小,EDGE_WEIGHT_TYPE用于判断距离类型,这里我简单的用了个switch语句。不同的类型需要不同的处理,这里我只实现了EUC_2D与EXPLICIT类型,其余的大家可以参考论文自行实现。如果是EXPLICIT类型,则还需要判断EDGE_WEIGHT_FORMAT,这里我实现了对称全矩阵和下三角矩阵两种情形,其余的大家也可自行实现。Main函数用于测试。最终得到的distMatrix就可以为各种算法所用了。比起常规的判断,正则表达式强大的表达力使得我们关心的信息的抽取变得十分容易。
TSPLIB简介与简易解析器实现