D라이브러리

개미가 현재 도시에서 다음 도시를 선택할 확률은 에 비례한다고 쓸 수 있습니다. 즉, 외판원 문제에서 다음 목적지를 정할 때 이 값이 큰 도시를 선택하는 방식으로 최적의 경로를 찾을 수 있습니다 ...

연구해 왔기 때문에 최적의 해법을 구하는 다양한 방법이 알려져 있습니다. 연구진은 외판원문제의 해법을 활용해서 가장 효과적인 방법을 제시할 수 있었죠.  수학재밋네? #12. 중학교 수학만 알아도 예측 문제 풀 수 있다? 이석훈 산업수학전문위원은 이날 모인 학생들에게 중학교 수학이 산업 ...

경로’와 비슷한 개념이에요. 저희가 경로를 짜는 것 역시 외판원 문제에 해당합니다. 외판원 문제는 캐나다 워털루대학교 연구팀이 만든 ‘Concorde(콩코드)’라는 프로그램으로 풀 수 있는데요, 이 프로그램에서는 지점 간의 거리를 기준으로 최단 경로만 계산할 수 있어, 저희가 필요한 최소 시간이 ...

찾는 알고리듬이에요. 실제 답에 가까울수록 좋은 근사 알고리듬이라고 할 수 있죠. 외판원 문제, 정점 커버 문제, 작업 스케줄링 문제, 클러스터링 문제 등 아직 해결되지 않은 문제로부터 우리 삶을 편리하게 해주는 몇 가지 근사 알고리듬을 배워볼게요.   그림으로 보는 알고리듬 ⑥ - ...

연방공과대학교 교수팀은 근사 알고리듬 분야에서 획기적인 발견을 했습니다. 여행하는 외판원 문제의 비대칭 상황에서 근사 알고리듬을 만든 것이지요. 스벤손 교수팀은 최적 해의 5500배 비용이 드는 알고리듬을 만들었습니다. 즉 어떤 도시들을 도는 데 최저 비용의 5500배 이내로 도는 방법을 ...

문제를 만들고, 컴퓨터에서 직접 답을 찾아볼 수도 있답니다.  활동 2  TSP 아트! 외판원 문제 알고리듬을 이용해 예술 작품을 그리기도 합니다. 프로그램을 이용해 사진을 최적 경로처럼 바꾸는 것이지요. 우리는 로마에 위치한 콜로세움으로 만들어 봤어요. 여러분도 좋아하는 그림이나 ...

산타학교 졸업을 앞둔 학생들에게 알립니다. 올해 졸업 여행의 주제는 ‘수학’입니다. 먼저 예비 산타들은 4명씩 조를 지어한 배를 탄 ‘크루’를 만들어 주 ... 1. 매스시티 맵 만들기part 2. 최저가 여행, 외판원 문제로 해결part 3. 야구 보며 여행하는 외판원 문제part 4. 무한히 많은 도시 ...

수 있는 범위를 정해두고, 범위를 벗어나는 값들을 지워 계산의 양을 줄이는 거죠.   외판원 문제는 모든 도시를 한 번씩은 반드시 다 들러야 하니, 모든 도시에서 딱 한 번씩 출발하고 한 번씩만 도착해야 합니다. 그래서 각 도시에서 다른 모든 도시로 이동할 때 나올 수 있는 비용 중, 최솟값들을 ...

SAS(미국 소프트웨어 회사) 연구원은 여행하는 야구팬 문제를 해결하기 위해 전통적인 외판원 문제에 ‘사건이 일어나는 시간’이 포함된 알고리듬을 이용했습니다. 각 경기장에서 경기가 있는 날과 경기 시간을 데이터로 이용했죠. 그 결과 24.8일 동안 약 4989km를 이동하는 경로가 최적의 답으로 ...