하노이의 탑의 새로운 그래프 시각화에 대한 연구 (A Study on a Novel Graph Visualization for the Tower of Hanoi)

서지정보

· 발행기관 : 한국항행학회
· 수록지 정보 : 한국항행학회논문지 / 14권 / 6호 / 975 ~ 983페이지
· 저자명 : 조청운, 강대기

초록

본 논문에서는 하노이의 탑 (Tower of Hanoi; ToH) 문제를 확장한 문제들을 소개하고, ToH 문제의 상태 공간을 그래프로 표현하기 위한 새로운 방안을 제시하고자 한다. 확장한 문제들로는 기둥의 수를 늘린 경우, 디스크 스택의 수를 늘린 경우, 그리고 일반 상태 간의 이동에 대한 세 가지를 소개하고, 다른 변종 문제들을 소개하고자 한다. 우리가 본 논문에서 제시한 새로운 표현 방안은 기존의 하노이 그래프 표현에 대해 확장된 방식의 그래프 표현을 제시하는 것이다. 제안된 표현에서는 각 디스크마다 하나의 직교좌표를 부여해 줌으로써 링크의 표시와 상태의 변화가 디스크가 어느 기둥에 배치되어 있는가와 시각적으로 일치된 시각화를 가능하게 해 준다. 제안된 표현을 기존의 하노이 그래프와 비교해 보면, 제안된 표현에서 디스크를 옮길 수 없는 링크를 제거하면 기존의 하노이 그래프와 isomorphic하다. 따라서, 제안된 표현은 기존의 하노이 그래프를 확장하여 표현력을 고도화한 것임을 알 수 있다. 제안된 표현에 대한 독자들의 이해를 돕기 위해, 우리는 본 논문에서 디스크의 개수가 2와 3인 경우에 대한 제안된 표현의 시각화 예를 제시하였다.

영어초록

In this paper, we introduce extended problems of Tower of Hanoi (ToH) and propose a novel visualization method to express a state space of ToH. As for the extended problems, we introduce multi-peg ToH, multi-stack ToH, and regular state ToH. The novel visualization method in this paper is a natural extension of Hanoi graph visualization. In the proposed method, we assign one Cartesian coordinate point per each disk to provide an unified visualization that the marks on a link and the changes of a state should correspond with a peg position of a disk. Compared with Hanoi graph, the generated graph by the proposed method is isomorphic if we remove links of forbidden move, which indicates that our method is a generalization of Hanoi graph and thus is more expressive. To help the understanding of the readers, we show the generated graphs by our method when the number of disks is 2 and 3.

참고자료

· 없음