| [ QuizWit ] in KIDS 글 쓴 이(By): ymir ( 마법기사) 날 짜 (Date): 1999년 10월 10일 일요일 오후 10시 55분 34초 제 목(Title): [Q] TSP 를 다이나믹 프로그래밍으로..? CnUnix 보드에 올렸다가, 알고리즘은 여기가 나을 듯 싶어.. 여기로 옮깁니다... TSP(Traveling Salesman Problem) 을 다이나믹 프로그래밍으로 구현하는건데여.. 다이나믹 프로그래밍에 대한 개념이 잘 안 잡히네여... 알고리즘을 보니까... 전체 vertex에 대한 모든 subset 을.. 배열에 넣구나서... (2^(n-1)*n 개의 배열이 필요하더군여..) 그 배열에 순서대로 최소값을 채우는 식이던데... 굳이 배열에 넣지않구... 리커시브 콜을 해도 상관은 없는지여..?? n 이 충분히 커지면 배열로는 감당 할 수 없을 듯... 또한 리스트를 쓴다해도... 서브셋을 비교해서 값을 추출하는 코스트도... 만만찮으니... 리커시브와두 별 차이 없을 듯 보이네여... 참고루 알고리즘을 적어 보겠습니다.. void travel(int , const number W[][], index P[][], number& minlength;) { index i, j, k; number D[1..n][subset of V-{V1}]; for(k=1; k<=n-2; k++) for(all subsets A ⊆ V-{V1} containing k vertices) for(i such that i!= 1 and Vi is not in A) { D[i][A] = minimum (W[i][j] + D[Vj][A-{Vj}]); Vj∈A P[i][A] = value of j that gave the minimum; } D[1][V-{V1}] = minimum (W[1][j] + D[Vj][V-{V1}]); P[1][V-{V1}] = value of j that gave the minimum; minlength = D[1][V-{V1}]; } n 은 vertex 의 수, W[i][j] 는 i->j 의 weight Vn 은 vertex n 입니다... 냠.. 어떻게 짜야 잘 짰다구 소문이 날지.. 크크.. --; 글고 혹시 다이나믹 프로그래밍에 관해 참조할 만한 사이트나 자료 같은거.. 알고 계시면 좀 알려 주세여~~ 웹에서 아무리 서치를 해바도... 찾을 수가 없네여... 없는건지.. 못찾는건지... --; 그럼 답변 기둘리겠습니다.. ^^; ... the Magic Knight! *Mizz* http://opera.cse.cau.ac.kr/~ymir |