여행 세일즈맨에게 수정

Question

여행 세일즈맨 문제에 대한 최적화 알고리즘에 대해 현재 배우고 있으며 실제 문제 자체를 변경하지 않고 문제를 수정할 수 있는지 궁금합니다. 그 모호한 소리가 나는 경우에, 저를 명확히하자 :

TSP의 결정 버전, 나는 그것을 이해, 다음과 같은 요청 :

정점 G와 비용 C의 목록을 감안할 때,이다 거기 P의 비용이 기껏해야 c가되도록 해밀 토니안 경로 P?

이 질문의 일반성 및 NP 완전성을 이해합니다. 그러나, 나는 생각하는 것이 더 직관적 질문의 수정 된 버전 발견 :

정점 G 특정 해밀턴 경로 P의 목록을 감안할 때이 같은 다른 해밀턴 경로 P의 *가 그 P의 비용 * P보다 작습니까?

매개 변수는 약간 다릅니다. 첫 번째는 전체 비용을, 두 번째는 전체 비용을 형성하는 정점의 전체 시퀀스를 제공합니다. 내가 궁금해 한 것은 첫 번째 질문을 일반성을 잃지 않고 두 번째 질문으로 줄일 수 있습니까? 분명히, P의 비용을 간단히 계산하여 두 번째를 첫 번째로 줄일 수 있습니다. 그러나 첫 번째에서 두 번째로 줄이는 것은 내 손아귀에서 벗어났습니다. 이 분야에 도움을 주시면 대단히 감사하겠습니다.

Answer 1

감소 시키려면 평가를 최단 경로 비용 인 c보다 엄격하게 요구해야합니다.

이 작업은 TSP가 c = 0으로 설정하고 반환 된 경로가 원하는 c보다 큰지 여부를 묻는 방법으로 TSP에서 줄이기 때문에 원래 TSP만큼 어렵습니다.

따라서 감소 자체는 NP 하드입니다. 그럼에도 불구하고 원본 TSP (경로를 반환하는)를 반복적으로 적용하여 그래프에 나타나는 가장자리 길이의 가장 작은 차이만큼 점진적으로 증가 시켜서 원래 질문에 대해 원하는 단계보다 한 단계 더 높은 단계에서 시작하여 형성 할 수 있습니다.