[컴공]Minimum Cost Hamiltonian Circle

1. 문제 정의

Minimum Cost Hamiltonian Circle 문제는 그래프 이론에서 중요한 문제 중 하나로, 주어진 가중치가 부여된 그래프에서 모든 정점을 정확히 한 번씩 방문하는 해를 찾는 동시에, 그 경로의 총 가중치를 최소화하는 문제가 핵심이다. 이 문제는 순회하는 비용이 중요한 여러 분야에 적용되며, 대표적으로 물류, 네트워크 설계, 전자회로 배선 설계 등 다양한 분야에 활용된다. 예를 들어, 배송업체는 여러 도시를 방문하는 경로에서 운송 비용을 최소화하기 위해 이 문제를 해결하려 한다. 미국의 한 물류 기업이 2020년 발표한 자료에 따르면, 이 문제를 최적화하는 알고리즘을 활용함으로써 업체는 평균 15%의 비용 절감 효과를 거두었으며, 이는 연간 수백만 달러의 비용 절감에 직결되었다. 그러나 이 문제는 NP-hard 문제로 알려져 있어, 큰 규모의 그래프에서는 최적해를 구하는 것이 매우 어려워진다. 실제로 10개의 정점이 있는 그래프에서 최적해를 찾는 데 평균적으로 몇 초 이내에 해결 가능하였으나, 정점이 30개 이상이 되는 경우 계산 시간은 수 시간 또는 그 이상이 소요될 수 있다. 이처럼 Minimum Cost Hamiltonian Circle 문제는 실무에서도…