우리는 여행 세일즈맨 문제의 해답을 나타내는 순환 목록을 가지고 있다고 가정 해보십시오. 이 목록은 처음에 비어 있습니다.여행 세일즈맨 건설적인 경험적 발견
사용자가 도시를 입력 할 수 있고 하나씩 좌표를 지정할 수 있다면 어떤 경험적 방법을 사용하여 에 삽입 할 수 있습니다. 이미 존재하는 둘러보기에 좌표가 삽입되어 있습니까?
예는 가장 가까운 이웃의 발견 적 방법을 사용합니다 : 그것은 가장 가까운이 투어에서 이미 조정 한 후 새로운 좌표를 삽입합니다.
다른 옵션 (가능하면 의사 코드)은 무엇입니까?
당신은 물론 당신이 언급 한 아이디어를 일반화 할 수
는 k 번째 경로를 계산하는 O(|V|^k) 것을 k'th_path(v) = minimum weight of a path including max{k,not_visited cities} cities
정의 주
특별한 경우 [이 결합하지 꽉] :
k=1의 경우 가장 가까운 이웃인 a 당신이 제안했습니다.k=|V|에 대한 최적의 솔루션을 얻을 수 있습니다. [매우 커지기에주의하십시오].감사합니다. amit !! 이것은 정확히 내가 찾던 답변의 종류입니다. 코드가없고, 경험적 발견에 대한 설명 일뿐입니다. 너에게 충분히 감사 할 수 없다. – Fatso
TSP는 항상 가장 가까운 좌표를 찾으므로 다른 발견 적 방법은 없습니다. 적어도 좌표를 삽입하고 가장 가까운 좌표를 알 수있는 알고리즘을 모르지만 좋은 둘러보기를 찾을 수있는 충분한 알고리즘이 있습니다. 좋은 추론은 예를 들어 Christofides 알고리즘입니다. 이것은 공룡 공간에서만 작동하지만 최적의 3/2 이내에 솔루션을 보증합니다. 코드 작성이 쉽지 않습니다. 특히 edmond blossom v 알고리즘은 숙련 된 기술을 필요로합니다. 드물 긴하지만 귀사의 방법이 비 감각을 제공 할 수 있다는 것을 어떻게 설명 할 것이기 때문에 보증의 중요성은 충분히 높지 않습니다.
첫 번째 맞춤, 첫 번째 맞춤 감소, 최상 맞춤, 최저 맞춤 감소 및 가장 저렴한 삽입과 같은 다양한 휴리스틱 방법을 사용할 수 있습니다. 이러한 구성 휴리스틱은 일반적으로 빈 포장에 적용되지만 TSP로도 변환 될 수 있습니다. Documentation about those heuristics is here.
만 시간에서 1 할당되지 않은 개체를 삽입하고 있기 때문에, 이들 모두는 기본적으로 당신이 가장 가까운 이웃이 (관계에 약간의 변화에) 발견,하지만 그건 그들이 일반적으로하지 않습니다 있습니다 부르는로 복귀 가장 가까운 이웃에게 전화하십시오. 가장 가까운 이웃은 항상 줄 끝 부분에 할당되지 않은 모든 항목의 가장 가까운 이웃을 추가합니다.
지금 당신이 정말로 원하는 것은 전체 건설 휴리스틱 스를 다시 시작하지 않아도 괜찮은 해결책입니다. 더 어렵습니다. repeated planning and real-time planning (및 this documentation)에 오신 것을 환영합니다. 저는 실시간 계획을 수행하는 TSP 및 차량 라우팅을위한 오픈 소스 예제를 개발 중입니다.
숙제 같은 냄새 ... – Stefan
나에게 코드를 줄 필요가 없습니다. 숙제 였다면 코드를 요청할 것이고, 나는 필요가 없습니다. 내 앱을 최적화하고 내 옵션이 무엇인지 확인하고 싶을뿐입니다. – Fatso