자동차 여행에 대한 나의 집착이 어디에서 시작되었는지 묻는다면, 그것은 아마도 아내와 내가 졸업 후 첫 직장을 시작하기 위해 버지니아주 블랙스버그에서 뉴멕시코주 앨버커키까지 I-40을 몰고 간 직후에 시작되었다고 말해야 할 것입니다. 학교. 아마도 변화하는 풍경을 보고 새로운 장소를 방문하는 것이 흥미로웠을 것입니다. 하지만 솔직히 말해서 "경로를 끝내고" 양쪽 끝에서 나머지 I-40을 운전해야 한다는 강박 때문일 가능성이 더 큽니다. 나는 타협하고 그것이 둘 다라고 말할 것입니다.
처음에 나의 로드 트립 페티쉬는 주로 미국의 모든 주요 고속도로(0 또는 5로 끝나는 고속도로)를 여행하는 데 중점을 두었습니다. 그러나 다양한 여행 서적을 읽어보니 도로 여행 커뮤니티는 주간 고속도로를 상업과 만능 "분주함"의 길로 치부하고 대신 미국의 다른 주요 도로인 미국 고속도로의 조용하고 약간 느린 속도를 선호하는 경향이 있음을 발견했습니다. 체계. 이러한 고속도로 중 몇 개를 지도로 그리면 새로운 장소와 풍경에 대한 흥분이 촉발되었습니다. 나의 새로운 꿈은 미국의 모든 주요 고속도로, 즉 캘리포니아의 101번 고속도로를 제외하고는 여전히 활성화되어 있는 두 자리 표시가 있는 모든 고속도로를 여행하는 것이었습니다.
The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)꿈이 만들어지는 것들... (Wikipedia의 이미지: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)
최근에 Research Statistician Tester로 제 직책을 시작한 이후 JMP , 가능하다고 생각했던 것보다 소프트웨어에 대해 더 많이 배웠습니다. JMP 스크립팅 언어를 얼마나 빨리 배웠는지(확실히 아직 JSL을 배우는 중이긴 하지만) 훨씬 더 많은 가능성을 열어준 것에 놀랐습니다. 하지만 일단 내가 끌어서 놓기 그래프 빌더 지도를 그리는 능력이 있었다?! 글쎄, 당신은 아마도 이것이 어디로 가는지 짐작할 수 있을 것입니다(제목이 죽은 공짜가 아니었다면).
처음의 설렘을 극복한 후 회의적인 순간이 있었습니다. Graph Builder를 사용하여 실제로 여행 계획을 세울 수 있습니까? 지역을 그릴 수 있다는 것은 알고 있었지만 선과 도로는 어떻습니까? 글쎄, 내가 인정하는 것보다 더 많은 시간을 보낸 후에 대답은 '예'라고 말할 수 있어서 기쁩니다! Google 지도나 AAA Trip Tik은 아니지만 확실히 볼 가치가 있다고 생각합니다.
경로 설정
그래서 대답해야 할 첫 번째 질문은 이것이 어떤 종류의 여행이 될 것인가였습니다. 음, 내 꿈은 미국의 모든 고속도로를 여행하는 것이었습니다. 구체적으로 목표는 다음과 같습니다.
모든 활성 기본 미국 고속도로를 연결하는 미국 고속도로 시스템을 통해 경로를 찾으십시오.
내 내면의 완성주의자는 특정 고속도로를 구성하는 포장 도로를 1마일도 주행하지 않을 가능성에 대해 머뭇거릴 것이지만, 어느 정도 타협해야 했고, 이것은 여전히 어쨌든 큰 도전이 될 것입니다. 그러나 먼저 다음과 같은 몇 가지 기본 규칙이 있습니다.
- 목표는 가능한 한 미국 고속도로로만 여행하는 것입니다. 즉, 가능한 한 중간에 고속도로가 아닌 도로를 이용하지 않고 한 고속도로에서 다른 고속도로로 직접 가고 싶습니다.
- 고속도로는 현재 활성 상태여야 하며(죄송합니다. Route 66ers) 고속도로 시스템의 기본 구성원 역할을 해야 합니다(101을 제외한 두 자리 지정).
- 각 고속도로는 한 번만 운행됩니다.
충분히 간단해 보이죠? 첫 번째 단계는 어떤 고속도로가 어떤 다른 고속도로와 연결되어 있고 이러한 교차로의 위치를 보여주는 고속도로 교차로 데이터베이스를 컴파일하는 것이었습니다. 나는 그러한 데이터베이스를 기성품으로 찾기 위해 많은 시간을 보냈지만 그런 행운은 없었습니다. 그래서 나는 데이터 테이블에서 내 자신을 만들기로 결정했습니다.
Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.각 교차로의 좌표를 얻기 위해 사용한 프로세스의 예. 진정한 사랑의 노동.
종종 고속도로가 서로 여러 번 교차하거나 서로 동시에 실행된다는 점을 언급할 가치가 있습니다. 나는 북쪽이나 동쪽에서 남쪽이나 서쪽으로 고속도로를 따라갈 때 발생하는 첫 번째 교차로만 기록하여 내 네트워크에 내재된 방향 편향을 주입했습니다. 사실, 그것이 바로 제가 구축하고 있던 것입니다. 교차로 "가장자리"를 기반으로 하는 미국 고속도로 "노드" 네트워크입니다. 이 네트워크가 완성되면 목표는 경로에서 노드가 반복되지 않고(가능한 경우) 각 노드를 연결하는 네트워크를 통해 경로를 찾는 것입니다.
그래프 이론에 익숙한 사람들에게는 이것이 유명한 "외판원 문제"를 다루는 것처럼 들릴 수 있습니다. 그리고 당신은 거의 맞을 것입니다. 여행하는 세일즈맨은 실제로 해밀턴 경로 , 이는 반복 없이 모든 단일 노드를 연결하는 경로입니다( 오일러 경로 , 반복 없이 네트워크의 모든 단일 에지를 사용하는 경로이며 유명한 Koenigsburg 다리 문제 ). 순회 외판원을 특별한 경우로 만드는 것은 가장자리에 가중치(예: 시간 또는 거리)가 있다는 사실이며, 따라서 경로가 총 가중치를 최소화해야 한다는 추가 조건이 있습니다. 재미있는 사실: 해밀턴 경로는 12면체의 모든 정점을 연결하는 경로를 찾는 작업을 했던 William Rowan Hamilton에서 그 이름을 얻었습니다. 어느 시점에서 그는 정점이 유명한 도시인 것처럼 가장하고 "월드 투어"를 찾고 있었습니다. 나는 우리가 꽤 잘 지냈을 것 같은 느낌이 든다.
Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)12면체 위의 해밀턴 경로의 전통적인 예(Wikipedia에 게시된 Christoph Sommer의 이미지: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
이 해밀턴 경로는 내가 찾던 바로 그 것입니다! 잘 알려진 객체였으니 이를 찾는 효율적인 알고리즘이 있어야겠죠? 글쎄, 그렇게 빠르지는 않아. 알다시피, 임의의 그래프를 통해 해밀턴 경로를 찾는 문제는 NP-hard 문제라고 합니다. 이것은 경로가 Hamiltonian인지 확인하는 것은 매우 쉽지만 몇 가지 예외를 제외하고는 그러한 경로를 찾기가 매우 어렵다는 멋진 용어입니다. 즉, 모든 상황에 대해 해밀턴 경로를 찾는 일반적인 빠른 알고리즘이 없습니다. 그래서 다시 한 번 제 사례에 맞는 알고리즘을 개발할 수 있는지 알아보기 위해 스스로 출발했습니다.
로 처음 시작했습니다 내 네트워크를 JSL의 연관 배열로 변환 그리고 들여다 보았다 동료가 작성한 소규모 네트워크에서 경로를 찾기 위한 간단한 알고리즘 . 이 알고리즘은 깊이 우선 검색을 사용합니다. 이 검색에는 네트워크의 노드에서 시작하여 연결이 모두 소진될 때까지 모든 노드에 대해 처음으로 만나는 연결을 따라가며 연결되지 않은 다른 노드로 돌아가서 계속하세요. 이 알고리즘이 해밀턴 경로를 보장하지는 않지만 여전히 이를 사용하여 가까이 접근할 수 있음을 발견했습니다. 이 접근 방식을 채택하여 도출한 알고리즘은 다음과 같습니다.
Near-Hamiltonian 경로 찾기
- 시작 노드를 제공하십시오.
- 각 연결 노드에 대해 단일 패스 깊이 우선 검색을 실행하고(즉, 일부 연결을 놓친 경우에도 연결이 끊어지면 다시 돌아가지 않음) 가장 긴 경로가 있는 노드를 확인합니다.
- 해당 연결 노드를 경로에 추가하십시오.
- 경로에 추가할 수 있는 노드가 더 이상 없을 때까지 2-3단계를 반복합니다.
이 알고리즘의 기본 아이디어는 이론상 가장 긴 잠재적 경로를 가진 노드를 추가하면 경로가 일찍 종료되는 위험을 줄여 네트워크 전체의 전체 경로에 훨씬 더 가까워져야 한다는 것입니다.
격차 채우기
이제 초기 경로를 얻을 수 있으므로 다음 단계는 초기 실행에서 제외된 누락된 노드를 "접목"하는 방법을 결정하는 것이었습니다. 가능한 세 가지 방법을 생각해 냈습니다.
- 첫 번째 누락된 노드를 선택하고 현재 경로에서 가능한 가장 빠른 연결에 강제로 연결한 다음 거기에서 검색을 다시 시작합니다. 물론 첫 번째 누락된 노드를 선택할 필요는 없지만(사실 "첫 번째" 누락된 노드가 반드시 있는 것은 아닙니다) 아이디어는 동일합니다. 기본적으로 이 접근 방식은 누락된 노드를 경로에 "접목"한 다음 알고리즘 실행(재시작 부분) 중에 이 지점에 도달한 것처럼 가장합니다. 이 접근 방식의 한 가지 위험은 끝없는 루프에 갇힐 수 있다는 것입니다. 기본 검색 알고리즘의 한계로 인해 모든 단일 노드를 통합하는 경로에 도달하지 못할 수 있습니다. 경로 검색에 더 많은 무작위 선택을 포함하여 이 접근 방식을 조정할 수 있지만 경로를 더 빨리 찾을 수 있다는 보장은 없습니다.
- 누락된 노드가 하나만 있는 경우 현재 경로에 맞추는 가능한 모든 조합을 탐색하고 성공적으로 수행하는 노드를 반환합니다. 본질적으로 이 접근 방식은 주어진 현재 경로 레이아웃에서 누락된 노드를 포함하는 모든 가능한 경로에서 철저한 검색에 해당합니다. 이 접근 방식의 한 가지 위험은 누락된 노드에 많은 연결이 있는 경우입니다. 가능성의 수는 컴퓨터의 계산 한계를 빠르게 초과할 수 있습니다. 그렇기 때문에 누락된 노드의 연결이 10개 미만인 경우에만 사용했습니다. 물론 둘 이상의 노드가 있지만 각각 연결이 거의 없는 경우에도 이 방법을 사용할 수 있습니다.
- 약간의 엘보우 그리스를 사용하고 누락된 노드를 경로에 수동으로 입력합니다. 이것은 회피처럼 보일 수 있지만 알고리즘이 경로를 찾는 데 어려움을 겪고 있는 경우 필요할 수 있으며 반드시 그렇게 어려운 것은 아닙니다. 또한 전문가의 판단을 경로에 통합하는 좋은 방법입니다. 아마도 순수한 컴퓨터 기반 솔루션보다 인간의 약간의 입력으로 더 아름다운 경로를 찾을 수 있습니다. 공동의 목표를 향해 조화롭게 일하는 인간과 기계의 완벽한 예입니다.
내 Hamiltonian 경로를 검색하면서 실제로 이러한 각 접근 방식을 적어도 한 번은 사용하게 되었습니다. ~ 안에 다음 포스트 , 내 노동의 결실을 볼 수 있습니다.
