16 . 스타이너 트리
16.3 얼음길
얼음길
16.3.1 들어가며
앞선 활동, 관광 마을은 매우 더운 지방에서 있던 활동이지만, 이번 활동은 정반대다. 얼어붙은 캐나다 북쪽지방에서 거대한 얼음으로 얼어버린 호수에서 이야기가 시작된다. 제설기를 사용해서 길을 만들어 드릴 사이트(drill site)를 연결해서, 승무원들이 서로 길을 오가며 왕래할 수 있다. 추운 밖에 최소한으로 길을 만드는데 길을 어디에 만들지에 해결하는 것이 주어진 과제다. 제약조건은 없다: 눈위에 고속도로는 어디에도 놓을 수 있다— 호수는 얼어서 빙판으로 덮혀있다. 표면은 거의 평평하다.
명확하게도 도로를 거의 직선으로 가로질러 가는데, 이유는 조금이라도 구불어지면 불필요하게 거리가 길어지기 때문이다. 모든 지점을 직선으로 연결하는 것은 그렇게 단순하지 않다. 왜냐하면, 빙판위에 교차점을 추가하는 것이 때때로 전체 길이를 줄일 수 있기 때문이다— 한 지점에서 다른 지점으로 이동 시간이 중요한 것이 아니라, 전체 길이가 중요하다.
상기 그림에서, (a)에 드릴 사이트 세곳이 있다.
(b)에서처럼 사이트를 연결하는 것은 납득할만한 도로 네트워크 구성방식이다.
또다른 방법은 삼각형 거의 중앙에 교차점을 만들고 드릴 사이트 세곳을 연결하는 것이다(c).
그리고 세번째 방법으로 전체 도로 길이를 측정한다면,
사실 더 나은 해결책이 된다. 추가 교차점은 스위스 수학자 스타이너(Jacob Steiner, 1796-1863)를 따라
스타이너 (steiner)점이라고 불린다. 스타이너는 문제를 처음 제기했으며,
새로운 점을 넣음으로써 전체 길이가 줄어들 수 있는 것을 주목한 첫번째 수학자다. 스타이너점을 새로운, 가상의 드릴 사이트로 > 간주할 수 있다.
16.3.2 토론
- 학생들이 작업할 문제를 기술하세요. 상기 문제를 사용해서, 학생들에게 세개 지점에서 새로운 점을 하나 추가하는 것이 종종 전체 도로건설 비용을 줄이는 해결책된다는 것을 시범으로 보여주세요.
(a)에서 보여진 것처럼 학생들이 사각형 모양으로 점을 네개 사용한다. 야외로 나가서 가로 1미터, 세로 1미터 정사각형 모양으로 각 그룹마다 잔디위에 못을 네개를 박는다.
학생들이 줄 혹은 고무줄로 못을 연결하는 실험을 하게 한다. 요구한 전체 길이가 최소가 되게 측정하고 기록한다. 이 단계에서 어떠한 스타이너점도 사용하지 말아야 한다. (이 단계에서 최소값은 (b)에서 처럼 정사각형의 세점을 연결해서 전체 길이가 3 미터가 된다.)
이제 하나의 스타이너점을 사용하여 학생들이 더 잘할 수 있는지 살펴본다. (가장 최적의 장소는 (c)로 정사각형의 중앙이다, 그러면 전체 길이는 \(2 \times \sqrt{2} = 2.83\) 미터가 된다.) 두개의 스타이너점을 사용해서 더 잘할 수 있다고 추천한다. (사실 (d)에서처럼 스타이너점을 두개 위치시켜서, 들어오는 도로사이에 각도를 120도로 구성하면, 전체 길이는 \(1 + \sqrt{3} = 2.73\) 미터가 된다.)
스타이너점 세개를 가지고 학생들이 더 잘할 수 있을까? (아니요— 점 두개가 최선이다. 더 많은 점을 사용해서 얻어지는 잇점은 없다.)
학생들과 왜 이런 문제가 어려운지 토론하자. (왜냐하면, 스타이너점을 어디에 놓아야 하는지 모르기 때문에 어렵고, 시도해 볼 수 있는 경우의 수가 많다.)
16.5 활동: 스타이너 트리 예제 2
가능한 가장 짧은 얼음길로 드릴 사이트를 연결하는 방법을 찾아라.
16.5.1 변형과 확장
앞서 원래 활동을 끝마친 그룹에게 흥미로운 실험은 가로 2미터, 세로 1미터 직사각형을 가지고 노는 것이다. 학생들은 스타이너점을 하나 추가하면 더 악화되고, 스타이너점을 두개 추가하면
향상된 해결책이 되는 것을 알게될 것이다. ((b)에 경우 4미터다, (c)의 경우 \(2 \times \sqrt{5} = 4.47\)미터, (d)의 경우 \(2 + \sqrt{3} = 3.73\) 미터가 된다.) 스타이너점을 하나 두는 배치조합이 정사각형일 때보다 직사각형일 때 나빠지는 이유를 학생들이 파악할 수 있는지 살펴보라. (정사각형이 직사각형으로 늘어날 때, (b)와 (d)는 늘어나는 양이 한번만 추가되는 반면에 (c)의 경우에는 양쪽 대각선에 증가하게 된다.)고학년 학생은 좀더 큰 문제를 다룰 수 있다. 장소를 얼음길로 연결하는 배치도 두개가 워크쉬트에 있다. 새로운 워크시트 사본, 혹은, 워크쉬트 위에 투명 슬라이드를 놓고 지울 수 있는 펜을 사용해서 다른 해결방안을 실험할 수도 있다. 다른 방식으로는, 야외 운동장에서 지도 표식을 따라 못을 박아 진행할 수도 있다. 새로운 최단 거리 기록을 세웠을 때 학생들이 학습에 알리도록 한다. ( 다음 첫번째 그림은 첫번째 예제에 대한 최단 거리 해결책을 보여주고, 두번째 예제에 대한 전체 거리가 거의 비슷한, 두가지 가능한 최단 거리 해결책을 보여준다.) 두개의 거이 비슷한 해결책이 있다는 사실이 역설적으로 왜 이런 유형의 문제가 그렇게 어려운지 반증한다— 스타이너점을 놓을 수 있는 선택지가 너무나도 많다!
첫번째 예제에 대한 최소 스타이너 트리
두번째 예제에 대한 두가지 가능한 스타이너 트리
- 다음과 같은 사다리 네트워크는 문제를 확장하는 또다른 방식을 제공한다.
사다리 네트워크
사다리 네트워크에 대한 최소 스타이너 트리가 몇개 다음에 있다. 가로대가 2개인 사다리는 정사각형과 동일하다. 하지만, 가로대가 3개인 사다리에 대해서, 해답이 상당히 다르다— 기억에서 다시 이끌어낼 수 있다면, 발견해내듯이. 가로대가 4개인 사다리의 해답은 가로대가 2개인 사다리 2개를 서로 연결한 것같다. 반면에 가로대가 5개인 사다리의 경우에는 사로대가 3개인 사다리를 좀더 > 확장한 것같다. 일반적으로, 사다리에 대한 최소 스타이너트리는 사다리의 가로대의 단수가 짝수냐 홀수냐에 달려있다. 만약 짝수라면, 가로대가 2단인 사다리 몇개가 서로 연결된 것처럼 보인다. 그렇지 않다면, 가로대가 3개인 사다리의 반복처럼 보인다. 하지만 엄격하게 증명하는 것은 쉽지 않다.
최소 스타이너 트리
- 또다른 흥미로운 활동은 스타이너트리 비눗방울 모델을 구축하는 것이다. 다음에 보여주듯이, 두장의 투명한 플라스틱 판 사이에 장소를 나타내는 핀을 끼워넣는다. 비눗물 용액에 전체 구조물을 담군다. 비눗물에서 빼내게 되면, 아름다운 스타이너 네트워크로 핀이 연결된 비누막을 발견하게 된다. 하지만, 불행하게도 반듯이 최소 스타이터 트리가 되는 것은 아니다. 비누막이 전체 길이를 최소화하는 배치조합을 찾아내지만, 찾아진 배치조합은 단지 지역 최소(local minimum)이지, 전역 최소(global minimum)는 아니다. 좀더 전체 길이를 적게 하려고 전혀 다르게 스타이너점을 배치하게 될 수도 있다. 예를 들어, 처음으로 비눗물 용액에 담궈 빼냈을 때, 첫번째 비누막 배치조합을 확장활동에 나와있는 것처럼 상상할수도 있고, 두번째 비눗물 용액에 담궈 빼냈을 때 또다른 비누막 배치조합을 상상할 수도 있다.
16.6 컴퓨터 과학 핵심 개념
지금까지 다뤄온 네트워크는 최소 스타이너 트리(minimal Steiner trees)다. 트리(tree)라고 불리는 이유는 순환(cycle)이 없기 때문이다. 마치 실제 나무 가지는 분기되면서 자라지만 합쳐지거나, 합쳐진 것이 다시 함께 자라 뻗어나가고 하지 않는다. “스타이너(steiner)” 트리라고 불리는 이유는 새로운 지점(스타이너점)이 나무가 연결할 원래 지점에 추가되기 때문이다. “최소”라고 불리는 이유는 모든 지점을 연결하는 최소 네트워크를 갖기 때문이다. 진흙도시(활동 9)에서 전체 길이가 최소가 되도록 지점을 연결하는 네트워크가 최소생성나무라고 학습했다. 스타이너 > 트리는 다른 것은 동일하고 새로운 점이 추가된다는 것만 차이점이 된다.
활동 14에서 최소생성나무(minimal spanning tree)를 찾아내는 매우 효율적인 알고리즘—욕심쟁이 알고리즘으로 두개의 가장 가깝지만 아직 연결되지 않은 점을 반복적으로 연결해 나감—이 존재하지만, 최소 스타이너 트리 문제에는 일반적으로 효율적인 해답이 없다는게 흥미롭니다. 스타이너 트리는 좀더 어려운데 이유는 어디에 추가 지점을 추가할지 결정해야 하기 때문이다. 사실 다소 놀라운 점은 스타이너 트리 문제에서 가장 어려운 부분이 스타이너점이 위치할 정확한 장소를 결정하기 보다, 대략 어느 지점에 스타이너점을 위치할 것인가 이것이 관건이다. 예를 들어, 두번째 사례에서 두가지 해답 사이의 차이가 된다. 새로운 점을 어디에 찍을 것인가를 알게된다면, 최적 지점을 찾으려고 미세 조정하는 것은 상대적으로 단순하다. 비누막 사례는 매우 효과적으로 작업을 수행하고, 컴퓨터도 마찬가지로 그렇게 할 수 있다.
최소 스타이너 트리를 찾아내는 것이 전화 통신 산업에서 큰 비용절감과 연관된 이야기의 일부분이다. 1967년 이전, 미국 기업고객이 매우 큰 사설 전화 네트워크를 운영했을 때, 전화 회사에서 회선을 임대했다. 비용이 청구되는 금액은 얼마나 회선이 사용되었냐에 따라 과금이 결정되는 것이 아니라 최소 네트워크 기준으로 과금이 결정되었다. 전화 회사가 로터리 루트를 사용하기 때문에 고객은 추가 비용을 지불하지 말아야 하는 것이 이유다. 원래, 얼마를 청구금액을 계산하는 알고리즘은 최소신장트리를 결정하고 산출하었다. 하지만, 1967년경 주요 허브 3개를 소유한 항공기 회사 고객이 주목한 점이 하나 있다. 만약 중간 지점에 네번째 허브가 있다면, 전체 네트워크 길이를 줄일 수 있다는 점이다. 어쩔 수 없이 스타이너점을 전화 교환지점에 놓는다면, 길이가 짧아져서 전화 회사가 청구금액을 낮춰야 했다. 특정 배치조합에서 최소 스타이너 트리가 5% 혹은 10% 정도 최소신장나무보다 짧을 수 있지만, 금액이 매우 큰 경우 유의미한 절감금액이 된다. 스타이너 트리 문제는 종종 최단 네트워크 문제(shortest network problem)라고 불리는데 이유는 지점을 연결하는 최단 네트워크를 찾아내는 것과 관련되기 때문이다.
앞선 두가지 활동 (지도 제작자 퍼즐과 관광 마을)을 다뤄보셨다면, 최소 스타이너 트리 문제가 NP-완전 이라는 말이 놀랍지 않을 것이다. 장소 개수가 증가함에 따라, 스타이너점을 찍을 잠재 위치 개수도 증가한다. 따라서 모든 가능한 조합을 찾아보는 것은 기하급수적으로 늘어나게 된다. 이것이 수천개의 문제 중의 또다른 하나고, 지수시간 검색이 가장 최선인지, 혹은 아직 찾지 못한 다항시간 알고리즘이 존재하는지 알려져 있지 않다. 하지만, 알려진 것은 다음과 같다. 만약 이 문제에 지수시간 알고리즘이 발견된다면, 그래프 채색과 최소 지배 집합을 찾는데 다항시간 알고리즘으로 변환할 수 있다는 것이다. 그리고, NP-완전에 속하는 모든 다른 문제도 또한 포함된다.
앞선 활동 말미에 NP-완전(NP-complete)의 “NP”는 “non-deterministic polynomial”의 약자고 “완전(complete)”는 만약 다항시간 알고리즘이 NP-완전 문제 중 하나에서 발견된다면, 다른 모든 문제에 변환해서 다항시간 알고리즘으로 적용할 수 있다는 것이다. 다항시간에 해결될 수 있는 문제 집합을 P 라고 부른다. 그래서, 핵심적인 질문은 NP-완전 문제에 다항시간 알고리즘이 존재하는냐?& mdash;다른 말로, P=NP?. 이 문제에 대한 정답은 알려져 있지 않고, 현대 컴퓨터 과학의 가장 큰 미스터리 중의 하나로 남아 있다.
다항시간 알고리즘이 존재하는 문제— 설사 알고리즘이 매우 느릴지라도—는 다룰 수 있다(“trackable”)고 한다. 그렇지 못한 문제는 다룰 수 없다(“intractable”)고 한다. 왜냐하면, 컴퓨터가 얼마나 빠르든지 관계없이, 얼마나 많은 컴퓨터를 동원하든지 관계없이, 문제의 크기가 조금만 커져도 실무에서 해결할 수 없다는 것을 의미하기 때문이다. 지도 제작자 퍼즐, 관광 마을, 얼음길을 포함한 NP-완전 문제가 다룰 수 있는지 없는지 알려져 있지 않다. 하지만, 대부분의 컴퓨터 과학자는 NP-완전 문제에 다항-시간 알고리즘이 발견될 것이라는데 회의적이다. 그래서 문제가 NP-완전이라고 증명하는 것이 문제가 태생적으로 다룰 수 없는 문제라는 강한 증거로 간주된다.
효유적인 알고리즘을 찾을 수 없을 때 무엇을 해야 할까요: 세가지 가능한 방법
직장 상사가 최적 솔류션을 가진 효율적인 알고리즘을 고안해 내라고 합니다. 하지만 효율적인 알고리즘을 찾을 수 없다면 여러줌은 무엇을 하실건가요? 스타이점을 도입해서 항공회사가 네트워크 비용을 절약한 사실이 있듯이 분명 그럴 수 있습니다. 만약 최적 솔류션을 도출하는 효율적인 알고리즘이 없다는 것을 증명할 수 있다면, 매우 좋을 것이다. 하지만, 컴퓨터과학에서 이와 같은 부정적인 결과를 증명하는 것은 매우 어렵다. 그리고 누가 알겠는가 좀더 똑똑한 프로그래머가 장래에 나와서 문제를 해결하는 아무도 생각하지 못한 기법을 생각해낼지 말이다. 그래서 불행하게도 어떤 효율적인 알고리즘도 가능하지 않다고 말할 수 있는 범주에 있을 것 같지는 않다. 사실 문제는 다룰 수 없는 것이 맞다. 하지만, 만약 다루는 문제가 NP-완전이라는 것을 보일 수만 있다면, 사실 연구소에서 수천명의 연구원들이 여러줌의 것에 상응하는 다른 문제를 풀기 위해서 작업중이고, 효과적인 해결책을 찾아내는데 실패했다. 이런 사실이 여러분에게 보너스가 되지는 않는다. 하지만, 여러분을 곤경에서 풀어줄 것이다. 물론, 실생활에서 여전히 이들 문제에 대한 답을 찾을 필요는 있다. 이런 경우 사람들은 보통 휴리스틱(heuristics)으로 관심을 돌린다. 휴리스틱 알고리즘은 최적해를 보장하지는 않지만, 최적해와 비교하여 약간 차이가 있는 해결책을 제시한다. 휴리스틱 알고리즘은 매우 빠르고, 최적해를 찾지 못하는데 드는 낭비가 매우 적다. 그래서 실무에서 적용하여 사용하는데 충분하다. 좀더 나은 시간표와 좀더 나은 네트워크나 도로 건설 배치가 있다는 것을 알게되면 약간 실망스러울 뿐이다.