동적프로그래밍_TSP문제_GDI_MFC_VS2008_소스및한글파일
- 최초 등록일
- 2009.05.13
- 최종 저작일
- 2009.05
- 12페이지/
압축파일
- 가격 1,000원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
소개글
본 압축파일은, 소스코드와 그와 관련된 자료-한글문서가 포함되어 있습니다.
TSP문제의 응용으로, 외판원이 출발점과 도착점이 같지 않고, 20*20 매트릭스에서 좌측상단에서 출발하여 우측하단으로 도착함으로 문제를 제시하여 해결하였다.
동적계획법을 응용한 TSP문제를 무작정알고리즘과 동적알고리즘의 두가지 방법으로 풀어냈다.
MFC의 GDI를 이용하였기 때문에 시각적으로 정보를 접할수 있고, 실행시간까지 출력하였기 때문에, 두가지 알고리즘의 성능까지 테스트할수 있다. 또한 한글파일을 첨부하여 소스코드와 관련된 내용조사까지 쉽게 접할수 있다.
프로그램의 크기를 줄이기 위해 Document형식의 SDK로 작성하였으며,
소스코드는 VS2008 버전으로 작성하였다.
컴파일 실행환경
Visual studio 2008
본문내용
void CleastPath_mfcView::TSP(void)
{
int h, i, j, k, min_j; // 설명2
double min; //설명3
min_j = 0;
arr= new int[n+1];
for(int i=0; i<n+1;i++)
arr[i] = 0;
for ( i = 2 ; i <= n ; i++ )
{ // A집합이 공집합인 경우
D[i][0]=Weight[i][ran+2]; //설명4
// 원점을 끝점으로 설정
}
for ( k = 1 ; k <= n-2 ; k++ )
{
for ( h = 1 ; h < nn ; h++ ) //설명5
{
if ( k == num(h) ) //설명5
{ // A집합의 원소의 개수가 k개인 경우
for ( i = n ; i >= 2 ; i-- ) {
if ( arr[i] == 0 ) {
min = 99999;
for ( j = n ; j >= 2 ; j-- ) {
if( arr[j] == 1 &&
( min > Weight[i][j] + D[j][h-(int)pow(2.0,j-2)]) )
{
min = Weight[i][j] + D[j][h-(int)pow(2.0,j-2)] ;
min_j = j;
} D[i][h] = min; //최소값저장 //설명6 Path[i][h] = min_j; //최단경로저장 //설명6
}
}
}
}
}
}
참고 자료
TSP문제
다이나믹프로그래밍
최단경로