[국내논문]들로네 삼각망과 최소신장트리를 결합한 효율적인 유클리드 스타이너 최소트리 생성 Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree원문보기
스타이너 트리의 생성은 NP-Complete 영역에 속하므로, 이것을 위한 휴리스틱들은, 다수의 입력 노드에 대해서 많은 시간과 계산을 요구한다. 본 논문에서는 많은 입력노드에 대해, 들로네 삼각망과 Prim의 최소신장트리를 결합한 효과적인 유클리드 스타이너 최소트리 구성방법을 제안한다. 이 방법은 Prim의 최소신장트리와 최소신장트리기반 스타이너 트리와 각각 비교 분석되었다. 제안된 방법은 30,000개의 입력노드에 대해 최소신장트리에 비해 연결 길이는 2.1% 감소, 실행시간은 138.2% 증가하였고, 최소신장트리기반 스타이너최소트리에 비해 실행시간 18.9% 감소, 연결 길이 0.013% 감소의 실험결과를 보였다. 따라서 본 연구의 제안방법은 실행시간이 주요 요인이 되지 않는 환경에서 연결 길이를 단축해야 할 응용에 잘 적용될 수 있을 것이다.
스타이너 트리의 생성은 NP-Complete 영역에 속하므로, 이것을 위한 휴리스틱들은, 다수의 입력 노드에 대해서 많은 시간과 계산을 요구한다. 본 논문에서는 많은 입력노드에 대해, 들로네 삼각망과 Prim의 최소신장트리를 결합한 효과적인 유클리드 스타이너 최소트리 구성방법을 제안한다. 이 방법은 Prim의 최소신장트리와 최소신장트리기반 스타이너 트리와 각각 비교 분석되었다. 제안된 방법은 30,000개의 입력노드에 대해 최소신장트리에 비해 연결 길이는 2.1% 감소, 실행시간은 138.2% 증가하였고, 최소신장트리기반 스타이너최소트리에 비해 실행시간 18.9% 감소, 연결 길이 0.013% 감소의 실험결과를 보였다. 따라서 본 연구의 제안방법은 실행시간이 주요 요인이 되지 않는 환경에서 연결 길이를 단축해야 할 응용에 잘 적용될 수 있을 것이다.
As Steiner minimum tree building belongs to NP-Complete problem domain, heuristics for the problem ask for immense amount execution time and computations in numerous inputs. In this paper, we propose an efficient mechanism of euclidean Steiner minimum tree construction for numerous inputs using comb...
As Steiner minimum tree building belongs to NP-Complete problem domain, heuristics for the problem ask for immense amount execution time and computations in numerous inputs. In this paper, we propose an efficient mechanism of euclidean Steiner minimum tree construction for numerous inputs using combination of Delaunay triangulation and Prim's minimum spanning tree algorithm. Trees built by proposed mechanism are compared respectively with the Prim's minimum spanning tree and minimums spanning tree based Steiner minimum tree. For 30,000 input nodes, Steiner minimum tree by proposed mechanism shows about 2.1% tree length less and 138.2% execution time more than minimum spanning tree, and does about 0.013% tree length less and 18.9% execution time less than minimum spanning tree based Steiner minimum tree in experimental results. Therefore the proposed mechanism can work moderately well to many useful applications where execution time is not critical but reduction of tree length is a key factor.
As Steiner minimum tree building belongs to NP-Complete problem domain, heuristics for the problem ask for immense amount execution time and computations in numerous inputs. In this paper, we propose an efficient mechanism of euclidean Steiner minimum tree construction for numerous inputs using combination of Delaunay triangulation and Prim's minimum spanning tree algorithm. Trees built by proposed mechanism are compared respectively with the Prim's minimum spanning tree and minimums spanning tree based Steiner minimum tree. For 30,000 input nodes, Steiner minimum tree by proposed mechanism shows about 2.1% tree length less and 138.2% execution time more than minimum spanning tree, and does about 0.013% tree length less and 18.9% execution time less than minimum spanning tree based Steiner minimum tree in experimental results. Therefore the proposed mechanism can work moderately well to many useful applications where execution time is not critical but reduction of tree length is a key factor.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 많은 입력에 대하여 들로네 삼각망과 최소신장트리를 결합하여, 기존의 유클리드 스타이너 최소트리 생성방법에 비해 짧은 시간 내에 효과적인 연결하는 방법을 제안한다. 이 방법은 네트워크 라우팅, 전력망, 가스망의 설계, 도로 및 선박 및 민간 항공기 항로의 설계 및 운용 등에 활용될 수 있다.
본 논문에서 제안하는 방법은 2차원 평면상에 산재한 다수의 입력 노드들을 스타이너 트리를 이용하여 최소 비용 또는 최단 길이로 연결하는 문제를 해결하기 위함이다. 주어진 입력노드와 입력 연결선이 있을 때 입력 연결선의 부분집합을 이용하여 입력노드들을 모두 연결하는 최소 비용의 트리가 최소신장트리이다.
Seo 등은 그래프 축소 규칙을 이용하여, 최적 해에 필요하지 않은 노드들과 연결들을 제거 후, Prim의 알고리즘을 조합한 max-min ant colony optimization 방법을 적용하였다[7]. 이 연구를 통해 비 방향 스타이너 트리 문제를 해결하고자 시도하였다. S.
실험에 사용된 인자는 입력 노드 수이고, 관찰 결과는 Prim의 최소신장트리를 이용한 방법[1], 최소신장트리를 이용한 스타이너 최소트리 방법[12], 그리고 본 논문에서 제안 하는 들로네삼각망과 최소신장트리를 결합한 방법에 의해 생성되는 트리의 길이 및 실행시간이다. 실험의 목적은 본 논문에서 제안하는 방법이, 다항 적 시간 내에서 최적의 네트워크를 생성하는 최소신장트리 방법은 물론 기존 스타이너 최소트리보다 트리 길이를 단축함과 동시에 실행시간을 개선할 수있음을 검증하는 것이다. 즉, 제안된 방법이 최소신장트리의 실행시간보다는 더 요구되지만, 트리 길이를 단축할 수 있고, 기존의 단축된 길이를 얻었던 스타이너최소트리 생성방법보다도 길이의 절감과 동시에 실행시간의 감소를 보이고자 한다.
제안 방법
Lee 등은 스타이너 트리를 이용하여 멀티캐스트 라우팅 문제를 해결하려는 연구를 하였다[8]. 이 연구에서 멀티캐스팅 문제와 순회 판매원 문제의 차이를 분석하여, 기존의 개미 시스템(Ant System)을 변경한 엘리트 에이전트에 의한 개미 멀티캐스트 라우팅 모델과 멀티캐스트 통신에서의 서비스 품질을 처리할 수 있는 다중 제약 멀티 캐스트 처리 알고리즘을 발표하였다[8]. 스타이너 트리를 활용하여 센서 네트워크의 효율적인 라우팅을 위한 센서노드들을 상호 연결을 위한 최적의 배치 문제를 해결하려 하였으며, 센서 네트워크에서의 물리적인 특성으로, 일반 그래프 노드 연결 문제의 범위를 축소하여 실행시간과 최적 치에 대한 근사비율을 발표되었다[9].
P2P1과 P1P3의 선분의 길이 합보다 후보 스타이너 포인트와 원래 세 정점과의 거리의 합이 작다면 S는 최종스타이너 포인트로 결정되고, 그렇지 않은 경우는 S 를 버리게 된다. 이렇게 하여 트리를 구성하는 연속적인 모든 경로에 대하여 최종스타이너 포인트를 구하고, 스타이너 포인트와 정점과 연결하고, 기존의 두 연속경로들을 버려서 스타 이너 그래프를 생성한다. 스타이너그래프를 입력으로 최소신장트리를 구하면 원래 트리의 길이보다 같거나 작게 된다.
실험에 사용된 인자는 입력 노드 수이고, 관찰 결과는 Prim의 최소신장트리를 이용한 방법[1], 최소신장트리를 이용한 스타이너 최소트리 방법[12], 그리고 본 논문에서 제안 하는 들로네삼각망과 최소신장트리를 결합한 방법에 의해 생성되는 트리의 길이 및 실행시간이다. 실험의 목적은 본 논문에서 제안하는 방법이, 다항 적 시간 내에서 최적의 네트워크를 생성하는 최소신장트리 방법은 물론 기존 스타이너 최소트리보다 트리 길이를 단축함과 동시에 실행시간을 개선할 수있음을 검증하는 것이다.
실험을 위해 무작위로 생성된 입력 노드의 수는 5000, 10000, 15000, 20000, 25000, 30000개이다. 최소신장트리 방법은 Prim의 최소신장트리 생성 알고리즘을 기반으로 생성되었으며, 기존의 스타이너 최소트리는 1차 최소신장트리에서 연속적인 경로 상에 있는 세 입력노드들을 활용해서 최종 스타이너 포인트를 생성하여 스타이너그래프를 구성하고 이것의 노드들과 선분을 입력으로 2차 최소신장트리를 생성하여, 최종적으로 불필요한 스타이너 포인트들과 선분들을 제거하여 완성하였다. 비교 방법들과 제안된 방법은 Intel 프로세서와 4기가 램의 32비트 윈도우즈 환경에서 Java로 구현하여 비교되었다.
대상 데이터
즉, 제안된 방법이 최소신장트리의 실행시간보다는 더 요구되지만, 트리 길이를 단축할 수 있고, 기존의 단축된 길이를 얻었던 스타이너최소트리 생성방법보다도 길이의 절감과 동시에 실행시간의 감소를 보이고자 한다. 실험을 위해 무작위로 생성된 입력 노드의 수는 5000, 10000, 15000, 20000, 25000, 30000개이다. 최소신장트리 방법은 Prim의 최소신장트리 생성 알고리즘을 기반으로 생성되었으며, 기존의 스타이너 최소트리는 1차 최소신장트리에서 연속적인 경로 상에 있는 세 입력노드들을 활용해서 최종 스타이너 포인트를 생성하여 스타이너그래프를 구성하고 이것의 노드들과 선분을 입력으로 2차 최소신장트리를 생성하여, 최종적으로 불필요한 스타이너 포인트들과 선분들을 제거하여 완성하였다.
데이터처리
최소신장트리 방법은 Prim의 최소신장트리 생성 알고리즘을 기반으로 생성되었으며, 기존의 스타이너 최소트리는 1차 최소신장트리에서 연속적인 경로 상에 있는 세 입력노드들을 활용해서 최종 스타이너 포인트를 생성하여 스타이너그래프를 구성하고 이것의 노드들과 선분을 입력으로 2차 최소신장트리를 생성하여, 최종적으로 불필요한 스타이너 포인트들과 선분들을 제거하여 완성하였다. 비교 방법들과 제안된 방법은 Intel 프로세서와 4기가 램의 32비트 윈도우즈 환경에서 Java로 구현하여 비교되었다.
이론/모형
이 삼각망 에는 현재 3개의 중첩되지 않은 삼각형이 존재한다. 본 논문에서 삼각망의 구성은 incremental 방법을 적용하였다. 즉, 그림 2에서 나타난 것 같이 정점 4가 새로 입력되었을 때, 그림 1에 존재하는 삼각망의 모든 삼각형들의 외접원을 생성하고, 이 외접원 중에서 정점 4를 포함하는 외접원을 선택한다.
성능/효과
이 방법의 경우 고려되는 두 연속경로를 구성하는 세 정점으로 생성되는 삼각형의 모양이 정삼각형과 유사할수록 최종스타 이너 포인트가 생성될 확률이 높다. 따라서 들로네 삼각망 기반의 최소신장트리가 단순 최소신장트리와 비교했을 때, 트리 길이는 같지만, 생성되는 토폴로지가 정삼각형에 좀 더 유사하므로 본 논문에서 제안하는 방법이 기존의 스타이너 최소트리 생성 방식에 비해 길이 단축이 가능하다.
그러나 동일한 길이라 할지라도 모든 경우에 두 개의 트리 토폴로지는 같지 않을 수 있다. 들로네 삼각망의 특징이 구성하는 삼각형이 정삼각형과 최대한 유사한 형태의 삼각형으로 구성된 삼각망을 형성하므로 유효한 스타이너 포인트를 생성할 확률이 높으므로, 들로네 삼각망을 활용하는 제안 방법이 트리길이 절감 측면에서 기존의 단순 방식보다 유리하다고 볼수 있다. 그림 12는 제안된 방법으로 생성된 유클리드 스타이너 최소트리의 모습이다.
실험의 목적은 본 논문에서 제안하는 방법이, 다항 적 시간 내에서 최적의 네트워크를 생성하는 최소신장트리 방법은 물론 기존 스타이너 최소트리보다 트리 길이를 단축함과 동시에 실행시간을 개선할 수있음을 검증하는 것이다. 즉, 제안된 방법이 최소신장트리의 실행시간보다는 더 요구되지만, 트리 길이를 단축할 수 있고, 기존의 단축된 길이를 얻었던 스타이너최소트리 생성방법보다도 길이의 절감과 동시에 실행시간의 감소를 보이고자 한다. 실험을 위해 무작위로 생성된 입력 노드의 수는 5000, 10000, 15000, 20000, 25000, 30000개이다.
Steiner)에 의해 생성된 트리의 길이에 관한 결과이다. 입력 노드의 수가 증가할수록 모든 방법의 트리의 길이는 증가하고, 제안된 방법은 최소신장트리와의 비교하여 평균 2.05%의 트리 길이 절감 율을 보였으며, 기존 스타이너 최소트리 생성방법에 비교해서도 평균 0.01%의 길이 감소율을 보였다. 이는 새로 제안된 방법이 길이 절감 율에서 최소신장트리는 물론 기존 스타이너최소트리 방법에 비해서 우수함을 보인다고 판단할 수 있다.
01%의 길이 감소율을 보였다. 이는 새로 제안된 방법이 길이 절감 율에서 최소신장트리는 물론 기존 스타이너최소트리 방법에 비해서 우수함을 보인다고 판단할 수 있다.
그림 14는 입력 노드 수에 따른, 각 트리 생성 소요시간을 나타낸다. 동일한 입력 노드 수에 대하여 기존 스타이너 최소 트리 방법이 가장 많은 시간을 필요하였고, 제안된 방법이 그 다음을 요구하며 최소신장트리 방법이 가장 적은 생성시간이 소비된다. 본 논문에서 제안된 방법은 최소신장트리 방법에 비해 평균 138.
동일한 입력 노드 수에 대하여 기존 스타이너 최소 트리 방법이 가장 많은 시간을 필요하였고, 제안된 방법이 그 다음을 요구하며 최소신장트리 방법이 가장 적은 생성시간이 소비된다. 본 논문에서 제안된 방법은 최소신장트리 방법에 비해 평균 138.21%의 추가시간을 요구했으나, 기존의 스타 이너 최소트리 생성 방법에 비해서는 평균 18.88%의 시간절감을 보였다.
따라서 본 논문에서 제안된 방법은 실행시간이 중요한 요인이 되지 않는 환경이나 응용에서, 연결비용 또는 트리길이가 중요한 요인이 되는 경우, 기존의 스타이너 트리 생성에 비해 비교적 빠른 실행시간으로 우수한 트리를 생성할 수 있다.
본 논문에서 제안하는 들로네삼각망과 최소신장트리를 결합한 유클리드 스타이너 최소트리는 많은 입력노드들로 구성된 응용에서, 효과적으로 서로 연결하고 통신할 수 있는 방법을 제공할 수 있다. 이 방법은 기존의 스타이너 최소시간에 비해 평균 18.88%의 실행시간의 절감과 약간의 트리길이 절감을 보였다. 또한 단순 유클리드 최소신장트리와 비교해서는 평균 2.
88%의 실행시간의 절감과 약간의 트리길이 절감을 보였다. 또한 단순 유클리드 최소신장트리와 비교해서는 평균 2.05%의 트리 길이의 절감을 보였다. 이는 들로네 삼각망이 정삼각형 근사 형태의 삼각형으로 구성하고, 이는 최종 스타이너 포인트 생성에 유리한 것으로 판단된다.
후속연구
본 논문에서 제안하는 들로네삼각망과 최소신장트리를 결합한 유클리드 스타이너 최소트리는 많은 입력노드들로 구성된 응용에서, 효과적으로 서로 연결하고 통신할 수 있는 방법을 제공할 수 있다. 이 방법은 기존의 스타이너 최소시간에 비해 평균 18.
또한 이를 통해서 완전연결을 하지 않고도 유클리드 연결이 가능함으로 보인다. 따라서 제안된 방법은 트리의 길이를 감소시키는 것이 매우 중요한 응용에서 상대적으로 빠른 결과를 요구하는 목적에 잘 부합될 수 있을 것이다.
향 후 연구는, 들로네 삼각망과 관련 있는 보로노이 다이어그램(Voronoi Diagram)을 활용하여 스타이너 최소트리를 빠른 시간에 생성하는 방법에 대한 연구와 본 논문에서 제안한 방법을 가중치를 갖는 입력 노드의 적용하는 방법에 관한 것이다. 이러한 연구를 통해 본 논문에서 제안하는 방법보다 개선된 방법을 제시할 수 있고, 또한 다양한 응용에 적용 가능할 수 있을 것이다.
향 후 연구는, 들로네 삼각망과 관련 있는 보로노이 다이어그램(Voronoi Diagram)을 활용하여 스타이너 최소트리를 빠른 시간에 생성하는 방법에 대한 연구와 본 논문에서 제안한 방법을 가중치를 갖는 입력 노드의 적용하는 방법에 관한 것이다. 이러한 연구를 통해 본 논문에서 제안하는 방법보다 개선된 방법을 제시할 수 있고, 또한 다양한 응용에 적용 가능할 수 있을 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
다항적 문제 영역에서 통신 네트워크 구성을 위한 최적의 트리 생성 방법은?
다항적(Polynomial) 문제 영역에서 통신 네트워크 구성을 위한 최적의 트리 생성방법은 최소신장트리(Minimum Spanning Tree)를 활용하는 것이다[1]. 비-다항 적 (Non-Polynomial) 문제 영역에서, 입력노드가 아닌 스타이너 포인트의 활용을 통한 최소 신장 트리에 비해 더 단축된 길이의 네트워크를 생성하는 것이 스타이너 최소트리 (Steiner Minimum Tree)이다[2,3].
스타이너 최소트리란 무엇인가?
다항적(Polynomial) 문제 영역에서 통신 네트워크 구성을 위한 최적의 트리 생성방법은 최소신장트리(Minimum Spanning Tree)를 활용하는 것이다[1]. 비-다항 적 (Non-Polynomial) 문제 영역에서, 입력노드가 아닌 스타이너 포인트의 활용을 통한 최소 신장 트리에 비해 더 단축된 길이의 네트워크를 생성하는 것이 스타이너 최소트리 (Steiner Minimum Tree)이다[2,3]. 비-다항 적 문제 영역인 스타이너 최소트리의 생성 및 활용을 위해서는 근사 최적 해를 위한 휴리스틱을 개발해야 한다.
스타이너 최소트리의 휴리스틱 개발 시 입력 노드 수가 많아지면 어떻게 되는가?
비-다항 적 문제 영역인 스타이너 최소트리의 생성 및 활용을 위해서는 근사 최적 해를 위한 휴리스틱을 개발해야 한다. 비록 휴리스틱이라 할지라도 많은 수의 입력 노드들에 대해서는 막대한 계산과 실행시간이 필요하다.
참고문헌 (12)
T.H. Cormen, C.E Leiserson, R.L. Rivest and C. Stein, "Introduction to Algorithms," 2nd Ed., THe MIT Press, pp.561-579, 2001.
B. Bell, "Steiner Minimal Tree Problem", http://www.css.taylor.edu/-bbell/steiner/, January 1999.
J. Kim, M. Cardei, I. Cardei and X. Jia, "A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem," Algorithmica, Vol.42, pp.109-120, 2005.
M. Seo, D. Kim, "A Max-Min Ant Colony Optimization for Undirected Steiner Tree Problem in Graphs", Korean Management Science Review, Vol.26, No.1, pp.65-76, 2009.
S. Lee, "Elite Ant System for Solving Multicast Routing Problem," Journal of the Korea Society of Computer and Information, Vol.13, No.3, pp.147-152, 2008.
J. Kim, "The application of the combinatorial schemes for the layout design of Sensor Networks," Journal of the Institute of Electronics Engineers of Korea TC, Vol.45, No.7, pp.9-16, 2008.
G. Leach, "ImprovingWorst-Case Optimal Delaunay Triangulation Algorithms," 4th Canadian Conference on Computational Geometry, June 1992.
Y. Sung, G. Kim, "Delaunay Triangulation based Fingerprint Matching Algorithm using Quality Estimation and Minutiae Classification," Journal of Korea Multimedia Society, Vol.13, No.4, pp. 547-559, 2010.
I. Kim, "Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS," Journal of the Korea Society of Computer and Information, Vol. 17, No.7, pp.87-95, 2011.
이 논문을 인용한 문헌
저자의 다른 논문 :
활용도 분석정보
상세보기
다운로드
내보내기
활용도 Top5 논문
해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다. 더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.