세일즈맨의 최단 경로 찾기

세일즈맨이 물건을 팔기 위해 5개의 도시를 순회하려고 하는데, 하나의 도시는 반드시 한 번만 방문한다고 할 때 최단 경로를 어떻게 찾을 수 있을까? 이는 ‘세일즈맨 최단 경로 문제’라고 하는 것으로서 동선(動線)의 최적화 문제를 다룰 때마다 약방의 감초 격으로 등장한다.

확실한 방법은 모든 경우를 하나씩 비교해보는 것이다. 도시가 5개라면 세일즈맨이 갈 수 있는 경로는 모두 120가지(5!=5×4×3×2×1)가 된다. 이 정도는 하루 정도의 시간과 인내심만 있다면 얼마든지 풀 수 있다.

도시가 25개로 늘어난다면 문제는 심각해진다. 상상을 초월하는 천문학적인 경우의 수(25!)가 나오기 때문이다. 초당 100만 번의 비교가 가능한 수퍼컴퓨터로도 4900억 년이라는 엄청난 시간이 걸린다. 우주의 나이인 100억 년보다 훨씬 오랜 억겁(億劫)의 시간이 필요하다.

하지만 비즈니스의 세계에서는 포기할 수 없는 노릇이다. 25개가 아니라 그 이상의 도시가 존재할 때도 최단 경로를 찾아야 하기 때문이다. 100% 만족스러운 답이 이론적으로 힘들다면 60% 혹은 70%만 만족할 수 있는 답이라도 찾아야 한다.

단숨에 답을 찾겠다는 만용은 버려야 한다. 무수히 많은 경로 중 가장 짧을 것 같은 두 개의 경로를 먼저 골라내야 한다. 그런 다음 서로 비교해 둘 중에 더 짧은 경로를 택하는 방법을 취하면 된다. 어느 정도 만족 할 만한 수준에 도달했다고 판단되면 문제 풀기를 멈춘다. 그것이 최단 경로가 아니라도 말이다. 정해진 기간 내에 25개의 도시를 모두 돌 수 있는 경로인지, 교통비를 감당할 수 있는 수준인지 등을 검토해야 되기 때문이다. 무식해 보이긴 하지만 이 같은 ‘한 걸음씩’ 접근방식이 복잡한 현실의 문제를 푸는 데 최선이다.

변화무쌍한 환경에 맞서 매순간 선택의 위험을 무릅써야 하는 기업이 경영의 해법을 찾기란 극히 어렵다. 그런데 세상이 복잡하게 변하고 그 변화에 치이다 보니 경영자들은 단순하면서도 명쾌한 해답을 찾는다. 경영자들의 그런 심정은 충분히 이해할 만하다. 그러나 최고의 완벽한 해법을 찾아야 한다는 생각은 경영자의 강박관념 내지는 편집증에 불과하다. 완벽을 추구하겠다는 의지는 높게 살 만하지만, 전략 실행의 타이밍을 놓치는 정도라면 곤란하다.

예일대 교수였던 찰스 린드블롬은 “현실의 복잡성을 완전하게 분석하는 것은 사실상 불가능하다”며 “이 때문에 주어진 정보와 처한 상황에 맞춰 최상의 결정을 하고 실행하면서 고쳐가는 것이 효과적인 방법”이라고 역설했다.

기업의 전략 수립에 있어서도 세일즈맨 문제 풀기처럼 ‘한 걸음씩’ 접근방식을 취해야 한다. 완벽한 답은 찾기 어렵고, 설령 찾았다 하더라도 전략적 수명은 오래가지 못한다. 현실적인 입장에서 가장 적합한 방안을 한 걸음씩 찾아가고, 그것을 적절한 타이밍에 맞춰 실행하겠다는 자세가 경영자에게는 중요하다.