수레바퀴 살 퍼즐에 관한 전정 알고리즘 (Pruning Algorithm for Spokes Puzzle)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 24권 / 4호 / 89 ~ 97페이지
· 저자명 : 이상운

초록

수레바퀴 중심축(허브, 정점)이 요구하는 살(간선)을 교차없이 연결하여 모든 중심축이 연결된 망을 형성하는수레바퀴 살 퍼즐 문제는 연구의 불모지라 할 수 있다. 이 문제에 대해서는 지수시간이 소요되는 전수 탐색법이나 분기한정 법조차도 제시된 알고리즘이 없는 실정이다. 본 논문은 주어진 SP에 대해 ×의 교차 대각선을 가진 격자 그래프를 작도하고, 잉여 간선을 전정(삭제)하는 알고리즘을 제안하였다. 제안된 알고리즘은 간선 수가 허브 요구량과 일치하는허브의 간선을 선택하고 이와 교차하는 간선을 삭제하는 단순한 방법이다. 만약 허브 요구량을 충족하는 간선을 가진허브가 존재하지 않으면 여유 량이 최대인 허브의 간선을 우선하여 삭제(전정)하는 전략을 채택하였다. 제안된 알고리즘을 20개의 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 시행착오 회수를 최소로 하는 해를 구할 수 있음을보였다.

영어초록

The problem of the spokes puzzle(SP), which connects the spokes(edges) required by the wheel axis (hub, vertex) without intersection to form a network in which all the hubs are connected, can be said to be a wasteland of research. For this problem, there is no algorithm that presents a brute-force search or branch-and-bound method that takes exponential time. This paper proposes an algorithm to plot a lattice graph with cross-diagonal lines of × for a given SP and to pruning(delete) the surplus edges(spokes). The proposed algorithm is a simple way to select an edge of a hub whose number of edges matches the hub requirement and delete the edge crossing it. If there is no hub with an edge that meets the hub requirement, a strategy was adopted to preferentially delete(pruning) the edge of the hub with the maximum amount of spare. As a result of applying the proposed algorithm to 20 benchmarking experimental data, it was shown that a solution that minimizes the number of trials and errors can be obtained for all problems.

참고자료

· 없음