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