여행 세일즈맨 - 2-Opt 개선

Question

그래서 여행 세일즈맨 문제에 대한 2-opt 개선에 대한 설명을 찾고 있었지만 그 점에 관해서는 알지만 한 가지를 이해하지 못합니다.

나는 생성 된 경로의 두 가장자리가 서로 교차하는 경우 두 점을 전환 할 수 있으며 더 이상 교차하지 않는다는 것을 알고 있습니다. 그러나 두 개의 가장자리가 교차하는지 여부를 어떻게 결정할 수 있는지 이해할 수 없습니다. 내 질문에 명확하게하려면

, 이것은 내가 지금까지 한 일이다 (나는 자바를했다)

1. 내가 X로, 도시를 대표하는 Point를라는 개체를 가지고 y 좌표 .
2. List에 포함 된 Points 집합을 가진 PointSet이 있습니다.
3. 나는 가까운 이웃 알고리즘을 통해 상당히 짧은 방법으로 PointSet을 배열 computeByNN()라는 방법이 있습니다.

그래서 이제 정렬 된 PointSet (최적은 아니지만 여전히 짧음)이 있으며 2 개를 선택하고 싶습니다. 그러나, 나는 어디에서 시작해야할지 모른다. 각 라인 세그먼트를 점검하여 교차하는지 확인해야합니까? 그렇다면 두 포인트를 전환하십시오. 나는 그것이 휴리스틱 스의 목적을 무효화하고 일종의 무차별 한 해결책이되는 것처럼 느낍니다. 투어의 두 세그먼트가 교차하는지 확인하는 효율적인 방법이 있습니까?

질문이 명확하지 않은 경우 애원을 표시합니다. 누구든지 나를 필요로한다면 더 명확하게 편집하려고 노력할 것입니다.

Answer 1

좋아하는 경우 룩업 테이블을 만들어 교차 가장자리를 감지 할 수 있습니다. n = 1000의 경우, 10^12 개 항목은 분명히 너무 사치 스럽습니다. 그러나 당신은 아마 짧은 가장자리에 대해 가장 걱정하고 있습니까? 각 노드에 대해 가장 가까운 이웃 노드의 √n에 에지를 포함 시키려고했습니다. 그렇다면 당신은 단지 메가 바이트의 공간과 어쨌든 O (n^2) 전처리 영역에 있습니다. 거기에서 그것은 휴리스틱 한, 행운을 빌어 요!

또한이 작업은 즉시 수행 할 수 있습니다.