美 수학자 한국 모든 술집 방문 최단 경로 계산…178일 2시간 걸린다 작성일 04-21 107 목록 <div id="layerTranslateNotice" style="display:none;"></div> <div class="article_view" data-translation-body="true" data-tiara-layer="article_body" data-tiara-action-name="본문이미지확대_클릭"> <section dmcf-sid="H83BjNEQiP"> <figure class="figure_frm origin_fig" contents-hash="3b976bb02a70805590f8af3727d27b5666d5554ac3097f47f16f36cdc5b18535" dmcf-pid="X60bAjDxM6" dmcf-ptype="figure"> <p class="link_figure"><img alt="윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공" class="thumb_g_article" data-org-src="https://t1.daumcdn.net/news/202504/21/dongascience/20250421103235171bbgn.png" data-org-width="680" dmcf-mid="YoHFdeLKLx" dmcf-mtype="image" height="auto" src="https://img1.daumcdn.net/thumb/R658x0.q70/?fname=https://t1.daumcdn.net/news/202504/21/dongascience/20250421103235171bbgn.png" width="658"></p> <figcaption class="txt_caption default_figure"> 윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공 </figcaption> </figure> <p contents-hash="818ede9e3df4122957a980fed1d48f13fb695cb06d8baad0937f466feb715abe" dmcf-pid="ZPpKcAwMe8" dmcf-ptype="general">미국 유명 수학자가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 쉬지 않고 모든 술집을 걸어서 방문하면 178일 1시간 56분 17초가 걸린다. </p> <p contents-hash="bad57f2f9f38da370f0a1f4b924c04c1568df6ea22058c8d5822665a5bc69eec" dmcf-pid="5QU9kcrRR4" dmcf-ptype="general"> 윌리엄 쿡 캐나다 워털루대 수학과 교수는 이달 8일(현지시간) 모든 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 계산하고 증명한 결과를 자신의 홈페이지에 공개했다. 쿡 교수는 조합론과 최적화 분야에서 세계적인 수학자다. </p> <p contents-hash="2b3485da84318e798ca2ec11b88244c6a31405d5a95dba8d41677ebac296651c" dmcf-pid="1xu2Ekmenf" dmcf-ptype="general"> 쿡 교수는 '외판원 문제(TSP)'라고 불리는 유명한 수학 문제를 도로에서 최적의 경로를 찾는 문제에 적용했다. 외판원 문제란 도시가 여러 개 있을 때 외판원이 모든 도시를 한 번만 지나가면서 전부 방문할 수 있는 가장 짧은 거리를 구하는 문제다. 방문하는 도시의 수가 같더라도 각 도시를 연결하는 경로가 다르고 가장 짧은 거리를 찾아야 하기 때문에 무엇을 대상으로 하느냐에 따라 완전히 다른 문제가 된다. </p> <p contents-hash="6d96c169117af1dd7e51f3f443f9e7a34bab160d6cedbf9ef12aba3ac99beafa" dmcf-pid="tM7VDEsdeV" dmcf-ptype="general"> 쿡 교수는 엄상일 기초과학연구원(IBS) 이산수학그룹 CI로부터 제공 받은 한국 경찰청의 '전국 술집 위치정보'를 이용했다. 주소, 위도, 경로 등이 포함된 전국 술집 위치정보에 따르면 2023년 기준 한국 술집 개수는 9만680개다. 쿡 교수는 같은 건물에 있는 여러 술집은 1개의 술집이라고 설정하는 등 데이터를 정리해 술집 개수를 8만1998개로 설정했다. </p> <p contents-hash="250c6155f2b9203f31040f7ef054a8f2684c1c63e579f65082be6cf670d36862" dmcf-pid="FRzfwDOJi2" dmcf-ptype="general"> 쿡 교수는 술집 8만1998개를 이용해 술집 2개씩을 붙여 한 쌍을 만드는 작업을 했다. 술집은 중복으로 등장할 수 있다. 총 33억 6179만 5003개쌍이 나왔다. 쿡 교수는 최단 거리를 계산해주는 공개 시스템인 '오픈소스라우팅 머신(OSRM)'을 이용해 각 쌍에 묶인 2개 술집을 서로 걸어서 잇는 최단 거리를 계산했다. </p> <p contents-hash="5facbac64093715fb6ee4043ae71bbc490686e80c8566f32bf37926fa1e4de03" dmcf-pid="3eq4rwIin9" dmcf-ptype="general"> 쿡 교수는 이 방대한 최단 거리 데이터를 조합해 '분기한정법(branch and bound)'으로 최적의 경로를 찾아냈다. 분기한정법이란 최적의 답이 될 만한 후보를 나무 가지처럼 늘어놓고 답이 될 가망이 없는 가지는 가차 없이 잘라버리는 방법이다. 답이 나올 수 있는 범위를 정해두고 범위를 벗어나는 값들을 지워 계산의 양을 줄일 수 있다. </p> <p contents-hash="dd86bd7394cf724441e92f86b7d7f691ee4e42d9deafb02403e651b7f1633ded" dmcf-pid="0dB8mrCneK" dmcf-ptype="general"> 쿡 교수는 3개월에 걸쳐 여러 대의 컴퓨터를 병렬로 이용해 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 찾아냈다. 병렬로 연결된 각 컴퓨터가 문제를 푸는 데 사용한 시간을 모두 합하면 총 44년이다. 결과에 따르면 최단 경로에 소요되는 시간은 178일 1시간 56분 17초다. 연구 논문은 연말에 나올 예정이다. </p> <p contents-hash="869343dd9e58fb00ed769722cbbcb64b7404c42360e90b2552988ae6f0a0b5ec" dmcf-pid="pzWteRnbJb" dmcf-ptype="general"> 동아사이언스에 쿡 교수는 "이번 문제를 2121개의 하위 문제로 바꿔 계산하는 양을 줄이는 수학적 아이디어로 해결했다"며 "외판원 문제를 길에서 여러 장소를 방문하는 최단 경로를 찾는 문제에 적용한 사례 중 가장 많은 수의 장소를 계산한 것"이라고 말했다. 직전 최고 기록은 2021년 네덜란드의 5만7912개 기념물을 방문하는 연구결과다. </p> <p contents-hash="0880c585347eced0bfc737a9919363ce4e19b1709e386298522844a1c9ea6843" dmcf-pid="UqYFdeLKLB" dmcf-ptype="general"> 쿡 교수는 "한국 경찰청이 제공하는 데이터가 정확하고 방대해 한국 술집 정보를 이용하게 됐다"고 말했다. 쿡 교수는 지난해 IBS 방문을 앞두고 한국 학생들을 위한 강연을 준비하면서 이번 문제에 도전하기 시작했다. 엄 CI는 "술집 위치정보를 구매한 가격은 단돈 1000원이다"며 "저렴한 가격으로 훌륭한 수학결과가 나오는 데 일조해 뿌듯하다"고 했다. </p> <p contents-hash="f7b2edb47b562a098dd97aed7fe4c2bc15e5c82afc0aa9031f23ee02188bf44b" dmcf-pid="uBG3Jdo9Rq" dmcf-ptype="general"> 외판원 문제는 수학 문제이지만 실생활을 비롯해 산업계 전반에 적용되고 있다. 택배 물품을 전달하는 최적의 경로, 반도체 기판을 만드는 방법 등에 외판원 문제가 사용된다. 엄 CI는 "외판원 문제를 우주의 수많은 별을 방문하는 최단 경로를 계산하는 데도 적용할 수 있다"며 "외판원 문제에서 방문 대상 숫자를 높이며 최적화를 할 수 있는 새로운 수학적 아이디어를 생각해낼 수 있다는 의미가 있다"고 말했다.</p> <figure class="figure_frm origin_fig" contents-hash="79524ffcaa955e76d5605a15cc55fff06b3bb4cc32a1760842b9d2ab71383b56" dmcf-pid="7bH0iJg2Rz" dmcf-ptype="figure"> <p class="link_figure"><img alt="쿡 교수. 위키미디어 제공" class="thumb_g_article" data-org-src="https://t1.daumcdn.net/news/202504/21/dongascience/20250421103236496prlj.jpg" data-org-width="349" dmcf-mid="GqIW4fQ0dQ" dmcf-mtype="image" height="auto" src="https://img2.daumcdn.net/thumb/R658x0.q70/?fname=https://t1.daumcdn.net/news/202504/21/dongascience/20250421103236496prlj.jpg" width="658"></p> <figcaption class="txt_caption default_figure"> 쿡 교수. 위키미디어 제공 </figcaption> </figure> <p contents-hash="4f25d7cc016c68210c26d16d66b208c8cdeb59e20a223e2c9631217023aa0d5c" dmcf-pid="zKXpniaVJ7" dmcf-ptype="general">다음은 쿡 교수와의 일문일답.</p> <p contents-hash="2a67c62fa30371155796ee399fea3a87ec8e91fea9858e5b878f04b1d24d10ff" dmcf-pid="q9ZULnNfiu" dmcf-ptype="general"><strong>Q. 외판원 문제에 대한 대중 서적도 쓴 바 있다. 외판원 문제가 중요한 이유가 무엇인가.</strong></p> <p contents-hash="a5f9991d517b56168201a8de28d944c0a80e9d7e6c0111ade0627afd1f7d9d79" dmcf-pid="B25uoLj4nU" dmcf-ptype="general">"외판원 문제는 수학에서 가장 유명한 최적화 문제다. 유전학, 기계 정보처리, 데이터 분석 등 다양한 분야에서 활용된다. 특히 미국에서 배송 트럭 경로 계산에 응용되고 있다. 아마존 택배 기사인 '아마존 프라임 드라이버'는 평균 150회 이상 배송을 위해 정차한다. 아마존은 택배 기사의 최적 경로를 알아내기 위해 2021년 전 세계적으로 외판원 문제를 아마존 택배 기사 경로에 적용해 최적 경로를 알아내는 문제를 개최했다. </p> <p contents-hash="3ba39b24c52f03a8eefa37db2a722b0ce16a3d1abbb293e6836b4d5f3302130f" dmcf-pid="bV17goA8np" dmcf-ptype="general">하지만 이 같은 응용은 수학에서 외판원 문제의 확장성 중 일부다. 외판원 문제는 복잡성 세계의 중심에 있다. 외판원 문제는 복잡한 계산을 얼마나 잘할 수 있는지 인간의 계산 능력의 한계를 탐구하게 한다는 의미가 있다."</p> <p contents-hash="7397a9e9964369dd6f9ac7fd165a6ed4e5aaf34f862f671fd6c9b00e2544235a" dmcf-pid="Kftzagc6e0" dmcf-ptype="general"><strong>Q. 한국 술집처럼 사람들과 친숙한 장소를 최적 경로 찾기 대상 장소로 설정한 이유는?</strong></p> <p contents-hash="a1728ab811842f3f7ad5c31c762a0cda240b01bc3e7e0c0b2d9be74ac5983c54" dmcf-pid="94FqNakPJ3" dmcf-ptype="general">"2016년에는 미국 역사 유적지, 2018년에는 영국 술집, 2021년에는 네덜란드 기념물 위치를 이용해 외판원 문제를 풀었다. 인류에게 굉장히 중요한 최적화 문제에 사람들의 관심이 높아졌으면 좋겠다고 생각해 친숙한 소재를 가져오고 있다. 최적화 문제에 도전하는 사람이 많아지면 인류의 미래는 크게 바뀔 수 있다."</p> <p contents-hash="698ef1e3768e77d1a3d2b3e9babd25791d1a16e486f19ed34d35103371ad087c" dmcf-pid="283BjNEQMF" dmcf-ptype="general"><strong>Q. 한국과 인연이 깊다고 들었다. </strong></p> <p contents-hash="7fda8a928709f01a5d6733383ea38221228a06d7169960ab2ad894037a0d8951" dmcf-pid="V60bAjDxMt" dmcf-ptype="general">"1989년 미국 벨 커뮤니케이션 연구소에서 일하고 있을 때 현재 김명희 올드 웨스트버리 뉴욕주립대 수학과 교수를 만나 인연을 맺었다. 당시 김 교수의 컴퓨터를 빌려 수학 문제를 풀었던 기억이 있다. 그리고 2002년 미국 프린스턴대 수학과에서 박사 과정을 밟고 있던 엄 CI와 알게 됐다. 엄 CI는 내게 외판원문제의 하한을 구하는 프로그램을 만들었다고 메일을 보내왔다. </p> <p contents-hash="ec33148cfbcadc09f1fe85c633c4c0db3242bc39c23adf74b11b202eda5a2f02" dmcf-pid="fUvZxQdzd1" dmcf-ptype="general">한국 방문은 지난해가 처음이다. 2020년 5월 한국 방문을 앞두고 있었지만 코로나10 팬데믹이 터져 방문이 취소됐다. 당시 IBS 이산수학그룹에 박사후연구원으로 제 딸인 린다 쿡 박사가 3년째 재직 중이라 한국 방문이 더욱 뜻깊었다. </p> <p contents-hash="aeab500843b8484a20e684da997be9579d8644d841d1be2ca87400df14a1cdda" dmcf-pid="4uT5MxJqi5" dmcf-ptype="general"><strong>Q. 앞으로의 목표가 무엇인가. </strong></p> <p contents-hash="67b391179b2329ca9896c1a3f4a9fbce26390ba465e904d61db46a108e135092" dmcf-pid="87y1RMiBJZ" dmcf-ptype="general">"항상 더 크고 더 어려운 최적화 문제를 해결하기 위해 항상 노력할 것이다. 어떤 최적화 문제에도 적용할 수 있는 최적화 문제 해법을 만들고 싶다. 세상에 자원은 한정돼 있기 때문에 수학적 최적화를 통해 자원을 효율적으로 사용하는 것이 점점 중요해질 것이다."</p> <p contents-hash="db3459852c8732a40632bd9bf02c979d00ae1e61246af183ae692703c34185eb" dmcf-pid="6zWteRnbRX" dmcf-ptype="general"><참고자료></p> <p contents-hash="0a324359e31b8d9bcb79e8bcc0f26067a8a43df50cd998e84dcdda37f1ada6fa" dmcf-pid="PqYFdeLKnH" dmcf-ptype="general">-https://www.math.uwaterloo.ca/tsp/korea/sk_index.html</p> <p contents-hash="90c23b6f8aa98f06f9bdeb43772036f72087604ad65b32b2d86aff952b102810" dmcf-pid="QBG3Jdo9JG" dmcf-ptype="general">-https://dimag.ibs.re.kr/2024/william-cook/</p> <p contents-hash="8438fa0f53d6b82b8e8b0b1486a4974a4faf7bb5a0535692384a7a43406d647a" dmcf-pid="xbH0iJg2eY" dmcf-ptype="general">-https://dimag.ibs.re.kr/2023/interview/</p> <p contents-hash="05dd746638b6188ceac72e9c04579ccc2d12eb8c968733fbc6d897719a7b1dc3" dmcf-pid="yrdNZXFOJW" dmcf-ptype="general">-https://www.math.uwaterloo.ca/tsp/star/gaia1.html</p> <p contents-hash="238a51b5498d3f4a617c0d9d74cf4e8ee984bd6a9bad44cde02e37134c0a45b7" dmcf-pid="WmJj5Z3Idy" dmcf-ptype="general">-https://www.newscientist.com/article/2258086-mathematicians-have-found-the-shortest-route-to-visit-2-million-stars/</p> <p contents-hash="c244b24f6c5110988f17cea5b941cfb02730126f45f6678e607db0fc32e6bfc3" dmcf-pid="YsiA150CJT" dmcf-ptype="general">[대전= 이채린 기자 rini113@donga.com]</p> </section> </div> <p class="" data-translation="true">Copyright © 동아사이언스. 무단전재 및 재배포 금지.</p> 관련자료 이전 "R&D카르텔 낙인, 시스템 불신 키워…장기 계획으로 대체불가 기술 키워야" 04-21 다음 산호초 살린 삼성 갤럭시 카메라 기술…농구장 25배 면적 복원에 기여 04-21 댓글 0 등록된 댓글이 없습니다. 로그인한 회원만 댓글 등록이 가능합니다.
