su1433.log
로그인
su1433.log
로그인
외판원 문제
suhan cho
·
2022년 6월 8일
팔로우
0
알고리즘
0
외판원 문제
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에서 다시 탐색
suhan cho
안녕하세요
팔로우
이전 포스트
전송층
다음 포스트
외판원 문제
0개의 댓글
댓글 작성