수학 7대난제 외판원 문제를 풀어보다.-연구저자 하늘나비

TSP외판원문제

외국인을 위한 블로그 준비 중...htps://nsnlgf.blogspot.com/

외판원 문제는 외판원 k가 미국 보스턴에서 출발하여 9개 도시를 돌고 되돌아오는 문제다. 단, 비행기를 타고. 가장 싼 비행기 티켓은?

사실 시간과 상관없이 여행비를 싸게 할 거라면, 배를 타고 기차를 타고 이동하면 훨씬 여행경비를 싸게 다닐 수 있다. 야간열차를 타서 숙비를 아끼고, 버스를 타고 가까운 곳을 돌아보고, 그런데 배와 기차로 이동할 시에 시간은 엄청 많이 들게 된다. 따라서 이동거리를 단축시키게 될 때 시간을 절약할 수 있게 되며, 거리를 단축시킬 때 비행기 연료도 줄어들게 되므로 비행기 티켓도 그만큼 다운될 테니까. 따라서 외판원 여행문제라기보다 이동거리 패턴 문제라고 정리해야 한다. 이 문제가 원하는 것은 비행기 이동 경로를 가장 짧게 잡아, 비행기 티켓 값을 아끼는 것이다.

지구본을 놓고 보면 좀 더 쉽게 알 수 있다.

여기서 우리는 물음을 던져봐야 한다.

왜 보스턴이 출발점인지에 대해서 말이다.

이 문제를 만들어낸 사람이 바로 미국인이기 때문이다. 즉, 보스턴에 사는 사람이며, 자신의 국가가 세계 중심으로 놓고 문제를 만들었기 때문이다. 한국이나, 중국을 추가하거나, 독일, 네덜란드 대륙이 포함되었다면 지구는 둥글 듯이 그냥 일직선 문제가 되어버린다. 즉, 미국을 중심으로 잡고 세계를 연결하기 위해선 바다를 기준으로 붙은 국가들로 만들어졌다고 볼 수 있다.

경로의 수

9!=1⨯2⨯3⨯4⨯5⨯6⨯7⨯8⨯9=362880

A)Boston⟷1,London⟷2,paris⟷3,Roma⟷4,Madrid⟷5,Washington⟷6,LA⟷7,Tokyo⟷8,Seattle⟷Boston

B-1)Boston⟷1,New York⟷2,London⟷3,paris⟷4,Roma⟷5,Madrid

⟷6,Washington⟷7,LA⟷8,Tokyo⟷9,Seattle⟷Boston

B-2)Boston⟷1,London⟷2,paris⟷3,Roma⟷4,Madrid⟷5,New York

⟷6,Washington⟷7,LA⟷8,Tokyo⟷9,Seattle⟷Boston

B-3)Boston⟷1,London⟷2,paris⟷3,Roma⟷4,Madrid⟷5,Washington

⟷6,New York⟷7,LA⟷8,Tokyo⟷9,Seattle⟷Boston

B-4)Boston⟷1,London⟷2,paris⟷3,Roma⟷4,Madrid⟷5,Washington

⟷6,LA⟷7,Tokyo⟷8,Seattle⟷9,New York⟷Boston

최종 경로 4개이므로 P=NP가 성립.

뉴욕 포인트이므로 뉴욕을 제거했을 때 타원형태가 된다. 그냥 따라서 연결해주면 된다. 포인트 기준 가장 가까운 곳을 연결했을 때 4개의 경로가 만들어진다.

참고, 포인트 기준 중앙으로 1/2로 나눠주고 중앙을 넘어서는 안 된다. 중앙을 넘었을 때 되돌아올 때 다시 중앙을 넘게 되므로 길이가 늘어나게 된다. 또한 선이 엉켜서도 안 된다. 한붓그리기와도 같다. 단순하게 외판원문제만 놓고 봤을 때 외판원문제는 아주 간단한문제다. 따라서 P=NP가 성립한다. 물론 문제에 따라 복잡도는 훨씬 늘어난다. 다만 외판원문제 자체에서 봤을 때 아주 간단한 문제다.

 

이동거리 패턴 방정식 1→2→3→4→5

1, 출발지 포인트를 바꿔 복잡도를 제거한다.

출발 포인트에서 가장 가까운 곳을 선택함. 예를 들면 외판원문제에서 보스턴에서 출발지일 때 최소 세 방향이 만들어진다. 그러나 도쿄에서 출발지를 선택했을 때 2방향으로 줄어든다. n! 이동거리가 하나가 더 늘어날 때의 경로의 수

7!=5040<8!=40320<9!=362880<10!=3628800<11!=39916800

2, A형 x,y 유턴1/2로 나눠줘 경로의 수를 줄인다.

평면 유턴 기준 좌우 x,y 1/2로 나눠 중앙을 넘어선 안 된다. 중앙을 넘었을 때 다시 중앙을 넘게 되므로 유턴하여 되돌아올 때, 길이는 늘어난다. 한붓그리기, 선이 한번이라도 겹쳐서는 안 된다. 선이 겹치는 수만큼 이동거리는 늘어난다. 해밀턴그래프에서 쉽게 증명되며, 해밀턴회로보다 빠른 회로의 경로를 구할 수 있다.

3, 1,2를 만족시키며 가장 가까운 거리로 이동한다.

xy1/2 유턴시 중앙기준으로 가까운 곳일지라도 자연스럽게 무시하게 된다. xy1/2기준을 세우지 않았을 때, 가까운 곳을 최우선으로 생각하게 될 때 중앙을 넘게 되며, 중앙을 넘었을 때 유턴하여 되돌아올 때 중앙을 넘었던 곳을 지나치게 되며, 길이는 그만큼 늘어나게 된다. 중앙을 넘는 경우 부분분할계산을 해야 한다.

4, 분할계산 복잡한 포인트를 분리하여 계산함.

부분분할계산, 복잡한 곳을 나눠 그 복잡한 곳만 따로 계산하여 최소거리를 구하고 다시 연결해준다. 전체 한 번에 계산하게 될 때, 시간과 복잡도가 높아진다.

선이 겹치는 것을 배제

x그룹

a=(T→S→N→B ≧≦T→S→B→N)

b=(N→Lo→P→R ≧≦B→Lo→P→R)

y그룹

c=T→L→W→N≧≦T→L→N→W

d=N→M→R→P≧≦W→M→R→P

x(ab)+y(dc)그룹을 합해서 가장 빠른 경로.

5, 불필요한 경로의 수를 줄인다.

9!에서 쉽고 완벽한 부분경로를 제거하게 될 때 경로의 수는 줄어들게 되며, 경로의 수가 줄어든 만큼 문제는 쉬워진다.

 

독도에서 출발했을 때, 외판원문제와 같다. 여기에 1나를 더 놓았을 때

경로의 수

10!=3628800→⨯½(반복)

9!에선 4개의 경로에다가 10!에서 2개의 경로가 추가 되므로 총 6개의 경로가 만들어진다.

구인 경우 비행기경로가 존재하지 않으므로 제외 된다. 그냥 참고.

구를 기준으로 잡았을 때 구를 한 바퀴 돌았을 때 원래 위치로 되돌아오게 된다. 따라서 직선이라고 봐도 무관하다. 따라서 가장 빠른 곳을 선택하게 될 때 빠른 경로가 만들어진다. 이때 빠른 경로의 약 3,4개의 경로가 만들어진다. 즉 평면과 구를 합치더라도 8개 이하의 경로가 만들어지며, 경로의 수는 9!⨯2가 된다. 또한, 왕복으로 측정된 것이므로 !/2가 된다.

A)Dokdo→1,LA→2,Seattle→3,Boston→4,New York→5,Washington→6,Madrid→7,Roma→8,paris→9,London→Dokdo

구는 원이므로 자연스럽게 출발지로 되돌아오게 되므로 직선이라고 봐도 무관하다. 포인트, (se, LA), (ma, Ro, Pa, Lo) 이 두 개의 포인트 계산만 해주면 나머지는 직선으로 연결해주면 된다. (se, LA=경로 수 2)+(ma, Ro, Pa, Lo=경로 수 4개)= 최대 경로 수 6개. 가장 가까운 곳을 우선시 함.

ma, Ro, Pa, Lo 중 하나의 도시가 마지막 도시가 되며, 그대로 출발지로 되돌아오게 된다. 구는 직선과 같으니까. 이처럼 부분 포인트를 잡아주고 부분 계산을 해줄 때 경로의 수는 줄어들게 된다. 즉, 인간이 쉽게 빠른 경로의 값을 얻을 수 있다. 따라서 외판원문제는 np=p가 된다.