선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이러한 응용들의 어떤 경우에는, 연결 방법을 찾는 시간을 단축하는 것보다는 입력 선분들을 최소의 비용으로 연결하는 것이 중요할 수 있다. 본 논문에서는 이러한 응용을 위해서 스타이너 트리를 이용하여 입력 선분들을 최소 비용으로 연결하는 방법을 제안한다. 제안된 방법에서 입력 선분은 노드로, 입력 선분의 연결은 연결선으로 변환하여 최소 신장 트리를 생성하고, 이 트리에 대한 스타이너 포인트를 생성하여 스타이너 그래프를 생성한 후, 이것에 대한 후처리 작업을 시행하여 입력 선분들에 대한 연결선을 생성한다.
- 본 연구와 유사한 연구 분야인,선분 연결 관련 연구는 많이 발표되지 않았는데, 그 중에서 입력 선분의 연결 문제를 변형된 최소 신장 트리와 입력 선분 상의 임의의 가상 노드인 포탈을 이용하여 선분을 사용자의 요구에 따라 연결하려는 연구가 시도되었다. 이 연구에서 선분 연결 방법의 결정 시, 연결 방법을 찾는 시간과 연결 비용을 조절하면서 특정 응용에서 관심 있는 방법을 선택할 수 있는 방안을 제안하였다[7]. 현재까지 발표된 많은 근사 최소 스타이너 트리를 구성할 수 있는 휴리스틱 중에서, 정삼각형의 외접원을 활용하여 스타이너 포인트를 구하는 휴리스틱이 대표적인 방법이다[15].
- 본 논문에서 스타이너 포인트를 적절히 생성하고 이를 이용한 스타이너 트리를 활용하여 최소 비용으로 입력 선분들을 연결하는 방법을 제안한다. 본 논문에서 다루는 입력 선분은 통신 네트워크에서의 통신선 또는 동적 객체의 정해진 이동궤적으로 간주될 수 있다.
제안 방법
- 본 논문에서는 이러한 응용을 위해서 스타이너 트리를 이용하여 입력 선분들을 최소 비용으로 연결하는 방법을 제안한다. 제안된 방법에서 입력 선분은 노드로, 입력 선분의 연결은 연결선으로 변환하여 최소 신장 트리를 생성하고, 이 트리에 대한 스타이너 포인트를 생성하여 스타이너 그래프를 생성한 후, 이것에 대한 후처리 작업을 시행하여 입력 선분들에 대한 연결선을 생성한다.
- 본 논문에서 제안하는 방법인 입력 선분을 스타이너 트리를 이용하여 연결하는 것은 입력 노드를 대상으로 한 전통적인 최소 신장 트리의 생성과 관련이 있다. 일반적인 환경과 입력에서 트리의 길이가 최적화된 최소 신장 트리는Kruskal 혹은 Prim의 알고리즘을 이용하여 얻을 수 있다[4-6].
- 본 논문에서 제안하는 방법은 에 기술되어 있는 최소 신장 트리를 이용한 선분 연결하는 방법과 비교된다[7].
- 이 알고리즘에서 주어진 입력 선분과 그 연결에 대하여 2장의 에서 기술한 변형된 Prim의 알고리즘을 응용한 선분 최소 신장 트리를 먼저 생성하고 이를 기반으로 하여 스타이너 포인트를 생성하고 이를 연결하여 스타이너 그래프를 생성한다.
- 또한 이 최소 신장 트리 생성 방법은 제안된 방법의 초기 단계에서 일부 사용된다. 최소 신장 트리 생성은 Prim의 알고리즘을 변형하였는데, 이 알고리즘은 주어진 노드들과 이들 사이의 입력 연결선을 이용하여 최소 비용의 신장 트리를 생성할 수 있다. 본 논문에서 제안하는 문제는 입력 선분들을 최소 비용으로 연결하는 것이므로 최소 신장 트리생성 알고리즘을 바로 응용할 수 없고 적절한 변환이 필요하다.
- 이 알고리즘에서 주어진 입력 선분과 그 연결에 대하여 2장의 <표1>에서 기술한 변형된 Prim의 알고리즘을 응용한 선분 최소 신장 트리를 먼저 생성하고 이를 기반으로 하여 스타이너 포인트를 생성하고 이를 연결하여 스타이너 그래프를 생성한다. 이 스타이너 그래프를 구성하는 노드와 연결들을 노드와 연결선으로 입력하여 새로운 최소 신장 트리를 생성한 후에, 필요 없는 연결선의 제거 및 새로운 최단 거리의 연결선을 생성하는 후처리 작업을 시행하고 이에 대한 결과를 최종 연결로 결정한다. 본 논문에서 다루는 문제는 입력 선분의 연결 문제는 기존의 최소 신장 트리 생성과는 다르게, 입력은 노드가 아닌 선분이고, 따라서 노드간의 연결 대신 선분간의 연결이므로 적절한 변환이 필요하다.
- 15이상이 되도록 제한을 가하였다. 실험환경은 Intel 1.83 GHz (T5600) 프로세서와 1기가 메모리 램의 랩탑 컴퓨터이고, 본 논문에서 제안하는 알고리즘을 C++로 구현하였다.
- (그림 6)은 본 논문에서 제안하는 후처리 효과에 대한 실험 결과이다. 실험 인자인 입력 선분의 수와 한 선분 당 최대 연결 수를 변경하여 생성되는 연결들의 길이 절감 비율을 관찰하였다. 후처리 절감 비율은 후처리를 시행함으로 절약되는 길이의 비율이다.
- 최소 스타이너 트리는, 다항적 시간 (Polynomial Time) 내에 최적의 해를 구할 수 있는 최소 신장 트리보다 연결 비용은 적지만, 이를 구성하는 것은 비 다항 적 시간(Non-Polynomial Time) 문제에 포함되므로 이를 위한 알고리즘은 오랫동안 발표되지 못했다. 입력 선분들을 연결하기 위해, 본 논문에서 제안하는 방법은 먼저 입력 선분과 입력선분간의 연결을 적절히 변환하여 선분 최소 신장 트리를 생성하고, 이 트리의 연속적으로 연결된 세 개의 노드로 구성된 모든 부분 트리에 대하여 스타이너 포인트를 생성하고 이들을 연결한 스타이너 그래프를 생성한다. 이 그래프에서 불필요한 연결을 삭제하고 후처리 작업을 통해 좀 더 연결 비용을 절감한다.
대상 데이터
- 단계 4에서 차수가 1인 스타이너 포인트를 찾고 이를 처리하는 시간은 스타이너 포인트의 수와 동일한 O(E2)이고, 단계 6에서 스타이너 포인트와 입력 선분간의 최단거리를 검사하고 처리하는 시간은 O(E2)이다. 따라서 본 논문에서 제안하는 방법의 실행 시간은 O(E2logE) 이다. 그러나 입력 선분과 입력 연결에 대해 생성되는 최소 신장 트리의 토폴로지가 스타 형일 가능성은 적으므로, 이보다는 빠른 시간 내에 실행이 가능할 것이다.
- 본 연구를 위해 사용된 실험 인자는 입력 선분의 수와 한 선분에서 최대로 연결할 수 있는 다른 입력 선분의 수이다. 관찰 결과는 입력 선분들을 연결한 연결선의 길이와 입력 선분의 연결 방법을 생성하는 시간이다.
- 연결 길이와 생성 시간은 <표 1>의 최소 신장 트리 알고리즘으로 생성된 선분 최소 신장 트리와 비교된다. 실험을 위해 무작위로 생성된 입력 선분의 수는 500, 1000, 1500, 2000, 2500, 3000개이다. 각 선분의 최대 연결의 수는 입력 선분 수의 20%, 40%,60%, 80%, 100%로 하였는데, 예를 들어 입력 선분이 500개의 경우, 최대 연결 20%는 각 선분에서 최대 100개의 다른 선분과 연결할 수 있다는 것을 의미한다.
이론/모형
- 본 논문에서 제안하는 문제는 입력 선분들을 최소 비용으로 연결하는 것이므로 최소 신장 트리생성 알고리즘을 바로 응용할 수 없고 적절한 변환이 필요하다. 즉 입력 선분을 노드로, 선분 연결을 연결선으로 변환한 후에 그 연결선의 길이를 가중치로 이용하여 순수한 Prim의 알고리즘을 적용한다. 최소 신장 트리를 이용한 입력 선분의 연결 과정은 <표 1>과 같고, 이에 대한 간단한 예는 (그림 3)의 (a), (b), (c)에 나타나 있다.
성능/효과
- (그림 4)의 (a)와 (b)에서 확인할 수 있는 것처럼 제안된 방법을 이용한 입력 선분의 연결은 최소 신장트리를 이용한 선분 연결 방법에 비해 길이는 감소된다. (그림 4)의 (a)에서 입력 선분의 수가 커질수록 제안하는 방법의 연결 길이의 절감율은 점차 떨어지지만, 그 변화량은 그리 크지 않음을 확인할 수 있다. 입력 선분의 수가 500일 때, 최고인 약 8.
- 9%이다. 입력 선분의 수가 많으면, 한정된 공간에서 최소 신장 트리를 이용한 연결 방법보다 더 단축된 연결 방법을 찾을 수 있는 가능성이 감소함을 확인할 수 있다. (그림 4)의 (b)는 한 입력 선분에서 연결 가능한 최대 연결 수를 변경하면서, 제안된 방법으로 생성된 연결의 길이를 분석한 결과로서, 한 선분 당 최대 연결 수가 적을수록 연결 길이의 절감율은 높다.
- 이는 선분간의 연결이 완전 연결에 근접할수록 최소 신장 트리를 이용한 연결 방법보다 더 단축된 연결방법을 확률적으로 찾기 어렵기 때문이다. 모든 입력 환경에 대하여 제안된 방법을 이용한 선분 연결 길이는 최소 신장 트리를 이용한 방법에 비해 평균 6.8% 감소되었다.
- (그림 5)는 실험 입력 인자인 입력 선분의 수와 한 선분당 최대 연결 수를 변경하면서, 본 논문에서 제안하는 방법으로 입력 선분의 연결선을 생성할 때, 필요한 실행시간에 대한 분석결과이다. (그림 5)의 (a)에서, 입력 선분의 수가 커질수록 제안된 방법과 최소 신장 트리를 이용한 방법 모두 실행 시간이 증가되고, 제안 방법이 좀 더 많은 시간이 소요됨을 보인다. 그러나 입력 선분의 수에 따른 제안된 방법의 실행 시간 증감율은 일정한 규칙을 보이지 않는다.
- 그러나 입력 선분의 수에 따른 제안된 방법의 실행 시간 증감율은 일정한 규칙을 보이지 않는다. (그림 5)의 (b)는 한 선분 당 최대 연결 수를 변경하며 선분 연결을 생성한 실험의 결과인데, 최소 신장 트리를 활용한 방법은 최대 연결 수를 증가시켜도 실행 시간의 변화가 없지만, 제안된 방법은 계속 증가함을 확인할 수 있다. 또한 제안된 방법은 한 노드 당 최대 연결의 수를 크게 하면, 실행 시간의 증가율이 높아져, 20%인 경우에는 실행시간이 최소신장 트리를 사용한 연결보다 약 90.
- (그림 5)의 (b)는 한 선분 당 최대 연결 수를 변경하며 선분 연결을 생성한 실험의 결과인데, 최소 신장 트리를 활용한 방법은 최대 연결 수를 증가시켜도 실행 시간의 변화가 없지만, 제안된 방법은 계속 증가함을 확인할 수 있다. 또한 제안된 방법은 한 노드 당 최대 연결의 수를 크게 하면, 실행 시간의 증가율이 높아져, 20%인 경우에는 실행시간이 최소신장 트리를 사용한 연결보다 약 90.6%의 증가이지만, 완전연결(100%)인 경우에는 약 276%가 증가함을 보인다. 모든 입력 환경에 대하여 제안된 방법을 이용한 선분 연결의 생성을 위한 실행 시간은 최소 신장 트리를 이용한 방법에 비해 평균 192% 증가되었다.
- 6%의 증가이지만, 완전연결(100%)인 경우에는 약 276%가 증가함을 보인다. 모든 입력 환경에 대하여 제안된 방법을 이용한 선분 연결의 생성을 위한 실행 시간은 최소 신장 트리를 이용한 방법에 비해 평균 192% 증가되었다.
- 2%임을 보인다. 모든 입력 환경에 대하여 제안된 방법의 후처리 작업을 통한 길이절감율은 평균 약 6.4%이다. 그러나 후처리 작업을 위해서는 추가적인 계산 작업을 수행해야 하므로 실행시간의 증가가 발생하는데, 입력 선분의 수가 1000이고 한 선분 당 최대연결 수가 40%인 환경의 실험에서 최대 0.
- 4%이다. 그러나 후처리 작업을 위해서는 추가적인 계산 작업을 수행해야 하므로 실행시간의 증가가 발생하는데, 입력 선분의 수가 1000이고 한 선분 당 최대연결 수가 40%인 환경의 실험에서 최대 0.22%의 추가 실행 시간이 요구되었고, 전체적으로는 평균 0.014%의 실행시간이 추가되었다.
- 따라서 입력 선분 연결 문제는 네트워크에서의 라우팅, ad-hoc 네트워크, 회로 설계, 항로 결정, 도로 연결 등에 적용될 수 있다. 제안된 방법은 비교 대상인 선분 최소 신장 트리에 비해 입력 선분의 연결생성 시간을 증가시켰지만, 그 연결 길이를 감소시켰다.
- 이 그래프에서 불필요한 연결을 삭제하고 후처리 작업을 통해 좀 더 연결 비용을 절감한다. 실험에서, 본 논문에서 제안된 방법은 유사 연구인 입력 선분의 연결 문제를 최소 신장 트리를 이용하여 해결한 선분 최소 신장 트리 방법[7]과 비교하여 입력 선분을 연결하는 연결선을 생성하는 시간은 192.0% 증가시켰으나, 선분 연결선의 길이는 평균 6.8% 감소시켰다. 이는 본 논문에서 제안하는 방법이 연결 생성 시간보다는 연결 비용의 절감이 더 중요한 응용에 잘 적용될 수 있음을 보인다.
후속연구
- 이들 중에서 최소 비용의 트리가 최소 스타이너 트리(Steiner Minimum Tree)이며, 이 문제는 NP-Complete 문제에 포함되는 것으로 알려져 있다[1-3]. 최소 스타이너 트리는 다항적 시간(polynomial time) 내에서 최적화된 해를 제공하는 최소 신장 트리보다 연결 비용을 줄일 수 있으나, 다항적 시간 내에 문제에 대한 해를 구할 수 없으므로, 실제 활용을 위해서는 적절한 휴리스틱을 통한 근사 최소 스타이너 트리를 생성하여 적용해야 할 것이다.
- 최소 신장 트리 생성은 Prim의 알고리즘을 변형하였는데, 이 알고리즘은 주어진 노드들과 이들 사이의 입력 연결선을 이용하여 최소 비용의 신장 트리를 생성할 수 있다. 본 논문에서 제안하는 문제는 입력 선분들을 최소 비용으로 연결하는 것이므로 최소 신장 트리생성 알고리즘을 바로 응용할 수 없고 적절한 변환이 필요하다. 즉 입력 선분을 노드로, 선분 연결을 연결선으로 변환한 후에 그 연결선의 길이를 가중치로 이용하여 순수한 Prim의 알고리즘을 적용한다.
- 따라서 본 논문에서 제안하는 방법의 실행 시간은 O(E2logE) 이다. 그러나 입력 선분과 입력 연결에 대해 생성되는 최소 신장 트리의 토폴로지가 스타 형일 가능성은 적으므로, 이보다는 빠른 시간 내에 실행이 가능할 것이다.
- 8% 감소시켰다. 이는 본 논문에서 제안하는 방법이 연결 생성 시간보다는 연결 비용의 절감이 더 중요한 응용에 잘 적용될 수 있음을 보인다.
- 향 후 연구는, 매우 많은 입력 선분들을 연결해야 하는 응용에서, 신속하게 연결 방법을 찾기 위해 다항 적 시간 근사구조 (Polynomial Time Approximation Scheme)의 적용에 관하여 연구할 예정이다[9]. 이 다항 적 시간 구조는 NP 문제와 같은 현실 세계에서 계산하기 힘든 문제에 대하여, 그 문제를 작은 기본 단위로 세분화시키고, 이를 Bruteforce 방법으로 해결한 후, 그 하위 단계의 결과를 상위 단계에서 통합하여 문제를 해결하는 방법이다.
- 이 다항 적 시간 구조는 NP 문제와 같은 현실 세계에서 계산하기 힘든 문제에 대하여, 그 문제를 작은 기본 단위로 세분화시키고, 이를 Bruteforce 방법으로 해결한 후, 그 하위 단계의 결과를 상위 단계에서 통합하여 문제를 해결하는 방법이다. 이러한 시도를 통해 현실 세계에서 당면할 수 있는 매우 많은 수의 통신선 연결과 같은 문제에 대하여 스타이너 트리를 이용한 연결 비용의 절감뿐만 아니라, 연결 생성의 시간적 측면에서, 좀 더 개선된 방법을 제안할 수 있을 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.