Traveling Salesman
모든 도시를 한 번씩 방문하는 최단 경로를 찾으세요 · 고전적인 외판원 문제
외판원 문제 소개
외판원 문제는 컴퓨터 과학에서 가장 유명한 문제 중 하나인 외판원 문제(Traveling Salesman Problem, TSP)를 기반으로 한 간결한 경로 최적화 퍼즐입니다. 지도에 몇 개의 도시가 흩어져 있고, 당신은 집에서 출발합니다. 당신의 임무는 모든 도시를 정확히 한 번씩 방문하고 집으로 돌아오는 가장 짧은 총 거리의 경로를 계획하는 것입니다. 운전할 순서대로 도시를 탭하면 경로가 그려지고, 실시간 거리 카운터가 루프의 길이를 알려줍니다.
뇌 훈련에 좋은 이유. 최단 경로를 찾는 것은 순수한 공간 추론 및 계획 능력입니다. 전체 순서를 서로 비교하고, 경로가 교차하여 거리를 낭비하는 경우를 파악하며, 이길 수 없는 배열을 찾아야 합니다. 적용할 공식은 없습니다. 기하학에 대해 직접 추론해야 하며, 이것이 바로 TSP를 유명하게 만든 최적화 사고 방식입니다.
최적 경로와 일치시켜 승리하세요. 모든 지도는 내부적으로 정확하게 해결되므로, 당신의 루프가 진정한 최단 경로와 일치할 때만 라운드가 승리로 간주됩니다. 길이가 같은 다른 최단 경로도 모두 승리로 인정됩니다. 더 길게 만들면 게임이 당신의 경로 위에 최적 경로를 보여주어 풀었어야 할 교차점을 확인할 수 있습니다.
레벨이 올라갈수록 지도가 커집니다. 초기 라운드는 도시가 4개 또는 5개로, 눈으로 쉽게 파악할 수 있습니다. 몇 레벨마다 지도는 도시를 하나 더 얻게 되며, 각 추가 정류장은 가능한 경로의 수를 증가시키므로, 연승이 길어질수록 최단 루프를 찾는 것이 더 어려워집니다.
PlayMemorize 두뇌 훈련 게임 제품군의 일부입니다. 전적으로 브라우저에서 실행되며, 프로그레시브 웹 앱으로 오프라인에서도 작동합니다.
FAQ
-
외판원 문제는 어떻게 플레이하나요?
집 마커에서 시작합니다. 방문할 순서대로 다른 도시들을 하나씩 탭하세요. 경로가 그려지고 거리 카운터가 업데이트됩니다. 모든 도시가 경로에 포함되면 확인을 누르세요. 당신의 루프가 가능한 최단 경로와 일치하면 라운드에서 승리합니다. -
외판원 문제(Traveling Salesman Problem)란 무엇인가요?
이것은 고전적인 최적화 문제입니다. 주어진 도시 집합에서 각 도시를 정확히 한 번 방문하고 시작점으로 돌아오는 가장 짧은 경로를 찾는 것입니다. 도시를 추가할수록 가능한 경로의 수가 폭발적으로 증가하기 때문에 해결하기 어렵기로 유명합니다. 이 게임은 작고 해결 가능한 인스턴스를 직접 다룰 수 있게 해줍니다. -
게임은 경로가 최적인지 어떻게 아나요?
각 지도는 게임이 모든 가능한 순서를 확인하여 정확한 최단 경로를 계산할 수 있을 만큼 충분히 작습니다. 당신의 루프 길이가 그 최적값과 일치하면 승리합니다. 두 개의 다른 경로가 최단 경로로 동점인 경우, 어느 쪽이든 승리로 간주됩니다. -
내 경로가 최단 경로가 아니면 어떻게 되나요?
해당 라운드는 패배로 간주되며, 게임은 당신의 경로 위에 진정한 최적 경로를 그려 비교할 수 있도록 합니다. 당신의 루프가 교차하는 지점을 찾아보세요. 교차점을 풀면 거의 항상 경로가 짧아집니다. 실행 취소를 사용하여 마지막 도시를 제거하거나 지우기를 사용하여 경로를 다시 시작하세요. -
진행할수록 더 어려워지나요?
네. 각 성공적인 라운드는 레벨을 올리고, 몇 레벨마다 지도는 도시를 하나 더 얻게 됩니다. 각 추가 정류장이 가능한 경로의 수를 급격히 증가시키기 때문에, 연승이 길어질수록 최단 루프를 찾는 것이 점점 더 어려워집니다. -
오프라인에서도 작동하나요?
네. PlayMemorize는 프로그레시브 웹 앱입니다. 한 번 설치하면 외판원 문제를 인터넷 연결 없이 어디서든 플레이할 수 있습니다.