검색어 입력폼
평가점수B

[TSP, C++, 프로그램소스]TSP - 3가지 알고리즘으로 구현

등록일 2006.07.30 파일확장자압축파일 (zip) | 가격 3,000원

소개글

이 프로그램은 주먹구구, 동적, 분기한정법 3가지 알고리즘을 통해서
TSP알고리즘을 완벽하게 구현했습니다..
최대한 소스를 깔끔하게 작성하였으며, 어려운 부분은 명쾌한 주석처리를
했습니다. 그리고 테스트 케이스도 여럿 만들어놓았습니다.
각각의 알고리즘을 비교하여 결론 또한 자세히 적어놓았습니다.
절대 후회없으실겁니다.

컴파일 실행환경

Windows XP, Visual C++ 6.0 Tool을 사용하였습니다.
C++로 작성되었습니다.
그리고 CUI로 결과화면을 보실수 있습니다

본문내용

// 주먹구구 알고리즘을 이용한 TSP 구현
#include <iostream>
#include <string>
#include <fstream>
#include <time.h>

using namespace std;

#define MAX 999999999
typedef unsigned int UINT;

UINT nodeCnt;
UINT edgeCnt;
UINT minLength = MAX;
UINT **W;
UINT *short_path;
UINT *path;

bool check(UINT iter, UINT i)
{
for(int j = 1; j < iter; j++)
if(path[j] == i) return false;


// 동적 알고리즘을 이용한 TSP 구현
#include <iostream>
#include <fstream>
#include <time.h>
#include <math.h>

using namespace std;

#define MAX 99 //999999999 // 4294967294 - 행렬 값들의 합
typedef unsigned int UINT;

UINT nodeCnt;
UINT edgeCnt;
UINT minLength = MAX;
UINT **W;

///// 새로 추가 되는 것..
UINT **D; // D[i][A] i번째 노드에서 A의 노드를 한번씩만 거쳐 v0에 가는 최소의 length
UINT **P; // P[i][A] vi 다음에 오는 노드 번호

// 숫자로 부분집합 크기 구하는 함수
UINT count(UINT subset)
{
UINT count = 0;
UINT i;
for(i = 0; i < nodeCnt -1; i ++)

//분기한정법 알고리즘을 이용한 TSP구현
#include <fstream>
#include "PriorityQueue.h"
#include "time.h"

#define MAX 9999

UINT nodeCnt;
UINT edgeCnt;
UINT minLength = MAX;
UINT **W;
UINT *opttour;

UINT length(node node)
{
UINT i = 0;
UINT result = 0;
UINT col, row;

while(i < nodeCnt)
{
col = node.path[i];
row = node.path[i+1];
result += W[col][row];
i++;
}
return result;
}

압축파일내 파일목록

PriorityQueue.cpp
PriorityQueue.h
best.cpp
dp.cpp
Low.cpp
data/tsp10.dat
data/tsp11.dat
data/tsp12.dat
data/tsp13.dat
data/tsp14.dat
data/tsp15.dat
data/tsp4.dat
data/tsp5.dat
data/tsp6.dat
data/tsp7.dat
data/tsp8.dat
data/tsp9.dat
실행결과.doc
추가 케이스 결과 및 결론.doc
테스트 케이스(추가).doc
다운로드 맨위로