판매원 문제 해결법
TLDR: 판매원 문제는 각 도시를 정확히 한 번 방문하고 최단 가능한 루프로 집으로 돌아오는 것을 요구합니다. 도시를 순서대로 탭하고 모든 도시가 경로에 있을 때 확인을 누릅니다. 거리가 최적과 일치할 때만 승리합니다. 게임은 최적 경로를 패배 시 보여주므로, 이를 연구하세요 - 자체 교차 경로는 거의 항상 원인입니다. 교차 경로를 제거하면 투어가 짧아집니다.
해결해야 할 문제
판매원 문제는 컴퓨터 과학에서 가장 유명한 문제 중 하나의 축소된 버전입니다. 시작 지점인 집 마커와 흩어져 있는 도시가 있는 지도를 보게 됩니다. 방문해야 할 도시는 하나도 빠짐없이 방문하고, 최단 가능한 총 거리를 사용하여 집으로 돌아오는 것이 목표입니다. 공식이나 단축 방법은 없습니다 - 기하학을 직접 생각하고, 전체 경로를 서로 비교해야 합니다.
게임은 실시간으로 현재 투어의 거리를 알려줍니다. 모든 도시를 방문한 후 확인을 누릅니다. 루프가 최적 해와 일치하면 승리하고 다음 단계로 진행합니다. 더 길면 최단 경로가 자신의 경로와 겹쳐서 표시됩니다 - 게임에서 가장 가치 있는 순간입니다. 그 즉시 시각적 비교는 정확히 어디에서 잘못되었는지 보여줍니다.
게임을 신선하게 유지하는 트릭은 성장입니다. 몇 레벨마다 지도가 새로운 도시를 얻습니다. 다섯 도시가 여섯 도시가 되고, 일곱 도시가 됩니다. 각 추가는 작아 보이나, 가능한 순서의 수가 극적으로 증가합니다. 레벨 1에서는 눈대중으로 할 수 있는 것이 레벨 10에서는 진정한 최적화 문제로 변합니다.
규칙 전체
먼저 지도를 공부하세요. 집 마커(시작점과 끝점)와 그 주위에 흩어져 있는 다른 도시들을 보게 됩니다. 경로는 항상 집에서 시작하고 끝납니다 - 집이 아닌 도시만 탭하여 루프를 만듭니다.
방문할 순서대로 도시를 탭합니다. 경로는 각 탭을 연결하는 선으로 그립니다. 거리 카운터는 실시간으로 업데이트됩니다. 잘못된 경우, 마지막 도시를 경로에서 제거하거나 전체 경로를 지우고 다시 시작하려면 취소를 사용하세요.
모든 도시를 탭한 후 확인을 누릅니다. 게임은 모든 가능한 순서를 확인하여 최적 해를 계산하고, 자신의 루프와 비교합니다. 일치하면 승리합니다. 더 길면 두 경로가 나란히 표시되어 잘못된 부분을 진단할 수 있습니다.
규칙은 엄격합니다: 각 도시를 정확히 한 번, 루프는 집으로 돌아야 하며, 최적과 일치해야 승리합니다. 부분 점수나 “거의 맞음”은 없습니다.
가장 중요한 패턴: 자체 교차 경로
가장 중요한 것은 자체 교차 경로를 찾는 것입니다. 대부분의 비최적 투어는 경로가 자신을 교차하기 때문입니다. 경로의 두 세그먼트가 교차하면 거리를 낭비하고 있습니다 - 교차 경로를 제거하면 거의 항상 투어가 짧아집니다.
이유는 다음과 같습니다: 네 도시가 대략 사각형을 이루고 있다고 상상해 보세요. X 모양을 만드는 순서로 방문하면 경로가 상단 왼쪽에서 하단 오른쪽, 상단 오른쪽에서 하단 왼쪽으로 이동합니다. 최적 경로는 대신 외곽을 따릅니다: 상단 왼쪽, 상단 오른쪽, 하단 오른쪽, 하단 왼쪽. 같은 도시, 교차 없음, 더 짧은 총 거리.
게임이 패배 후 최적 경로를 보여줄 때, 먼저 자신의 경로가 어디에서 자신을 교차했는지 확인하세요. 최적 해는 교차 경로를 풀어냅니다. 두 도시의 순서를 바꾸면 교차 경로를 제거하고 최적 거리를 얻을 수 있습니다.
매번 패배 후, 최적 경로를 보기 전에 자신의 경로에서 교차 경로를 세어 보세요. 몇 개의 교차점을 볼 수 있나요? 최적 경로는 모두 제거했습니다. 그런 다음 최적 경로를 제거하는 가장 나쁜 교차 경로를 제거하는 도시 교환을 식별하세요. 이 비교에서 가장 많은 학습이 이루어집니다 - 승리에서가 아니라 진단된 패배에서.
외곽 순회. 새로운 지도에서 먼저 외곽 경계를 상상해 보세요 - 외곽 모양을 형성하는 도시(가장 바깥쪽 모양). 최적 경로는 종종 이 외곽을 따라가며, 시계 방향 또는 반시계 방향으로 외곽 도시를 방문한 후 내부 도시를 삽입합니다. 경로를 가장자리로부터 시작하고, 간극에서 추가 거리를 최소화하는 내부 도시를 삽입합니다.
체계적인 경로 구축
도시를 무작위로 탭하고 희망하지 마세요. 경로를 단계별로 구축하여 백트래킹을 최소화하는 지역 결정을 내립니다.
집에서 시작하여 다음 질문을 합니다: 어떤 도시를 먼저 방문해야 할까요? 일반적으로 가장 가까운 도시이거나, 지도를 가로지르며 백트래킹 없이 이동할 수 있는 방향에 있는 도시입니다. 탭합니다.
각 도시에서 동일한 질문을 합니다 - 현재 위치에서 추가 거리를 최소화하는 방문하지 않은 도시는 무엇입니까? 이 탐욕적인 접근(항상 가장 가까운 또는 가장 합리적인 다음 정류장으로 이동)은 항상 최적 해를 제공하지 않지만, 개선할 수 있는 합리적인 시작 경로를 구축합니다.
첫 번째 시도 경로를 얻으면, 경로를 정신적으로 따라가세요. 거리가 낭비되는 느낌이 드는 곳은 어디인가요? 지도를 가로지르는 긴 세그먼트가 있는지 확인하세요. 두 도시가 멀리 떨어져 있지만 경로에서 인접해 있는 경우, 두 도시의 순서를 바꾸면 교차 경로를 제거하거나 긴 점프를 제거할 수 있습니까? 이러한 작은 지역 개선은 좋은 경로를 최적 경로로 전환하는 데 도움이 됩니다.
가장 가까운 이웃, 그런 다음 개선. 탐욕스럽게 도시를 탭하여 항상 가장 가까운 방문하지 않은 정류장으로 이동합니다. 거리를 기록합니다. 그런 다음 경로를 정신적으로 따라가서 교차 경로, 백트래킹 또는 비효율성을 찾습니다. 그 비효율성을 일으키는 두 도시의 순서를 바꾸고, 교환을 다시 탭하여 개선되었는지 확인합니다. 최적과 일치하거나 명확한 수정이 소진될 때까지 반복합니다.
탐욕적은 최적이 아닙니다. 가장 가까운 이웃 접근법은 자연스럽게 느껴지지만, 종종 거리를 남깁니다. 초기 레벨에서는 용서할 수 있지만, 도시 수가 증가함에 따라 탐욕적인 경로는 일관되게 부족합니다. 가장 가까운 이웃을 빠른 시작점으로 사용하고, 개선하세요 - 최종 답변으로 의존하지 마세요.
일반적인 실수와 피하는 방법
무작위 순서로 탭하고 희망. 지도의 기하학이 중요합니다. 가까운 도시는 경로에서 연속적으로 나타나야 합니다. 클러스터는 그룹으로 투어하고 다음 클러스터로 이동하기 전에 방문해야 합니다. 무작위 순서는 거의 항상 비용이 높은 긴 점프를 포함합니다.
패배 후 첫 번째 경로에 집착. 패배하면 한 도시를 취소하고 다시 탭하지 마세요. 게임이 보여주는 최적 경로를 연구하세요. 자신의 경로와 어떻게 근본적으로 다른지 확인하세요? 어떤 순서 원칙을 따르는지 확인하세요. 이 메타 뷰 - 전체 전략을 비교하는 것이 아니라 개별 도시를 비교하는 것이 실질적인 개선이 이루어지는 곳입니다.
매우 긴 세그먼트는 단서입니다. 경로가 지도를 가로지르는 긴 다리를 가지고 있다면, 이는 거의 항상 나쁜 순서를 나타냅니다. 최적 경로에는 단일 다리가 다른 다리보다 훨씬 길지 않습니다 - 거리는 균형 잡혀야 합니다. 긴 점프는 두 도시가 멀리 떨어져 있지만 경로에서 인접해 있는 경우를 나타냅니다.
몇 가지 탭 후 고립. 취소와 지우기를 자유롭게 사용하세요. 경로가 다섯 도시 후 잘못된 느낌이 든다면, 지우고 다른 시작 방향을 시도하세요. 반복은 고치기보다 빠릅니다.
기억할 수 있는 공식 찾기. 각 지도는 고유합니다. “항상 시계 방향으로 이동” 또는 “항상 위쪽부터 방문”은 다른 지도에서 작동하지 않습니다. 최적 전략은 이 특정 기하학에 따라 달라집니다. 새로운 지도를 항상 신선하게 읽을 수 있도록 훈련하세요.
탭하기 전에 10초 동안 지도를 공부하세요. 클러스터는 어디인가요? 어떤 도시가 가장 고립되어 있나요? 지도의 대략적인 모양은 무엇인가요 - 퍼져 있나요, 아니면 밀집되어 있나요? 모든 다른 도시에서 멀리 떨어진 한 도시가 비용이 높은 우회를 필요로 하는가요? 이러한 관찰은 첫 몇 가지 탭을 안내하고, 최적 경로로 이끌기 전에 거리에 대한 어떤 것도 약속하지 않습니다.
난이도가 증가함에 따라
초기 레벨에는 네 또는 다섯 개의 도시가 있습니다. 가능한 순서의 수는 눈대중으로 할 수 있을 만큼 작습니다. 이 단계에서는 탭하기 전에 답을 볼 수 있습니다 - 지도를 스캔하고, 가장 자연스러운 루프를 식별하고, 이를 실행합니다.
레벨 6 또는 7에서는 여섯 번째 도시가 나타납니다. 가능한 경로의 수가 극적으로 증가합니다. 눈대중은 더 이상 신뢰할 수 없습니다. 이 단계에서 전략적 기술이 필요합니다. 기하학을 생각하고, 교차 경로를 찾고, 전략을 비교해야 합니다.
몇 레벨마다 새로운 도시가 추가됩니다. 레벨 12에서 15에서는 일곱 또는 여덟 개의 도시를 관리합니다. 가능한 경로의 수는 수백만 개입니다. 모든 것을 정신적으로 확인할 수 없습니다. 구조적으로 생각하세요 - 패턴을 사용하고, 공간적 직관을 신뢰하며, 각 지도를 해결해야 할 기하학 문제로 접근하세요.
큰 지도에서 분할 정복. 도시를 클러스터 또는 지역으로 정신적으로 나누세요. 각 지역 내에서 효율적인 하위 투어를 구축하고, 지역 간의 거리를 최소화하는 순서로 지역을 연결합니다. 도시 수가 여섯 또는 일곱을 초과하면 작은 하위 문제를 해결하고, 그런 다음 결합하는 접근 방식은 신뢰할 수 있습니다.
연습 루틴
주당 세 번의 집중된 세션(약 10분씩)은 빠른 개선을 구축하는 데 충분합니다.
세션 1 - 기하학 관찰. 세 라운드를 레이싱하지 않고 플레이합니다. 도시를 탭하기 전에 15초 동안 지도의 모양을 설명합니다: “도시가 대략 타원 모양을 이루고 왼쪽에 외딴 곳이 있습니다.” 그 모양이 경로를 안내합니다. 거리에 대한 약속 없이 지도의 구조를 읽는 연습을 합니다.
세션 2 - 교차 제거. 세 라운드를 플레이합니다. 각 패배 후 1분 동안 자신의 경로를 최적 경로와 비교합니다. 경로에서 모든 교차 경로를 세어 보세요. 어떤 한 교환이 가장 나쁜 교차 경로를 제거할 수 있나요? 이 의도적인 분석은 장기적인 직관을 구축하는 곳입니다.
세션 3 - 속도와 일관성. 다섯 라운드를 플레이하고 세 라운드를 연속으로 승리하세요. 세 번째 라운드에는 개선이 느껴질 것입니다 - 경로 구축이 더 빠르고, 교차 경로 탐지가 더 직관적이고, 거리가 최적과 더 자주 일치합니다.
진행 표시기. 첫 번째 시도에서 라운드를 승리할 때 진보하고 있습니다 - 지도의 기하학에서 최적 경로를 예측하고, 피드백을 보여주지 않고 실행할 수 있습니다. 초급 플레이어는 자주 패배합니다. 중급 플레이어는 대부분의 라운드를 승리하지만, 높은 도시 수에서는 여전히 부족합니다. 고급 플레이어는 레벨 10 이상에서 일관되게 승리합니다.
정신적 패턴 로그를 구축하세요. 각 라운드 후, 무엇이 효과가 있었는지 기록하세요: “외곽 우선이 여기 성공했습니다” 또는 “상단 왼쪽의 고립된 도시는 마지막에 방문해야 합니다.” 시간이 지나면서 이러한 관찰은 모든 미래 지도에서 적용되는 공간적 직관으로 쌓입니다.
최종 생각
판매원 문제는 게임을 넘어서는 기술을 훈련합니다: 공식 없이 공간 배열과 최적화를 생각하는 능력입니다. 엔지니어가 배송 경로를 설계하고, 외과의사가 수술 단계를 순서대로 배치하고, 건축가가 공간을 효율적으로 배치하는 데 사용하는 동일한 사고를 사용합니다.
게임은 함께 성장합니다. 초기 라운드는 기본 사항을 가르칩니다 - 도시 탭, 교차 경로 탐지, 거리 확인. 후기 라운드는 더 깊은 사고를 요구합니다 - 여러 제약 조건을 균형 맞추기, 전체 그림 보기, 가능성 수가 폭발할 때 공간적 직관을 신뢰하기.
현재 위치에서 시작하세요. 자신의 능력의 가장자리에 있는 라운드를 플레이하세요. 각 패배에서 배우세요. 최적 경로는 항상 기다리고 있습니다. 당신의 일은 더 빨리 그것을 보게 되는 것입니다.
