'TSP'에 해당되는 글 1건

  1. 2008.06.12 [Algorithm] - 동적 계획을 이용한 TSP구현!

동적계획으로 구현을 위해서는 동적계획 부터 알고 넘어가야겠다. 동적 계획이란...
알고리즘 구현방법 중의 하나로 문제를 해결함에 있어서 기존에 계산된 결과가 있다면 그것을 사용하여 수행 시간을 단축 시키는 방법이다.
그럼 이 동적계획법을 사용하여 TSP를 구현함에 있어서의 기존에 구해진 재귀관계식 부터 살펴보자..맨땅에 헤딩 할 순 없으니깐;;;;;;ㅋ

사용자 삽입 이미지

위의 식에서 D[V1][V-{V1}] 이라는 배열이 바로 동적계획에 사용될 최소 여행 경로의 거리를 저장할 배열이다. 그리고 W[i][j]배열이 정점 i에서 j로 가는 간선의 가중치를 담을 배열이다.
위의 식을 일반화 해서 i<>1 이고 Vi가 A에 속하지 않을때라 하면 아래와 같이 된다라고 하는....

사용자 삽입 이미지

위 수식을 얻는 과정은 알고리즘 책을 봐야겠다...;
.
.
그럼 위의 주어진 재귀식을 통해 프로그램으로 승화 시켜보자~! ㅡ_ㅡ+

일단 필요한 배열들... 동적계획을 위해 계산된 결과를 저장할 이차원 배열 D[][]와 간선들의 가중치를 저장할 배열 W[][]가 있어야겠다. 그럼 여기서 문제되는게 A로 표기된 'V-{vi}' 요녀석을 어떻게 표현 할껀지가 이번 동적계획의 핵심이 되겠다.
검색을 좀 해보게되면 배열(?) 또는 리스트로 담는다는 분들도 있고, bit로 해서 표현한다는 분들도 있는데.. 난  bit로 하기로 결정!
bit로 하게 되었을때 간단히 보면 v1,v2,v3,v4가 있을 때 v1,v2가 포함되어 있다면 0011로 표시될수 있다. 흠 이렇게 하면 이해가 잘 되지 않지만 아래를 보면
 


V4

V3

V2

V1

십진수

모든 정점이 포함되지 않음

0

0

0

0

0

정점 V1이 포함

0

0

0

1

1

정점 V2가 포함

0

0

1

0

2

이렇게 표로 나타내보면 이해가 쉬울 것이다. 하지만 이방법에도 불필요한 메모리 공간을 사용한다는 문제점이 존재하고 이문제가 TSP를 해결하는데 정점의 수가 제한되게 된다.
이제 본격적으로 코드를 살표보기로 하자!


Posted by hazeyun
TAG

댓글을 달아 주세요