-1

MST를 사용하여 TSP에 대해 가장 최적의 (또는 최적에 가까운) 상한을 찾는 가장 효과적인 방법이 무엇인지 궁금합니다. 속도를 위해 알고리즘을 최적화하려고하지만 MST를 찾은 후 알고리즘 적으로 "양호한"경계를 계산하는 데 문제가 있습니다. 베이스 바운드는 2 x MST length이 될 것입니다. 그러나 이것이 우리가 할 수있는 최선의 방법은 아닙니다. 모든 참조 또는 통찰력은 인정 될 것이다.MST를 사용하여 TSP에 대한 가장 효과적인 상한 찾기

답변

0

아마도 MST를 둘러보기로 변환해야하며 선형 시간 내에 2 * MST 길이보다 작은 바운드를 제공해야합니다. 크리스토프의 알고리즘 (Christofide 's Algorithm)이라 불리는 MST의 확장도 있습니다.

TSP heuristics에 대한 위키 백과 페이지를 살펴 보시기 바랍니다.