바다에서 육지에 부딪히지 않고 얼마나 멀리 항해할 수 있을까, 반대로 큰 물을 만나지 않고 얼마나 멀리 차를 몰 수 있을까. 언뜻 술자리 잡담처럼 들리는 이 질문은 사실 잘 정의된 최적화 문제다. 2018년 arXiv에 공개된 논문 'Longest Straight Line Paths on Water or Land on the Earth'는 이 두 가지 경로를 계산하는 방법론을 제시하면서, 지리 데이터 위에서 최적해를 찾는 일이 왜 만만치 않은지를 보여준다. 온라인 커뮤니티에서 '지구에서 가장 긴 직선 항로'가 화제가 되면서 시작된 호기심을, 저자들은 알고리즘 관점에서 다시 정리했다.
왜 단순 계산이 아닌가
문제의 핵심은 '직선'이 지구라는 구면 위에서는 대원(great circle)을 따라간다는 점, 그리고 그 경로가 지나가는 지형이 극도로 복잡하다는 점이다. 논문은 이 문제를 최적화 문제로 규정하면서도, 섬과 호수의 존재 때문에 해 공간이 혼돈스러워진다고 지적한다. 넓게 트인 바다 한가운데 작은 섬 하나만 있어도 그 지점을 지나는 무수한 항로가 무효가 되고, 육지 경로에서는 반대로 호수 하나가 길을 끊는다. 여기에 해안선 자체가 프랙털 구조라는 점이 더해진다. 해안선은 관측 해상도를 높일수록 길이가 늘어나고 굴곡이 세밀해지므로, 어느 축척의 데이터를 쓰느냐에 따라 '육지에 닿았다'는 판정 자체가 달라진다. 결국 정답은 사용한 지형 데이터의 정밀도와 분리해서 말하기 어렵다.
분기한정법이라는 선택
지구 표면 위 모든 시작점과 방향의 조합을 하나하나 검사하는 무차별 탐색은 계산량이 감당하기 어렵다. 논문이 채택한 도구는 분기한정법(branch-and-bound)이다. 이 기법은 탐색 공간을 여러 영역으로 쪼개고(분기), 각 영역이 가질 수 있는 최선의 값에 대한 상한을 추정한 뒤, 그 상한이 이미 확보한 최선의 해보다 나쁘면 해당 영역 전체를 더 파고들지 않고 잘라낸다(한정). 유망하지 않은 가지를 통째로 배제하기 때문에, 이론적으로는 전수 탐색과 같은 최적해를 보장하면서도 실제 계산량을 크게 줄일 수 있다. 조합 최적화나 정수 계획법에서 오래 검증된 이 접근을 지리 좌표 공간에 옮겨 적용했다는 점이 이 연구의 방법론적 골자다.
실무자가 눈여겨볼 지점
이 논문은 흥미 위주의 주제를 다루지만, 지리정보(GIS)나 최적화를 다루는 개발자에게는 익숙한 패턴의 사례 연구로 읽힌다. 첫째, 문제를 명확한 목적함수와 제약조건으로 환원하는 모델링의 힘이다. '가장 긴 항로'라는 모호한 질문을 대원 거리 최대화와 육지 미접촉이라는 조건으로 정식화하는 순간, 검증된 알고리즘 자산을 끌어다 쓸 수 있게 된다. 둘째, 데이터 해상도와 결과의 관계다. 해안선의 프랙털 특성은 실무에서 흔히 만나는 '입력 정밀도가 곧 출력 신뢰도의 상한'이라는 원리를 극단적으로 보여준다. 같은 알고리즘이라도 저해상도 해안선 데이터로 낸 답과 고해상도로 낸 답은 다를 수 있다.
동시에 한계도 분명하다. 논문은 계산 방법론을 제시하는 데 초점이 있으며, 제공된 요약만으로는 사용한 지형 데이터셋의 구체적 사양이나 판정 기준의 세부가 온전히 드러나지 않는다. '큰 물'과 무시할 만한 물을 어디서 가르는지, 어느 축척의 해안선을 채택하는지 같은 선택은 결과 수치를 좌우하는 변수인데, 이런 전제들은 결과를 인용하기 전에 반드시 확인해야 한다. 분기한정법 역시 만능은 아니어서, 상한 추정이 느슨하면 가지치기 효과가 줄어 최악의 경우 탐색 비용이 급증할 수 있다.
그럼에도 이 연구가 남기는 교훈은 견고하다. 흥미로운 질문 하나가 정확한 정식화와 적절한 알고리즘 선택을 만나면 재현 가능한 계산 문제로 바뀐다는 것, 그리고 지구처럼 지저분하고 프랙털적인 실제 데이터 위에서는 '정답'이 언제나 데이터 품질이라는 전제 위에 서 있다는 것이다. 최적화 도구를 다루는 이들에게는, 화려한 결과값보다 그 값이 어떤 가정에서 나왔는지를 먼저 묻는 태도가 왜 중요한지를 되새기게 하는 사례다.