| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1994년11월28일(월) 04시50분08초 KST 제 목(Title): [보충]일반화된 총최단거리문제 총 최단거리라는 말은 minimum total cost입니다. 연결이 되면서 가장 적은 total cost (여기선 총 거리)가 되려면 cycle이 생기지 않겠죠? 그런 구조가 tree구조입니다. minimum (cost) spanning tree를 구하는 방법은 시중에 많이 나와있지요. 그리고 Polynomial time으로 풀릴 수 있는 방법입니다. 만일 n개의 점이 평면위 random하게 분포되어 있다고 할 경우. 그 n개의 점 이외에도 임의로 다른 점들을 추가해서 연결 시킬 수 있다면 그 거리는 더 짧아지겠죠. (예: 스테아님의 답) 그 임의의 점들을 steiner point라고 합니다. 그리고 그렇게 해서 나오는 tree를 steiner tree라고 하구요.. steiner minimal tree(SMT) 는 그런 tree들중 가장 적은 total cost를 가진 것을 말합니다. 응용은 많겠죠. VLSI, 전화선 가장 짧게 여러 곳을 연결한다던지. 하지만 불행이도 아직까지 polynomial time의 해는 없을 뿐더러 그런 해를 구한다는 것은 P = NP임을 증명하는 꼴이 되어 (NP-complete 문제임 SMT문제가) 전산/수학계에서 이름을 떨칠 것이란 얘깁니다. 가장 큰 open problem이기 때문입니다. 그럼 n개의 점이 원위에 균일하게 분포되어 있다면 어떻게 될까요? 그렇게 될 경우 polynomial time해가 존재할까요? 만일 존재한다면 어떤 모양이며 그 코스트가 어떻게 될 것인가 하는 문제입니다. n=3일 경우는 steiner point가 한개 존재해서 (그 원의 중심) 각점을 연결하는 형태가 될 것이고, n=4일 경우는 스테아님이 푸신 것처럼 steiner point가 두개 존재하는데 그것을 일반화 시킨 모양과 cost는 어찌 될까하는 문제입니다. 즉 정 n각형의 꼭지점에 위치하는 점들을 연결시킨다고 보면 됩니다. 그 꼭지점들을 도시라고 보고 국도를 놓는다고 생각해보죠. 임의로 만드는 교차로(삼거리 사(네)거리 등등..)는 steiner point에 해당되겠지요? polynomial time의 개념을 안배우신 분들은 신경쓰지 마시고 그냥 그 해만 구해보세요. 우선 n=5와 n=6일 경우만 :) --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |