어떤 TSP 휴리스틱 알고리즘을 채택해야합니까?

TSP 휴리스틱 알고리즘과 관련하여 엄청난 양의 논문이 있으며, 각각은 여러 종류의 TSP 문제에 집중할 수 있습니다. TSP 문제의 "도시 크기"는 30과 같습니다.어떤 TSP 휴리스틱 알고리즘을 채택해야합니까?

2013-06-18 tookoo

개미 식민지 최적화 – Regenschein

이 질문은 주로 의견 기반입니다. 알고리즘 선택에 대한 객관적인 기준을 제시하십시오. 속도? –

Tabu Search, Simulated Annealing 및 Late Acceptance 모두 나를 위해 잘 작동합니다. for example.

2013-06-18 11:59:14

공간 채우기 곡선은 매우 빨리 해결할 수 있습니다. 그런 다음 k-opt 또는 무언가를 사용하여 가장자리를 개선 할 수 있습니다. 예를 들어 Gebweb tsp solver와 같은 Ant Colony Optimization도 있습니다. 그것은 또한 무력과 역동적 인 해결책을 가지고 있습니다.

출처

2013-06-18 12:10:33 Bytemain

-1

여행 판매원이 미터법 (삼각형 부등식을 존중하는 경우)보다 다항식 인 근사 알고리즘을 사용하는 것이 좋습니다. 항상 최적의 알고리즘보다 최대 X 시간이 더 나쁜 솔루션을 반환합니다. 예를 들어 Christofides algorithm은 경로가 최적 경로보다 1.5 배 이상 길다는 것을 보장합니다.

출처

2013-06-19 12:54:04 malejpavouk

Christofides 알고리즘은 작성하기가 매우 어렵습니다. – Bytemain

그래,하지만 페이지에 또한 2- 스패닝 트리를 사용하는 근접 알고리즘입니다. 그리고이 알고리즘은 구현하기가 쉽습니다. 나는이 목적을 위해 afaik 최첨단 기술이고 질문은 일반적인 것 (나에게 : 구현하기 쉬운 알고리즘을 제공하라)이기 때문에 나는 christofides를 언급했다. – malejpavouk

내가 무례한 경우에 사과하지만있다. christofides에 대한 실제적인 사용은 거의 없다. – Bytemain

어떤 TSP 휴리스틱 알고리즘을 채택해야합니까?

답변

관련 문제