연구해 왔기 때문에 최적의 해법을 구하는 다양한 방법이 알려져 있습니다. 연구진은 외판원문제의 해법을 활용해서 가장 효과적인 방법을 제시할 수 있었죠. 수학재밋네? #12. 중학교 수학만 알아도 예측 문제 풀 수 있다? 이석훈 산업수학전문위원은 이날 모인 학생들에게 중학교 수학이 산업 ...
경로’와 비슷한 개념이에요. 저희가 경로를 짜는 것 역시 외판원 문제에 해당합니다. 외판원 문제는 캐나다 워털루대학교 연구팀이 만든 ‘Concorde(콩코드)’라는 프로그램으로 풀 수 있는데요, 이 프로그램에서는 지점 간의 거리를 기준으로 최단 경로만 계산할 수 있어, 저희가 필요한 최소 시간이 ...
찾는 알고리듬이에요. 실제 답에 가까울수록 좋은 근사 알고리듬이라고 할 수 있죠. 외판원 문제, 정점 커버 문제, 작업 스케줄링 문제, 클러스터링 문제 등 아직 해결되지 않은 문제로부터 우리 삶을 편리하게 해주는 몇 가지 근사 알고리듬을 배워볼게요. 그림으로 보는 알고리듬 ⑥ - ...
연방공과대학교 교수팀은 근사 알고리듬 분야에서 획기적인 발견을 했습니다. 여행하는 외판원 문제의 비대칭 상황에서 근사 알고리듬을 만든 것이지요. 스벤손 교수팀은 최적 해의 5500배 비용이 드는 알고리듬을 만들었습니다. 즉 어떤 도시들을 도는 데 최저 비용의 5500배 이내로 도는 방법을 ...
산타학교 졸업을 앞둔 학생들에게 알립니다. 올해 졸업 여행의 주제는 ‘수학’입니다. 먼저 예비 산타들은 4명씩 조를 지어한 배를 탄 ‘크루’를 만들어 주 ... 1. 매스시티 맵 만들기part 2. 최저가 여행, 외판원 문제로 해결part 3. 야구 보며 여행하는 외판원 문제part 4. 무한히 많은 도시 ...
수 있는 범위를 정해두고, 범위를 벗어나는 값들을 지워 계산의 양을 줄이는 거죠. 외판원 문제는 모든 도시를 한 번씩은 반드시 다 들러야 하니, 모든 도시에서 딱 한 번씩 출발하고 한 번씩만 도착해야 합니다. 그래서 각 도시에서 다른 모든 도시로 이동할 때 나올 수 있는 비용 중, 최솟값들을 ...
SAS(미국 소프트웨어 회사) 연구원은 여행하는 야구팬 문제를 해결하기 위해 전통적인 외판원 문제에 ‘사건이 일어나는 시간’이 포함된 알고리듬을 이용했습니다. 각 경기장에서 경기가 있는 날과 경기 시간을 데이터로 이용했죠. 그 결과 24.8일 동안 약 4989km를 이동하는 경로가 최적의 답으로 ...
문제를 만들고, 컴퓨터에서 직접 답을 찾아볼 수도 있답니다. 활동 2 TSP 아트! 외판원 문제 알고리듬을 이용해 예술 작품을 그리기도 합니다. 프로그램을 이용해 사진을 최적 경로처럼 바꾸는 것이지요. 우리는 로마에 위치한 콜로세움으로 만들어 봤어요. 여러분도 좋아하는 그림이나 ...
컴퓨터 과학 두 분야에서 모두 중요하게 연구하기 때문입니다. 대표적으로 ‘여행하는 외판원 문제’가 있지요.외판원 문제는 여러 마을이 있고 한 마을에서 다른 마을로 이동하는 비용이 모두 정해져 있을 때, 모든 마을을 한 번씩만 방문하고 처음으로 돌아오는 최소 비용의 이동 방법을 구하는 ...
폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.
☎문의 02-6749-3911
정기구독 인증방법 안내
