티스토리 뷰
TSP(Traveling Salesman Problem)
모든 노드를 단 한번씩만 순환하는 최소 경로 계산 문제
노드1을 시작으로 최소 경로 계산 방법
->집합 A의 크기를 0 부터 시작하여 DP를 이용해 계산
DP(Dynamic Programming)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
간단히 말하자면 답을 재활용하는 것으로 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하는 것.
슈도코드
참고
http://blog.naver.com/PostView.nhn?blogId=57gate&logNo=60159523081
https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95
댓글