TSP (Traveling Salesman Problem) 정의 중 하나는 다음과 같습니다.TSP- 변형, 가능한 알고리즘?
삼각형 부등식이 유지되는 가중치 완전 무향 그래프에서 최소 총 무게의 해밀턴 경로를 반환합니다.
제 경우에는 해밀턴 경로를 원하지 않습니다. 두 개의 잘 알려진 꼭지점 사이의 경로가 필요합니다. 따라서 공식은 다음과 같습니다.
triangle inequality가 유지되는 두 개의 특수 정점과 원본 및 대상이라는 두 개의 특수 정점은 모든 노드를 정확히 한 번 방문하고 소스에서 시작하여 대상까지 끝나는 최소 가중 경로를 반환합니다.
해밀턴 경로는 각 꼭지점을 정확히 한 번 방문하는 무향 그래프의 경로입니다.
근원적 인 문제에 대한 좋은 근사법 (가장 좋은 솔루션의 3/2)은 Christodes의 알고리즘입니다. 제 경우를 수정할 수 있습니까? 아니면 다른 방법을 알고 있습니까?
대상 노드에서 비용 노드 0으로 가장자리 (= 도로)를 추가하면 TSP (삼각형 부등식이 유지되지 않음)가 있습니다.
"여행 세일즈맨의 추구"라는 책에서이 기술에 대해 간략하게 설명합니다.
그래프가 완료되었습니다. 이미 소스와 대상 사이에 모서리가 있습니다. 나는 체중을 바꾸는 것이 의미가 있다는 것을 확신하지 못합니다. 그거야? –
나는이 아이디어를 얻었다 고 생각한다. 가중치가 0 인 두 개의 가장자리 만있는 버텍스를 소스 및 대상에 추가합니다. 마지막으로 새 그래프에서 해밀턴 경로를 계산합니다. 0 가중치는 소스와 대상이 연속되도록합니다. 여분의 노드와 상대 에지를 제거하면 솔루션을 얻게됩니다. –
dijkstra의 알고리즘을 사용하여 경로 정보를 위해 각 노드에 여분의 책을 보관하지 않는 이유는 무엇입니까? 즉, 소스로부터의 특정 꼭지점에 대한 최단 경로에서 전달 된 꼭지점의리스트.
끝점에 도달하면 멈 춥니 다. 그러면 경로는
현재 가장자리의 시작점 + 현재 가장자리 경로입니다.
여기서 현재 가장자리는 목적지로 연결되는 마지막 가장자리입니다.
모든 노드를 정확히 한 번 방문해야합니다. –
각 꼭지점을 정확히 한 번 방문해야한다는 제약이 있습니까? – bloops
........................ 고정. 감사. –
가치가있는 경우 시작/끝 정점이 지정된 해밀턴 경로 문제의 변형을 "제한된 해밀턴 경로"라고도합니다. – mhum