본 논문에서는 하노이의 탑 (Tower of Hanoi; ToH) 문제를 확장한 문제들을 소개하고, ToH 문제의 상태 공간을 그래프로 표현하기 위한 새로운 방안을 제시하고자 한다. 확장한 문제들로는 기둥의 수를 늘린 경우, 디스크 스택의 수를 늘린 경우, 그리고 일반 상태 간의 이동에 대한 세 가지를 소개하고, 다른 변종 문제들을 소개하고자 한다. 우리가 본 논문에서 제시한 새로운 표현 방안은 기존의 하노이 그래프 표현에 대해 확장된 방식의 그래프 표현을 제시하는 것이다. 제안된 표현에서는 각 디스크마다 하나의 직교좌표를 부여해 줌으로써 링크의 표시와 상태의 변화가 디스크가 어느 기둥에 배치되어 있는가와 시각적으로 일치된 시각화를 가능하게 해 준다. 제안된 표현을 기존의 하노이 그래프와 비교해 보면, 제안된 표현에서 디스크를 옮길 수 없는 링크를 제거하면 기존의 하노이 그래프와 isomorphic하다. 따라서, 제안된 표현은 기존의 하노이 그래프를 확장하여 표현력을 고도화한 것임을 알 수 있다. 제안된 표현에 대한 독자들의 이해를 돕기 위해, 우리는 본 논문에서 디스크의 개수가 2와 3인 경우에 대한 제안된 표현의 시각화 예를 제시하였다.
본 논문에서는 하노이의 탑 (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 ...
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.
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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
학술적으로 볼 때, 하노이의 탑 문제는 컴퓨터 게임에 자주 등장할 정도로 대중적으로 잘 알려져 있으나, 실제로는 다양한 확장과 변형이 있으며 확장된 문제들은 매우 어렵기로 악명 높음에도 불구하고 [4,5], 심지어 대부분의 전산학자들도 하노이의 탑 문제에 대해 깊이 알지 못하고, 자료 구조 관련 서적에 있는 내용 정도인 재귀 호출을 익히기 위한 단순한 문제로만 알고 있는 경우가 많다. 따라서 우리는 본논문에서 하노이의 탑 문제에 대한 관심사의 저변 확충을 위해 하노이의 탑 문제를 확장한 문제들 중 세가지 종류를 제시하고, 하노이의 탑 문제는 아니지만 비슷한 문제들에 대해서도 소개하고자 한다.
그림 3은 세 개의 기둥과 두 개의 스택을 가진 하노이의 탑 문제이다. 목표는 원래 문제의 조건들을 그대로 지키면서 양 쪽의 스택을 가운 데로 모으는 것이다.
본 논문에서는 기존의 하노이의 탑 문제와 관련되어 상태를 표시하는 방법으로 주로 사용되어 왔던 시에르핀스키 그래프의 형태와 다른 새로운 형태의 시각화 방안을 제안하였다. 기존의 시각화 방안은 p=3인 경우가 시에르핀스키 그래프와 유사하다는 점 때문에 이후 p>3인 일반적인 경우의 문제의 경우에도 시에르핀스키와 관련된 시각화 방법으로만 접근해 왔다.
본 논문에서는 디스크의 개수 n이 증가함에 따라서 표시되는 차원이 증가하는 형태로 하노이의 탑의 상태를 표현하고자 한다. 기존의 시에르핀스키 형태에 맞추어 시각화하려는 방법에서 탈피하여 하노이 탑의 문제를 접근할 수 있게 하고자 한다.
가설 설정
(2) 어떠한 경우에도, 큰 디스크는 작은 디스크 위에 오면 안된다. 이를 흔히 디바인 룰(divine rule)이라 부른다.
제안 방법
본 논문에서는 디스크의 개수 n이 증가함에 따라서 표시되는 차원이 증가하는 형태로 하노이의 탑의 상태를 표현하고자 한다. 기존의 시에르핀스키 형태에 맞추어 시각화하려는 방법에서 탈피하여 하노이 탑의 문제를 접근할 수 있게 하고자 한다.
ski graph)와 유사하나 실제로는 다소 다른 점이 있으며, 하노이의 탑 문제를 다방면으로 이해하기 위해서는 다른 표현이 가능할 수도 있음에도, 하노이의 탑 문제를 표현하는 거의 유일한 방법으로 사용되어 왔다. 따라서, 우리는 본 논문에서 하노이 그래프를 확장하여 하노이의 탑 문제를 표현한 방식 을 제시하고, 하노이 그래프와의 장단점을 정성적으로 분석하였다.
각 기둥에 대해 놓여 있는 디스크의 번호를 표시하는 방법을 사용하기도 하지만 작은 디스크가 큰 디스크 위에 항상 놓인다는 가정을 이용하면 큰 디스크부터 현재 놓여 있는 기둥의 번호를 순서대로 적는 방법으로 상태를 구분할 수 있다. 본 논문에서는 사용하는 기둥에 A, B, C 순서로 알파벳 문자를 부여하여 상태를 구분하는 방법을 사용할 것이다. 이렇게 하면 상태는 디스크의 개수 n에 따라 n개의 알파벳 문자로 표현할 수 있으며 사용할 수 있는 알파벳의 종류는 기둥의 개수 p에 따라 결정된다.
그러나 하노이 그래프는 n의 크기와 p의 크기에 따라 상태가 정해지는 형태로 일반적인 (n, p)에 대해서는 시에르핀스키로 해석하는 것이 무리가 있다. 제안된 방법은 디스크의 개수에 따라 차원이 증가하고 기둥의 수에 따라 축 방향으로 개수만 증가하는 형태의 하노이 그래프에 대해 제안하고 n이 2인경우와 3인 경우에 시각화 하는 방법을 제시하였다. n이 4이상인 경우에 대한 시각화는 4차원의 그래프이므로 이를 다시 2차원이나 3차원의 형태로 표현하는 방법을 고려할 수 있다.
이론/모형
Hinz[11]의정의에 따르면, 이는 디스크들이 한 쪽 기둥에만 쌓여있는 경우는 완전 상태(perfect state)이며, 디스크들이 기존의 조건을 지키면서 여러 기둥에 쌓여있는 경우는 정규 상태(regular state)로 규정한다. 이 문제는 저명한 인지심리학자이며 노벨상 수상자인 Simon[2] 의 연구에 사용되었다. 그림 5는 이러한 세 개의 기둥을 가지는 하노이의 탑 문제의 정규 상태 문제를 Psychology Experiment Building Language (PEBL)로구현한 것이다.
이 문제를 컴퓨터 알고리즘으로 푸는 경우는 세개의 기둥을 가지는 경우는 Hinz[11]에 의해서 비결 정적 알고리즘(non-deterministic algorithm)이 주어졌고, Romik[13]이 이에 오토마타를 추가하여 결정적 알고리즘(deterministic algorithm)으로 해결하었다.
후속연구
향후 연구 방향으로는 런던 탑 문제(ToL)나 유사한 문제에 대한 시각화를 고려해 볼 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
하노이의 탑 문제는 무엇인가?
하노이의 탑 문제는 프랑스의 수학자 뤼카(É. Lucas)가 발표한 퍼즐[1]로, 인도 베나라스의 한 사원에 있는 3 개의 기둥과 그 중 하나의 기둥에 크기 순서대로 쌓여있는 64 개의 디스크들에 대한 이야기에서 유래한 문제이다. 이 64 개의 디스크은 가장 작은 것이 위에 있고 크기 순서대로 쌓여있는 데, 이들을한 번에 한 개씩 옮기되, 큰 디스크가 작은 디스크 위에 오지 못하도록 정해진 규칙에 따라 전부 옮기면 세상은 종말을 맞이하게 된다고 전해진다.
하노이의 탑 문제가 게임에 사용된 예로 무엇이 있는가?
이러한 하노이의 탑 문제는 자료 구조 및 알고리 즘에서 재귀 호출을 시연하기 위해 많이 쓰이며, 퍼즐을 기반으로 한 컴퓨터 게임의 소재로도 많이 쓰인다. 예를 들어, 최근 닌텐도 DS 라이트 (Nintendo DS Lite) 기반에서 퍼즐풀이와 애니메이션 스토리 텔링을 통합한 새로운 장르의 게임으로 인기를 끈 “레이튼 교수와 이상한 마을”에서도 하노이의 탑이 등장한 바 있다. 또한 하노이의 탑을 실제로 가지고 놀아 보게 함으로써 아동 교육학이나 정신분석학에서 활용되기도 한다[2].
하노이의 탑 문제는 어떤 분야에서 많이 쓰이는가?
이러한 하노이의 탑 문제는 자료 구조 및 알고리 즘에서 재귀 호출을 시연하기 위해 많이 쓰이며, 퍼즐을 기반으로 한 컴퓨터 게임의 소재로도 많이 쓰인다. 예를 들어, 최근 닌텐도 DS 라이트 (Nintendo DS Lite) 기반에서 퍼즐풀이와 애니메이션 스토리 텔링을 통합한 새로운 장르의 게임으로 인기를 끈 “레이튼 교수와 이상한 마을”에서도 하노이의 탑이 등장한 바 있다.
참고문헌 (15)
E. Lucas. "Nouveaux Jeux Scientifiques de M. Edouard Lucas," La Nature. 17. 2e semestre. pp. 301-303, 1889.
A. Newell, H. A. Simon, Human problem solving, Englewood Cliffs, NJ: Prentice-Hall, 1972.
M. Faloutsos, P. Faloutsos and C. Faloutsos, "On power-law relationships of the Internet topology," ACM SIGCOMM Computer Communication Review, 29(4), 1999.
J.-P. Bode, A. M. Hinz, "Results and Open Problems on the Tower of Hanoi," Congressus Numerantium, 139, pp. 113-122, 1999.
A. M. Hinz, A. Kostav, F. Kneissl, F. Surer, A. Danek "A Mathematical Model and a Computer Tool for the Tower of Hanoi and Tower of London Puzzles," Information Sciences, 179, pp. 2934-2947, 2009.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.