외판원 문제

외판원 문제

• W: 주어진 그래프 G=(V,E)의 인접 행렬
• V: 모든 도시의 집합
• A: V의 부분집합
• D[vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 vi에서 v1으로 가는 최단 경로 길이

주어진 그래프 G=(V,E)

• 인접행렬 W의 구성
  

• 비용을 추측 해야 되는데 실제 비용보다 작아야 된다

• 비용추측(=어림비) <= 실제비용

• A로 다시 돌아와야하므로 A로 돌아오는 최소값인 0이니 16+0보다는 크거나 같다
• 가로는 나가는데 드는 비용 세로는 들어오는데 드는 비용

• 각 행과 열의 최소항을 더해준다

• 어림수=20 실제비용보다 작거나 같다

• 각 행과 열이 0인 원소가 있게 한다

• b로 갈 경우 b에 머물러 있으면 안되므로 b열은 무한으로
• b에서 다시 a로 가면 안되므로 무한으로
• 나머지 동일

• 가로 세로에 0이 하나씩 있도록 축소
• 비용이 작은거 부터 탐색

• 비용작은 b에서 다시 탐색