~ 안에 이전 게시물 , 나는 미국의 모든 주요 고속도로를 가로지르는 로드 트립 맵을 만들기 위한 계획을 세웠습니다. 네트워크를 설정하는 방법과 경로를 찾는 데 사용한 알고리즘에 대해 논의했습니다. 이 게시물에서는 내가 찾은 결과 경로와 궁극적인 로드 트립에서 어떻게 좁혀졌는지 보여 드리겠습니다.
검색 알고리즘을 처음 실행하기 전에 경로를 찾는 데 도움이 되도록 추가할 수 있는 추가 제약 사항이 있는지 확인하기 위해 네트워크를 간략하게 요약했습니다. 몇 가지가 있었습니다.
- Hwy 3은 Hwy 2와 Hwy 4라는 두 개의 다른 고속도로만 교차합니다. 이것은 시퀀스 2-3-4 또는 4-3-2가 경로의 고정된 부분임을 의미했습니다.
- Hwy 48은 Hwy 33과 Hwy 11과 같은 두 개의 다른 고속도로만 교차합니다. 이는 시퀀스 33-48-11 또는 11-48-33이 경로의 고정된 부분임을 의미했습니다.
- Hwy 57은 기술적으로 다른 하나의 고속도로(Hwy 83)와만 연결됩니다. 그 종점은 멕시코 국경에 있고 I-35는 샌안토니오로 향합니다. 그러나 그것은 Hwy 90과 꽤 가까웠기 때문에 그쪽으로 연결하게 놔두는 것이 매우 유혹적이었습니다. 하지만 규칙은 규칙이잖아요? … 말해봐, 그렇지 않아? 존 살 거기?! 그래, 저기!... 아닌데요?... 확실해?... 그 사람이라고 맹세할 수 있었어요. 어쨌든 내가 말했듯이 Hwy 57은 Hwys 83과 90에만 연결되므로 83-57-90 또는 90-57-83이 경로의 고정된 부분이 됩니다.
- 마지막으로 Hwy 46은 Hwy 1과 Hwy 9와 같은 두 개의 다른 고속도로에만 연결됩니다. 그러나 이 "두" 교차점은 실제로 하나의 교차점에 불과하기 때문에 흥미로운 경우입니다. 이 교차로가 발생하는 곳(뉴저지주 팰리세이즈 파크)에서 Hwy 1과 Hwy 9가 동시에 운행됩니다. 따라서 이것은 1-46, 9-46, 46-9 또는 46-1 중 하나가 경로의 고정점이 된다는 것을 의미했습니다. 또한 이것은 경로가 46번 고속도로에서 시작하거나 끝납니다.
라운드 1: 검색!
이러한 제약 조건을 알고리즘에 신중하게 넣은 후 Hwy 46으로 경로를 시작하고 알고리즘을 실행하기로 결정했습니다. 몇 개의 고속도로가 빠져 있었기 때문에 Filling Gap 방법의 방법 1을 사용하여 다시 끼워 넣었습니다("그래프트 및 재시도" 접근 방식). 3번의 재시도 끝에 ...성공!! 그림 1은 이 첫 번째 시도의 원시 출력을 보여줍니다.
Figure 1: Raw output of first attemptFigure 1: Raw output of first attemptFigure 1: Raw output of first attemptFigure 1: Raw output of first attempt그림 1: 첫 번째 시도의 원시 출력 이것은 내 취향에 너무 투박했기 때문에 Google Maps의 친절한 도움으로 약간 더 곡률을 추가하고 실제 경로를 더 가깝게 따르기 위해 추가 점으로 일부 선을 채웠습니다. 또한 내 데이터에 마커 유형 열을 추가하여 경로를 따라 주요 도시와 랜드마크를 식별하는 데 사용할 수 있습니다. 너무 많은 마커로 그래프가 복잡해지는 것을 방지하기 위해 위도 열을 복사하고 주요 도시 또는 랜드마크와 연결되지 않은 해당 열의 값을 삭제한 다음 포인트가 해당 열을 "Y축"으로 사용하도록 했습니다( 의 해당 그룹 아래에 있는 변수 화살표를 선택하여 이를 수행할 수 있습니다. JMP 그래프 빌더). 그건 그렇고, 여기에서 내가 사용하는 배경 지도는 미국 주가 부과된 스트리트 맵 보기입니다(경계선은 기본값보다 약간 더 어두운 회색으로 설정됨).
이 약간의 정리 후에 그림 2와 같은 경로를 얻습니다.
Figure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attempt그림 2: 첫 번째 시도의 정리된 버전
이 지도에 대한 귀하의 응답 중 일부는 다음과 같습니다.
- 꺄아아악!! 저게 뭐에요?! 끔찍해!! 누군가가 2살짜리 아이에게 그림을 그릴 수 있는 팁 마커와 미국 지도를 준 것 같습니다.
- 그래서 나는 당신이 어디에서 시작하고 어디에서 끝나는지 알 수 있지만 도대체 어떻게 거기에 도달합니까? 조지아주 애틀랜타에 있는 스파게티 교차로가 나쁘다고 생각했는데....
- 야, 내 상태를 완전히 놓쳤어!! (캘리포니아, 애리조나, 로드 아일랜드 및 메인 거주자로부터).
- 캐나다 여행은 어떤가요? (이건 쉽습니다. 재미있는 사실: Hwy 2는 설계에 따라 동부와 서부로 나뉩니다! 이 모든 것을 통과하려면 캐나다로 우회해야 합니다. 여기에 불만이 없습니다!).
알겠습니다. 첫 번째 시도에 꽤 많은 문제가 있음을 인정합니다. 나에게 가장 주목할만한 것은 그것이 여러 주를 완전히 놓쳤다는 사실이었습니다. 확실히 전국을 가로 질러 도로 여행을하지 않을 것입니다 (미안합니다, 알래스카와 하와이; 이해하기를 바랍니다). 그렇다면 왜 이러한 상태가 제외되었습니까? 글쎄, 그 질문에 대답하기 위해 나는 처음에 했어야 할 일을 했다: 네트워크를 플로팅!!
그림 3은 이전 게시물에서 설명한 대로 컴파일한 고속도로 네트워크를 보여줍니다.
Figure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualized그림 3: 시각화된 고속도로 교차로 네트워크
이 그림에서 우리는 왜 그 상태가 누락되었는지 명확하게 알 수 있습니다.
- 캘리포니아에는 교차로가 없고 끝 또는 시작만 있습니다(어딘가에 심오한 진술이 있습니다).
- Maine에는 Hwys 1과 Houlton의 2번 고속도로 사이에 단 하나의 교차로가 있습니다. 이 교차로는 경로 탐색에서 쉽게 지나갈 수 있었습니다.
- 애리조나에는 두 개의 교차로만 있습니다. Hwys 60 및 95(왼쪽) 및 Hwys 60 및 70(오른쪽). 앞의 논점과 같은 논리입니다.
- 로드 아일랜드에는 Hwys 6과 44의 교차로가 하나뿐입니다.
2라운드: 대망의 속편!
그림 3에서 수집한 정보를 사용하여 모든 상태를 충분히 방문할 수 있도록 몇 가지 제약 조건을 추가해야 합니다.
- 캘리포니아를 확실히 방문하기 위해 저는 로스앤젤레스에서 시작하여 주의 거의 전체 해안을 따라 확장되는 101번 고속도로에서 길을 시작하기로 결정했습니다. 경로는 여전히 Hwy 46으로 끝나야 합니다.
- Hwy 101 이후의 다음 고속도로에는 4가지 연결 옵션이 있습니다. 나는 처음에 Hwy 26에서 시작하기로 선택했는데, 이 옵션은 포틀랜드와 후드 산을 지나게 하기 때문입니다.
- 4-3-2 고정점을 확장하여 이제 Hwy 1을 포함합니다. 이로 인해 Maine이 경로의 일부가 되어야 하지만 더 이상 Hwy 2(캐나다 죄송합니다)에서 연장된 여행을 허용하지 않습니다.
- 60-70 및 93-95의 고정 소수점을 경로에 추가했는데, 결과적으로 알고리즘의 특성으로 인해 체인 93-95-60-70 또는 그 반대가 경로의 일부가 되었습니다. 이것은 애리조나가 경로의 일부가 되도록 하고 라스베가스를 일부로 만드는 추가 보너스를 가지고 있습니다. 천만에요.
- 나는 또한 52번 고속도로와 83번 고속도로가 미노트, ND에서 교차하기 때문에 83-57-90 체인에 52번 고속도로를 추가하기로 결정했습니다. 이것은 노스다코타의 더 넓은 범위를 허용했습니다. 모든 국가는 사랑을 공유해야 합니다.
이러한 새로운 제약 조건이 추가되면서 알고리즘을 다시 실행했고 고속도로는 하나만 남았습니다. 그래서 저는 채우기 방법의 방법 2를 사용하여 다시 추가했습니다("모든 옵션 시도" 방법). 약간의 청소 후 그림 4와 같은 지도가 생성되었습니다.
Figure 4: The second attempt at a road tripFigure 4: The second attempt at a road tripFigure 4: The second attempt at a road tripFigure 4: The second attempt at a road trip그림 4: 두 번째 도로 여행 시도 글쎄, 적어도 모든 주에는 현재 약간의 적용 범위가 있지만 여전히 약간 지저분합니다. 이 여행에 대해 내가 여전히 너무 열중하지 않은 한 가지는 와이오밍에 있는 루프입니다. 87번 고속도로와 85번 고속도로가 덴버에서 내려오는 I-25와 거의 동시에 운행되는 것으로 나타났습니다. 이것이 그들이 여기에서 하는 방식으로 나타나는 이유입니다. 또한 워싱턴 주는 버몬트처럼 거의 보장을 받지 못하는 것 같습니다. 그래서 몇 가지 제약 조건(101번 고속도로 – 12번 고속도로 시작으로 전환 포함)을 추가하고 그림 5와 같은 경로를 얻었습니다.
Figure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road trip그림 5: 로드 트립의 또 다른 시도 지금은 조금 나아진 모습입니다. 여전히 경로의 일부와 겹치는 부분이 많지만 제 생각에는 2라운드 버전만큼 나쁘지는 않습니다.
따라서 이 마지막 두 경로로 "누락 상태" 문제를 해결할 수 있었던 것 같습니다. 그러나 레이아웃에는 여전히 약간의 광기가 있습니다. 이 게시물은 코스를 실행한 것처럼 느껴지므로 다음 게시물에서 경로를 더 정리하고 최종 경로를 표시하기 위해 수행한 몇 가지 조정에 대해 논의하겠습니다.
나는 내가 한 방법을 가지고 있습니다 ... 비록 그것이 그리 쉽지는 않았다는 것을 보장 할 수 있습니다. 기본적으로 일부 경로를 작성하면서 Google 지도를 사용하여 운전 시간과 거리를 모두 계산했습니다. 누적 시간과 거리를 추적하는 다른 두 개의 열이 있었습니다. 경로가 고속도로를 따라가는지 확인해야 했기 때문에 다소 힘들었어요. Google이 계속해서 해당 주간 고속도로를 이용해야 한다고 주장하면서 주간 고속도로 옆을 따라갈 때 더 어려워졌습니다. 결국 2라운드 맵의 총 거리를 계산하고 3라운드 맵에 가까워졌고 둘 다 36,000마일(약 650시간의 운전 시간) 정도였습니다.
정류장 사이의 유클리드 거리(까마귀가 날아갈 때)를 취하여 총 거리를 근사할 수 있다고 생각합니다. 당신은 분명히 특정 도로의 세부 사항 중 일부를 놓칠 수 있지만 실제 사용에는 충분할 것이라고 확신합니다. SAS를 사용하여 이를 수행하는 방법이 있지만 JMP에서 수행하는 방법은 아직 잘 모르겠습니다.
좋은 작업! 다양한 노선의 총 마일리지가 궁금합니다. 쉽게 계산할 수 있는 방법이 있습니까?
