tsp 알고리즘 코드 설명좀 부탁드립니다..급급ㅜㅜ
이치코
제가 짠것은 아니고요 알고리즘 공부하고 있는데요...int travel() 함수가 이해가 안가요...int 변수들을 한개씩 대입해서 해보려구 해도 잘 모르겟요...ㅠㅠ조그만 도와주세요~ 그리고 시간이 되시면void mininum(int i, int A) 함수설명도 부탁드려요
#include stdio.h#include stdlib.h#include math.h#include windows.h //시간 구하기위해 필요한 헤더파일int **W; //인접행렬 입력값int **D; //최단경로 저장배열int **P; //P[Vi][A] = D[Vi][A]의 최단경로로 갈때 처음가는 원소int *subset; //각 부분집합이며, 원소갯수를 저장한다.
int max; //부분 집합 최대 원소 갯수int node_EA; //정점의 갯수
void mininum(int i, int A){ int j,s; //A는 각 정점에서의 부분 집합 D[i][A]=1000; // ∞(1000)로 초기화 for(j=0; jnode_EA; j++){ s=(int)pow(2,j); //pow함수로 지수승 구하기 2^j if((A & s)!=0){ //V1 is not in A if(D[i][A]W[i][j]+D[j][A-s]){ D[i][A]=W[i][j]+D[j][A-s]; P[i][A]=j; //j의 최소값 저장 } } }}
int travel(){ //경로 구하기 int i,k,A; int minlength; for(i=0; inode_EA; i++) D[i][0] = W[i][0]; for(k=1; k=node_EA-2; k++) { for(A=0; Amax; A++) { //all subset A는 자신을 뺀 나머지 k개의 정점을 포함한 부분집합 if(subset[A]==k && (A&1)==0) { for(i=0; inode_EA; i++) { if(A & (int)pow(2,i)) continue; mininum(i,A); } } } } mininum(0,max-2); minlength = D[0][max-2]; return minlength;}void path(int i, int A) //경로를 출력 하는 함수{ int j=P[i][A]; printf(V%d - , i+1); if(A-pow(2,j)!=0) path(j,(int)A-pow(2,j)); else printf(V%d - V%d\n,j+1,1);}
void print(int min_lenth) //화면에 결과 출력 함수{ int i,j,a; if(min_lenth=1000) printf(불가능한 경로입니다.); else { printf(\n 입력 파일 \n\n); for(a=0; anode_EA; a++) { if(a==0) printf(\t); printf([V%d]\t,a+1); } printf(\n); for(i=0; inode_EA; i++) { printf([V%d]\t,i+1); for(j=0; jnode_EA; j++) { if(W[i][j] == 1000) printf( ∞\t); else printf( %d\t,W[i][j]); //배열값 출력 } printf(\n); } printf(\n); for(i=0; inode_EA;i++) { printf(--------); } printf(\n\n); printf(최소 경로 : ); //경로출력 path(0,max-2); printf(\n경로의 거리 : %d \n\n,min_lenth); //최소비용 출력 }}
int main(){ static char *inFile = test2.txt; //읽을 화일명 int i,j; //for문에 사용되는 변수 int tmp,middle_max, subset_count; //부분집합 개수 구하기위해 필요한 변수 int min_lenth; //최단 길이 경로 //High-resolution performance counter를 이용하여 코드의 수행 시간을 측정 LARGE_INTEGER liCounter1, liCounter2, liFrequency; FILE *fp; fp = fopen(inFile, r); if(!fp){ printf(읽을 파일이 없습니다.\n); fclose(fp); exit(1); } else{ fscanf(fp,%d\n,&node_EA); //파일로 부터 정점의 갯수 읽기 max = (int)pow(2,node_EA); //부분집합 최대 갯수 W=(int**)malloc(node_EA*sizeof(int)); //각 배열들 메모리 할당 D=(int**)malloc(node_EA*sizeof(int)); P=(int**)malloc(node_EA*sizeof(int)); subset=(int*)malloc(max*sizeof(int)); for(i=0;inode_EA;i++) { D[i]=(int*)malloc(max*sizeof(int)); P[i]=(int*)malloc(max*sizeof(int)); for(j=0;jmax;j++) { D[i][j]=P[i][j]=0; //배열 D,P 초기화 } } for(i=0;inode_EA;i++) { W[i]=(int*)malloc(node_EA*sizeof(int)); for(j=0;jnode_EA;j++) { //파일로 부터 가중치 읽어서 배열 W에 저장 fscanf(fp,%d,&W[i][j]); } } } fclose(fp); for(i=0; imax; i++) //각 정점에서의 부분집합 갯수 구하기 { tmp=i; middle_max = max/2; subset_count=0; while(tmp0) { if(tmp-middle_max=0) { tmp=tmp-middle_max; subset_count++; } middle_max = middle_max / 2; } subset[i]=subset_count; }// 주파수(1초당 증가되는 카운트수)를 구한다. QueryPerformanceFrequency(&liFrequency); QueryPerformanceCounter(&liCounter1); // 코드 수행 전 카운트 저장 min_lenth = travel();//최소 경로 찾기 QueryPerformanceCounter(&liCounter2); // 코드 수행 후 카운트 저장 print(min_lenth); //결과 출력 printf(수행 시간 = %f 초\n, (double)(liCounter2.QuadPart - liCounter1.QuadPart) / (double)liFrequency.QuadPart); for(i=0;inode_EA;i++) //각 배열들 메모리 할당 해제 하기 { free(W[i]); free(D[i]); free(P[i]); } free(D); free(P); free(subset); free(W); return 0;}
