외판원문제(TSP)의 최소비용, 최단거리경로 구함

소개글

문 제 : 외판원문제(TSP)의 최소비용, 최단거리경로 구함
방 법 : 동적계획알고리즘(Dynamic Programming) VS 분기한정법(Branch And Bound)
두가지 알고리즘을 동시에 구현하고 이를 비교 분석함
작성일 : 2005/6/6
작성자 : 이진영
한 계 : 32bit int를 사용하여 Vertex를 구분하였으므로 (unsigned)최대 33X32행렬 까지만 처리할수 있다.
장 점 : < Dynamic Programming >
책에서는 pMatrix와 dMatrix의 메모리를 {n*2^(n-1)}로 처리하였는데
공부하는중 pMatrixd와 dMatrix의 0행이 임시 변수 하나로 충당될수 있다는 점에 착안
{(n-1)*2^(n-1)}의 공간복잡도를 갇도록 수정하였다. 이는 1/n만큼의 공간이 절약되는
효과가 있다.

< Branch And Bound >
Node객체의 path와 bIsPassed배열을 동적으로 잡으려는 시도를 해봤는데 실패했다.
동적으로 잡으면 사용자 입장에서 따로 신경써줘야 할 부분이 없고 더많은 확장이
수정없이 가능하지만 이런 경우 실행시에 배열을 잡는다는 오버헤드는 무시할 수 없다.
속도차이가 엄청난 것을 발견했다. 그래서 힙의 영역도 정적으로 잡으려 했지만
정적으로 잡는 메모리 영역 stack overflew가 난다는 사실을 알게되었다.
어쩔 수 없이 힙은 동적으로 생성했다. 동적 프로그래밍 방식으로는 20개 이상의 데이타
처리시 눈에 띄게 속도가 저하된다. 그러나 분기한정법은 뒤로 갈수록 동적 알고리즘과의
격차가 커짐을 확인할 수 있었다. 일단 Node 클래스에 고정 사이즈로 30을 주었다.
30개의 정점만 확인하는데도 엄청난 인내심이 필요할 것이다. 참고로 나는 23개까지 확인하고
뻗었다. 그나마 동적 프로그래밍은 확인조차 되지 않았다. 너무 느려서...

컴파일 실행환경

Visual Studio 2005, VC++

압축파일 내 파일목록

Heap.h
Node.cpp
Node.h
run.cpp
TSP.cpp
TSP.h
TSP.sln
TSP.vcproj
inputData/TSP04.txt
inputData/TSP05.txt
inputData/TSP10.txt
inputData/TSP15.txt
inputData/TSP20.txt
inputData/TSP21.txt
inputData/TSP22.txt
inputData/TSP23.txt
inputData/TSP24.txt
inputData/TSP25.txt

전체 목록 보기

참고 자료

Foundations of Algorithms using c++ pseudocode
Richard Nepolitan / Kumarss Naimipour - 도경구역
알고리즘