TSPLIB 소개 와 간이 해석 기 구현
TSP 는 바로 Travelling Salesman Problem (여행 상인 문제) 의 약칭 이다.수학 분야 의 유명한 문제 중의 하나 다.n 개 도시 가 있 는데 한 여행 상인 이 그 중의 한 도시 에서 출발 하여 유일 하 게 모든 도 시 를 돌아 다 니 고 그 가 출발 한 도시 로 돌아 가 가장 짧 은 노선 을 구 해 야 한다.이 문 제 는 택배 업 등 업계 에 도 매우 현실 적 인 의 미 를 가진다. 물론 현실 의 TSP 는 일반적으로 동태 적 이 고 더욱 복잡 해 야 한다.TSP 는 대칭 TSP (Symmetric TSP), 다른 하 나 는 비대 칭 TSP (Asymmetric TSP) 로 나 눌 수 있다.차이 점 은 도시 a 에서 b 까지 도시 b 에서 a 까지 의 cost 가 같 는 지, 같은 것 은 대칭 TSP 이다.여기 서 우리 가 토론 하 는 것 은 모두 대칭 TSP 이다.모든 TSP 문 제 를 하나의 그래프 로 묘사 할 수 있다 는 것 을 상상 할 수 있 을 것 이다. 물론 이 글 은 주로 TSP 자 체 를 토론 하기 위 한 것 이 아니 라 구체 적 인 정 의 는 생략 되 어 여러분 이 스스로 찾 을 수 있다.
TSP 는 이미 NP Hard 문제 로 증명 되 었 다.현재 많은 알고리즘 이 TSP 를 해결 할 수 있다. 예 를 들 어 모두 가 익숙 한 동적 계획 과 개미 떼 알고리즘 과 같은 각종 진화 알고리즘 이다.이러한 알고리즘 의 성능 을 평가 하기 위해 독일 하 이 델 베 르 크 유 니 버 시 티 의 Gerhard Reinellt 는 1990 년대 연구실 홈 페이지 에 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)。그러나 해설 은 특별히 상세 하지 않 고 다른 많은 학우 들 도 이 논문 의 존 재 를 모 르 기 때문에 저 는 여기 서 조금 설명 하 겠 습 니 다.
eil51. tsp 와 같은 전형 적 인 TSPLIB 파일 은 다음 과 같은 형식 을 가지 고 있 습 니 다.
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 좌표 의 순서에 따른다.
하지만 주의해 야 할 것 은 EDGEWEIGHT_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 항목 이 아니 라 대응 하 는 EDGEWEIGHT_FORMAT 와 EDGEWEIGHT_SECTION，EDGE_WEIGHT_FORMAT 는 데이터 가 어떤 형태 로 나타 나 는 지, 여기 LOWERDIAG_ROW 는 하 삼각 행렬 을 대표 한다.그 러 니까 EDGEWEIGHT_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 = @"
TYPE\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[] {' ', '
'});
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 는 도시 간 거 리 를 저장 하 는 2 차원 배열 입 니 다.먼저 전체 파일 을 string 으로 읽 은 다음 4 가지 pattern 으로 필드 TYPE, DIMENSION, EDGE 를 각각 캡 처 합 니 다.WEIGHT_TYPE, EDGE_WEIGHT_FORMAT 이후 의 내용.정규 표현 식 자 체 는 복잡 하지 않 습 니 다. 여러분 이 알 수 있 을 것 이 라 고 믿 습 니 다. 주의해 야 할 부분 은 빈 칸 과 줄 바 꿈 의 일치 입 니 다.캡 처 된 TYPE 형식 은 파일 이 tsp 형식 파일 인지 판단 하 는 데 사 용 됩 니 다. DIMENSION 은 배열 의 크기 를 결정 하 는 데 사 용 됩 니 다. EDGEWEIGHT_TYPE 는 거리 유형 을 판단 하 는 데 사 용 됩 니 다. 여기 서 저 는 간단하게 switch 문 구 를 사 용 했 습 니 다.서로 다른 유형 은 서로 다른 처리 가 필요 합 니 다. 여 기 는 EUC 만 실 현 했 습 니 다.2D 와 EXPLICIT 유형 은 나머지 는 논문 을 참고 하여 자체 적 으로 실현 할 수 있 습 니 다.EXPLICIT 유형 이 라면 EDGE 를 판단 해 야 합 니 다.WEIGHT_FORMAT, 여기 서 저 는 대칭 적 인 전체 행렬 과 하 삼각형 행렬 두 가지 상황 을 실 현 했 고 나머지 여러분 도 스스로 실현 할 수 있 습 니 다.Main 함 수 는 테스트 에 사 용 됩 니 다.최종 적 으로 얻 은 distMatrix 는 각종 알고리즘 에 사용 할 수 있다.일반적인 판단 에 비해 정규 표현 식 의 강 한 표 현 력 은 우리 가 관심 을 가 지 는 정 보 를 쉽게 추출 할 수 있다.
마지막 으로 완전한 TSP 실험 도 구 를 제공 합 니 다.https://github.com/natsu1211/JikkenTsp다양한 알고리즘 과 도형 의 실시 간 생 성 을 지원 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
awk 상용 명령awk 는 모든 입력 줄 을 하나의 기록 으로 인식 하고 그 줄 의 모든 단어 도 메 인 을 하나의 필드 로 인식 합 니 다. ARGC 명령 줄 에 awk 스 크 립 트 가 들 어 오 는 매개...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
