외판원 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 잔글편집 요약 없음 |
잔글편집 요약 없음 |
||
4번째 줄:
여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가?
[[그래프 이론]]의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 [[완전 그래프]](weighted complete graph)에서 가장 작은 가중치를 가지는 [[해밀턴 순환]]을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 [[계산 복잡도 이론|계산 복잡도]]는 변하지 않는다.
== 응용 ==
| |||