EDA365电子论坛网
标题:
TSPLIB数据集简介与MATLAB读取
[打印本页]
作者:
mutougeda
时间:
2020-10-28 11:14
标题:
TSPLIB数据集简介与MATLAB读取
# R& l- b8 F/ E K: L
数据格式：
! y2 R/ \9 R1 d' e, L1 v& A; A
; K) Y8 w& k3 ~" y0 ~2 p8 {
NAME : eil51
" ^/ ?* m# I" X' J" y
2 K7 H2 I" b0 S+ ?
COMMENT : 51-city problem (Christofides/Eilon)
& x. a$ @0 f1 e) M" X
. ]" ^% y' }6 ~* a
TYPE : TSP
2 s4 l, A# P! E6 b9 L
7 T& D1 F! Y! E, M
DIMENSION : 51
3 N/ B- O2 K) y5 |. V
. I) o1 K' w2 z) f) Y9 S( E! `
EDGE_WEIGHT_TYPE : EUC_2D
, l/ `6 e' c2 S$ y" p3 h: |7 C3 I
* _% i" q/ W3 N* l2 z
NODE_COORD_SECTION
- w4 t; C5 q2 r$ Q
; M0 W6 ~% x7 i# K
1 37 52
2 r" `$ b4 E$ o' C8 l) c2 M5 [
- ^! S( p$ x+ C' d V
2 49 49
" H7 g% C; U. o! E4 r: t
, @2 R, P+ F: [/ B) ?0 z* _
3 52 64
# S. i* n' R0 @$ R% `. h9 F- q
" S, D' X! z- }% o; b' Y8 E
4 20 26
3 J! z7 I+ ?% S& e8 f, @
" V4 X' k0 f" P/ d
5 40 30
5 o8 k1 z/ `& n/ }
5 P' n ]: |: E7 i5 E- m( A4 J
…
8 x9 G* V/ ]$ k- _
4 b0 S0 \" H& V. X# O( ?, B
50 56 37
. K, `3 N0 u; Y
5 {- a& Q6 C5 j- v
51 30 40
8 H# [8 H5 f' Q) c
1 d9 M6 r% V% @* n6 j
EOF
# F6 f/ _$ ?; }: T. D) U$ T
+ [$ i4 \4 z! `2 `# J
1 F) N) U0 J/ Q* _
* E7 s" Q3 Q( C
NAME就是该文件的名字。
$ S" z/ u {% S& m
" {8 G$ w7 e* [$ c( H
COMMENT是对这个问题的附加说明。
4 w5 p1 ~8 v; W: e( Y
: H% r: i# Q4 Y) B/ R; _( {% G
TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
6 g! q7 \8 U/ Y! n: w) j2 `
: i* g! ?, P% n. _
DIMENSION描述了城市的数量。
" D: z% T5 N+ F! A& E; X" D( Q0 G
5 W1 x C0 T) e+ w) |" ^, }
EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。
! N! \8 ~+ u: r
! A7 y9 y, N$ _5 {2 [. G9 a* {- J
NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
# a# T( H5 l, @7 h/ Z1 J: ~3 Y
5 ^7 w, q/ d' b2 e& ?( i/ D$ U" R9 H8 d
但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。
! d% e$ h9 y: a! q7 ~& o
$ o! R, p5 G4 X4 S3 x# R) D) {+ ?5 {
MATLAB读取代码：
6 p$ r# b0 o5 }6 I0 n
, u- w/ _. h9 v# g3 ?% d c
function [n_citys,city_position] = Read(filename)
fid = fopen(filename,'rt');
location=[];
A = [1 2];
tline = fgetl(fid);
while ischar(tline)
if(strcmp(tline,'NODE_COORD_SECTION'))
while ~isempty(A)
A=fscanf(fid,'%f',[3,1]);
if isempty(A)
break;
end
location=[location;A(2:3)'];
end
end
tline = fgetl(fid);
if strcmp(tline,'EOF')
break;
end
end
[m,n]=size(location);
n_citys = m;
city_position=location;
fclose(fid);
end
% G' ~- A4 u. r2 o7 f0 Z! F
3 u' r3 e3 p) T7 c$ \/ d) _
l6 X# F; r4 e
作者:
ExxNEN
时间:
2020-10-28 13:11
TSPLIB数据集简介与MATLAB读取
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2