[이산수학] 해밀턴 경로(Hamiltonian path), 해밀턴 순회 (Hamiltonian circuit)

해밀턴 경로

해밀턴 경로 (Hamiltonian path)
그래프에서 모든 정점을 오직 한 번씩 지나는 경로. 시작점으로 돌아오지 않음

 

해밀턴 순회

해밀턴 순회 (Hamiltonian circuit)
그래프에서 모든 정점들을 오직 한 번씩만 지나는 순회

 

외판원 문제

외판원 문제 (traveling salesperson problem)
방문해야 할 도시들과 도시들 사이의 거리가 주어짐. 외판원이 특정 도시에서 출발해 각 도시를 한 번씩 방문하며 모든 도시들을 거쳐 처음 출발한 도시로 되돌아올 때 최소 비용이 드는 경로를 찾는 문제

외판원 문제는 해밀턴 순회를 응용한 문제입니다. 따라서 해밀턴 순회와 같이 외판원 문제는 다항 시간 안에 푸는 알고리즘이 발견되지 않아 NP-난해 문제에 속합니다.

 

이 문제는 정점의 개수 $n$이 작을 때에는 브루트 포스로 접근할 수 있습니다만, 시간이 매우 오래 걸려 문제를 푸는 방법으로 일반화 할 수는 없습니다.