2025-11-12T21:19:10.850730

The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph

Mehiri
We introduce and study a new four-peg variant of the Tower of Hanoi problem under parity constraints. Two pegs are neutral and allow arbitrary disc placements, while the remaining two pegs are restricted to discs of a prescribed parity: one for even-labelled discs and the other for odd-labelled discs. Within this constrained setting, we investigate four canonical optimization objectives according to distinct target configurations and derive for each the exact number of moves required to optimally transfer the discs. We establish a coupled system of recursive relations governing the four optimal move functions and unfold them into higher-order recurrences and explicit closed forms. These formulas exhibit periodic growth patterns and reveal that all solutions grow exponentially, but at a significantly slower rate than the classical three-peg case. In particular, each optimal move sequence has an a half-exponential-like asymptotic order induced by the parity restriction. In addition, we define the associated parity-constrained Hanoi graph, whose vertices represent all feasible states and whose edges represent legal moves. We determine its order, degrees, connectivity, planarity, diameter, Hamiltonicity, clique number, and chromatic properties, and show that it lies strictly between the classical three- and four-peg Hanoi graphs via the inclusion relation.
academic

패리티 제약 4-기둥 하노이 타워 문제와 관련 그래프

기본 정보

  • 논문 ID: 2510.22361
  • 제목: The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph
  • 저자: El-Mehdi Mehiri
  • 분류: math.CO (조합론), cs.DM (이산수학)
  • 제출 시간: 2025년 10월 25일 arXiv 제출
  • 논문 링크: https://arxiv.org/abs/2510.22361v1

초록

본 논문은 패리티 제약을 부과한 새로운 4-기둥 하노이 타워 문제 변형을 소개하고 연구한다. 4개의 기둥 중 2개는 중립 기둥(임의의 원판 배치 허용)이고, 나머지 2개는 제약 기둥이다: 하나는 짝수 번호 원판만, 다른 하나는 홀수 번호 원판만 허용한다. 이러한 제약 하에서 저자는 4가지 전형적인 최적화 목표를 연구하고 각 목표에 대한 최적 이동 횟수의 정확한 공식을 도출한다. 연구는 결합 재귀 관계 시스템을 확립하고 이를 고차 재귀 및 명시적 폐형식 표현으로 전개한다. 이 공식들은 주기적 성장 패턴을 나타내며, 모든 해가 지수 성장을 보이지만 고전 3-기둥 문제보다 훨씬 느린 성장률을 드러낸다. 특히, 각 최적 이동 수열은 패리티 제약에 의해 유도된 "반지수" 점근 차수를 갖는다. 또한 논문은 관련 패리티 제약 하노이 그래프를 정의하며, 그 꼭짓점은 모든 가능한 상태를 나타내고 간선은 합법적 이동을 나타낸다. 그리고 차수, 연결성, 평면성, 직경, 해밀턴성, 클리크 수, 색수 등의 성질을 결정한다.

연구 배경 및 동기

연구 문제

본 논문의 핵심 문제는: 패리티 제약이 부과된 4-기둥 하노이 타워 문제에서 서로 다른 목표 배치를 어떻게 최적으로 완성할 것인가?

고전 하노이 타워 문제는 1세기 이상의 연구 역사를 가지고 있다:

  • 3-기둥 문제: 명확한 지수 해 h3n=2n−1h_3^n = 2^n - 1, 구조 단순
  • 4-기둥 문제(Reve의 퍼즐): 최적 해가 2014년 Bousch에 의해 확인될 때까지 미해결, 더 높은 복잡도
  • 5-기둥 이상: Frame-Stewart 알고리즘이 최적으로 여겨지지만 형식적 증명 부재

문제의 중요성

  1. 이론적 의의: 하노이 타워 문제는 조합 최적화와 재귀 알고리즘의 고전적 범례이며, 그 변형 연구는 재귀 구조와 상태 공간에 대한 이해를 심화시킨다
  2. 제약 최적화: 패리티 제약은 중요한 구조적 제한의 한 종류를 나타내며, 실제 응용(자원 할당, 스케줄링 문제)에서 보편적이다
  3. 그래프 이론적 가치: 관련 상태 그래프는 제약 그래프 구조 성질 연구의 새로운 관점을 제공한다
  4. 복잡도 분석: 제약이 문제의 계산 복잡도를 어떻게 변경하는지 연구하는 것은 알고리즘 설계에 지침을 제공한다

기존 방법의 한계

  1. 고전 하노이 타워: 기둥의 특수한 속성이나 제약을 고려하지 않음
  2. 기존 변형: 주로 기둥 수의 변화에 초점을 맞추고, 구조적 제약 연구는 적음
  3. 그래프 이론 연구: 고전 하노이 그래프의 성질은 충분히 연구되었으나, 제약 버전은 아직 체계적으로 탐구되지 않음

연구 동기

저자의 혁신은 다음에 있다:

  1. 패리티 제약 도입 - 자연스럽고 의미 있는 제한
  2. 제약이 최적 전략과 성장률을 어떻게 변경하는지 체계적 연구
  3. 최적화 문제와 그래프 구조를 연결하는 완전한 그래프 이론 프레임워크 구축
  4. 제약 문제가 3-기둥과 4-기둥 고전 문제 사이의 독특한 위치를 차지함을 드러냄

핵심 기여

본 논문의 주요 기여는 다음과 같다:

  1. 새로운 문제 정의: 패리티 제약 4-기둥 하노이 타워 문제를 처음 제안하고 형식화하며, 4가지 전형적 최적화 목표 정의:
    • (a) 전체 타워 이동: N₁에서 N₂로
    • (b) 홀짝 분리: 홀수 원판을 O로, 짝수 원판을 E로
    • (c) 홀수를 O로, 짝수를 N₂로
    • (d) 홀수를 N₂로, 짝수를 E로
  2. 재귀 관계 시스템: 4개의 최적 이동 수열 (an,bn,cn,dn)(a_n, b_n, c_n, d_n)을 설명하는 결합 재귀 시스템 확립(정리 1), 최적 해의 유일성 증명(따름정리 1)
  3. 명시적 공식: 고차 재귀 관계(명제 2)와 폐형식 표현(명제 3) 도출, 주기적 성장 패턴 드러냄
  4. 점근 분석: 모든 4개 수열이 "반지수" 성장 Θ(2n)\Theta(\sqrt{2}^n)을 가짐을 증명(정리 3), 3-기둥 문제의 2n2^n 성장률보다 훨씬 느림
  5. 그래프 이론적 특성화: 패리티 제약 하노이 그래프 PnP^n의 구조 성질 전면 분석:
    • 꼭짓점 수: ∣V(Pn)∣=3n|V(P^n)| = 3^n
    • 간선 수의 재귀 및 폐형식 공식
    • 연결성: κ(Pn)=λ(Pn)=2\kappa(P^n) = \lambda(P^n) = 2
    • 평면성: n≤2n \leq 2일 때만 평면
    • 해밀턴성: 모든 PnP^n은 해밀턴 그래프
    • 색수: χ(Pn)=ω(Pn)=3\chi(P^n) = \omega(P^n) = 3 (완벽 그래프)
    • 색 지수: χ′(Pn)=Δ(Pn)=5\chi'(P^n) = \Delta(P^n) = 5
  6. 계층 관계: H⌈n/2⌉3⊆Pn⊆Hn4H_{\lceil n/2 \rceil}^3 \subseteq P^n \subseteq H_n^4 증명, 패리티 제약 그래프가 고전 하노이 그래프 스펙트럼에서의 위치 확립

방법 상세 설명

작업 정의

문제 설정:

  • 기둥 집합: P={N1,N2,O,E}P = \{N_1, N_2, O, E\}
    • N1,N2N_1, N_2: 중립 기둥, 임의의 원판 배치 가능
    • OO: 홀수 기둥, 홀수 번호 원판만 배치 가능
    • EE: 짝수 기둥, 짝수 번호 원판만 배치 가능
  • 원판: [n]={1,2,…,n}[n] = \{1, 2, \ldots, n\}, 1이 최소
  • 상태: 4-튜플 S=(N1,E,O,N2)S = (N_1, E, O, N_2), 각 기둥의 원판 집합 나타냄, 다음 만족:
    • 각 기둥의 원판은 위에서 아래로 엄격히 증가
    • 각 원판은 그 홀짝성과 호환되는 기둥에 위치
  • 합법적 이동: 원판 dd를 기둥 pp에서 기둥 qq로 이동 합법 조건:
    • dd는 pp의 최상단 원판
    • qq가 비어있거나 최상단 원판이 dd보다 큼
    • pp와 qq 모두 dd의 홀짝성 허용

초기 상태: S0=([n],∅,∅,∅)S_0 = ([n], \emptyset, \emptyset, \emptyset) (모든 원판이 N₁에 위치)

4가지 최적화 목표:

  • ana_n: (∅,∅,∅,[n])(\emptyset, \emptyset, \emptyset, [n])로 이동
  • bnb_n: (∅,[n]0,[n]1,∅)(\emptyset, [n]_0, [n]_1, \emptyset)로 이동 (홀짝 분리)
  • cnc_n: (∅,∅,[n]1,[n]0)(\emptyset, \emptyset, [n]_1, [n]_0)로 이동
  • dnd_n: (∅,[n]0,∅,[n]1)(\emptyset, [n]_0, \emptyset, [n]_1)로 이동

재귀 관계 도출

정리 1 (결합 재귀 시스템):

핵심 재귀 관계: an=2bn−1+1a_n = 2b_{n-1} + 1

c_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ 짝수} \\ d_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ 홀수} \end{cases}$$ $$c_n = \begin{cases} b_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ 짝수} \\ b_{n-2} + 2h_{\lfloor(n-1)/2\rfloor}^3 + h_{\lfloor(n-2)/2\rfloor}^3 + 2, & n \text{ 홀수} \end{cases}$$ $$d_n = \begin{cases} b_{n-2} + 3h_{\lfloor(n-2)/2\rfloor}^3 + 2, & n \text{ 짝수} \\ b_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ 홀수} \end{cases}$$ 여기서 $h_m^3 = 2^m - 1$은 고전 3-기둥 문제의 해이다. **도출 논리** ($a_n$의 예): 1. 원판 $n$을 $N_1$에서 $N_2$로 이동하려면 두 기둥을 먼저 비워야 함 2. 최적 전략은 $n-1$개의 작은 원판을 홀짝성에 따라 $E$와 $O$로 분리 (필요: $b_{n-1}$ 단계) 3. 원판 $n$ 이동 (1단계) 4. 작은 원판을 $E$와 $O$에서 $N_2$로 이동 (대칭, 다시 $b_{n-1}$ 단계) 5. 총합: $a_n = 2b_{n-1} + 1$ ### 고차 재귀 및 폐형식 공식 **명제 2 (고차 재귀)**: 소거를 통해 단일 변수 재귀 획득: $$a_n = \begin{cases} a_{n-3} + 5 \cdot 2^{(n-2)/2} - 2, & n \text{ 짝수} \\ a_{n-3} + 7 \cdot 2^{(n-3)/2} - 2, & n \text{ 홀수} \end{cases}$$ $$b_n = \begin{cases} b_{n-3} + 7 \cdot 2^{(n-4)/2} - 1, & n \text{ 짝수} \\ b_{n-3} + 5 \cdot 2^{(n-3)/2} - 1, & n \text{ 홀수} \end{cases}$$ 유사하게, $c_n$과 $d_n$은 주기가 5와 6인 재귀를 만족한다. **명제 3 (폐형식 표현)**: $\rho(n) = n \bmod 3$, $\theta(n) = (n - \rho(n))/3$으로 정의하면, 명시적 공식 존재 (형식 복잡, $\rho(n)$, $\theta(n)$ 및 기하급수 포함). ### 기술적 혁신점 1. **결합 시스템 분석**: 4개 목표가 상호 의존적이므로 동시에 해결 필요, 독립 재귀보다 복잡 2. **홀짝 분리 전략**: 홀짝 제약을 교묘히 활용하여 서로 다른 홀짝성의 원판을 분리함으로써 이동 공간 창출 3. **주기성 패턴 인식**: 재귀의 주기성 발견 (mod 3, mod 5, mod 6), 이는 홀짝 제약의 직접 결과 4. **반지수 성장**: 성장률이 $\Theta(\sqrt{2}^n)$임을 증명, 다항식과 전체 지수 사이에 위치, 제약 효과의 정량화 표현 ## 실험 설정 본 논문은 순수 이론 연구로 전통적 의미의 실험은 없지만 다음을 포함한다: ### 수치 검증 - **처음 15항 계산**: 표 1은 $h_3^n$, $h_4^n$, $a_n$, $b_n$, $c_n$, $d_n$의 처음 15개 값 나열 - **재귀 관계 검증**: 이론 공식과 직접 계산의 일치 확인 ### 시각화 분석 - **그래프 구조 표시**: 그림 3은 $P^1$, $P^2$, $P^3$의 완전한 구조 표시 - **성장 곡선**: 그림 2는 로그 척도에서 6개 수열의 성장 비교, 반지수 성장 검증 ### 그래프 이론 성질 검증 - **소규모 검증**: $n \leq 3$의 그래프에 대해 평면성, 해밀턴성 등 성질 직접 검증 - **부분그래프 관계**: 그림 5는 $P^3$의 최대 3-기둥 하노이 부분그래프 표시 ## 실험 결과 ### 주요 수치 결과 **표 1 데이터 분석**: - $a_{14} = 481$, 반면 $h_3^{14} = 16383$, $h_4^{14} = 113$ - $h_4^n \leq a_n \leq h_3^n$ 검증 - $b_n$, $c_n$, $d_n$의 값은 유사하지만 고정된 크기 관계 없음 **성장률 검증** (정리 2): - $\lim_{k \to \infty} a_{2k}/a_{2k-1} = 27/19 \approx 1.421$ - $\lim_{k \to \infty} a_{2k+1}/a_{2k} = 38/27 \approx 1.407$ - 2단계 성장: $\lim_{n \to \infty} a_n/a_{n-2} = 2$ ### 그래프 이론 성질 결과 **꼭짓점 및 간선 수**: - $|V(P^{10})| = 3^{10} = 59049$ - $|E(P^{10})| = 113834$ (표 2) - $|E(H_{10}^3)| = 88572 < |E(P^{10})| < |E(H_{10}^4)| = 3142656$ 만족 **차수**: - 최소 차수: $\delta(P^n) = 2$ (완벽 상태) - 최대 차수: $\Delta(P^n) = 5$ ($n \geq 3$) - 평균 차수: $\lim_{n \to \infty} \bar{d}(P^n) = 27/7 \approx 3.857$ **연결성**: - 점 연결도: $\kappa(P^n) = 2$ - 간선 연결도: $\lambda(P^n) = 2$ - 최대 연결 ($\kappa = \lambda = \delta$) **직경 범위**: - $4n - 7 \leq \text{diam}(P^n) \leq 2^{\lceil n/2 \rceil} - 1$ **착색**: - 클리크 수: $\omega(P^n) = 3$ (원판 1 또는 2의 이동으로만 생성) - 색수: $\chi(P^n) = 3$ (완벽 그래프) - 색 지수: $\chi'(P^n) = 5 = \Delta(P^n)$ (1류 그래프) ### 주요 발견 1. **반지수 성장의 정확한 특성화**: 모든 4개 수열이 $\Theta(\sqrt{2}^n)$, 홀짝 제약의 직접 결과 2. **주기적 행동**: 재귀 관계가 mod 3, mod 5, mod 6의 주기성 나타냄, 홀짝성과 기둥 수의 상호작용 반영 3. **그래프의 중간 위치**: $P^n$이 구조상 $H_{\lceil n/2 \rceil}^3$과 $H_n^4$ 사이에 엄격히 위치 4. **완벽 그래프 성질**: $\omega(P^n) = \chi(P^n) = 3$은 $P^n$이 완벽 그래프임을 의미, 하노이 그래프 족에서 흥미로운 성질 5. **해밀턴성**: 제약에도 불구하고 $P^n$은 해밀턴성 유지, 완벽 상태 간 해밀턴 경로 구성 가능 ## 관련 연구 ### 고전 하노이 타워 연구 1. **3-기둥 문제**: - 최적 해 $h_3^n = 2^n - 1$은 1세기 이상 알려짐 - 그래프 $H_n^3$의 성질 충분히 연구됨 (Hinz 등, 2018) 2. **4-기둥 문제**: - Bousch (2014) 최적 해의 재귀 관계 증명 - Frame-Stewart 알고리즘 (1941) 3. **다중 기둥 문제**: - 5-기둥 이상의 최적성은 여전히 미해결 문제 ### 하노이 그래프 연구 1. **구조 성질** (Hinz & Parisse, 2002, 2012): - 평면성: $H_n^4$는 $n \leq 2$일 때만 평면 - 해밀턴성: 모든 $H_n^m$ ($m \geq 3$)은 해밀턴 그래프 2. **착색 성질** (Arett & Dorée, 2010; Hinz & Parisse, 2012): - $\chi(H_n^3) = 3$, $\chi(H_n^4) = 4$ - 클리크 수 $\omega(H_n^m) = m$ 3. **거리 성질** (Klavžar 등, 2001): - 간선 수, 직경 등의 정확한 공식 ### 제약 변형 1. **Sierpiński 그래프** (Hinz 등, 2013): - 하노이 그래프의 생성 부분그래프 2. **제약 하노이 그래프** (Mehiri, 2024): - 다른 유형의 이동 제한 ### 본 논문의 위치 본 논문은 **구조적 제약** (홀짝성)이 하노이 타워 문제에 미치는 영향을 처음 체계적으로 연구하며, 다음 공백을 채운다: 1. 제약이 최적 전략과 복잡도를 어떻게 변경하는가 2. 제약 그래프의 완전한 구조 특성화 3. 반지수 성장의 정확한 분석 ## 결론 및 논의 ### 주요 결론 1. **최적화 결론**: - 4개 목표의 최적 해는 결합 재귀 시스템으로 정확히 계산 가능 - 최적 전략은 유일함 - 모든 해의 성장률은 $\Theta(\sqrt{2}^n)$, 3-기둥의 $\Theta(2^n)$보다 현저히 느림 2. **그래프 이론 결론**: - $P^n$은 $3^n$개 꼭짓점, 간선 수 $\Theta(3^n)$ - 최대 연결이지만 고도로 연결되지 않음 ($\kappa = 2$) - 소규모일 때만 평면 ($n \leq 2$) - 항상 해밀턴 그래프이자 완벽 그래프 - $H_{\lceil n/2 \rceil}^3$과 $H_n^4$ 사이에 엄격히 위치 3. **이론적 의의**: - 홀짝 제약이 새로운 복잡도 계층 창출 - 제약이 가능한 이동을 감소시키지만 전략 복잡성 증가 - 반지수 성장은 제약 최적화의 흥미로운 사례 ### 한계 1. **제약 유형 단일**: 이진 홀짝 제약만 고려, 다른 모듈로 연산 제약 미탐색 2. **기둥 수 고정**: 4-기둥만 연구, 임의 기둥 수로 미추광 3. **직경 정확값**: 범위만 제시, 정확값 미결정 4. **계산 복잡도**: 최적 해 계산 알고리즘 복잡도 미분석 5. **실제 응용**: 실제 응용 사례 미논의 ### 향후 방향 저자가 제시한 연구 방향: 1. **그래프 이론 확장**: - 스펙트럼 매개변수 (고유값, 고유벡터) - 거리 지표 (Wiener 지수, Hosoya 지수) - 지배 수, 거리 차원 2. **제약 추광**: - 모듈로 $k$ 제약 ($k > 2$) - 다중 그룹 제약 - 혼합 제약 유형 3. **일반화 프레임워크**: - $p$개 기둥, $k$개 제약 클러스터 - 제약 배치가 위상 구조에 미치는 영향 4. **알고리즘 연구**: - 효율적 계산 알고리즘 - 근사 알고리즘 - 온라인 알고리즘 5. **응용 탐색**: - 자원 스케줄링 - 제약 만족 문제 - 병렬 컴퓨팅 ## 심층 평가 ### 장점 1. **문제 혁신성 강함**: - 홀짝 제약 하노이 타워 문제를 처음 체계적으로 연구 - 제약 설계가 자연스럽고 의미 있음 - 4개 목표가 주요 최적화 시나리오 포괄 2. **이론 분석 완전함**: - 재귀 관계에서 폐형식 공식까지 추론 엄밀 - 점근 분석 심화, 반지수 성장의 본질 드러냄 - 증명 기법 다양 (귀납법, 대수 소거, 점근 분석) 3. **그래프 이론 특성화 포괄적**: - 10여 개 그래프 이론 성질 체계적 연구 - 증명 기법 풍부 (부분그래프 임베딩, 착색 논증, 해밀턴 경로 구성) - 고전 하노이 그래프와의 관계 명확 4. **작성 명확하고 규범적**: - 구조 합리적, 논리 명확 - 정의 정확, 기호 체계 완선 - 도표가 설명 보조, 가독성 향상 5. **결과 심화**: - 반지수 성장은 제약 최적화의 새 예시 - 완벽 그래프 성질 예상 외 - 계층 관계 $H_{\lceil n/2 \rceil}^3 \subseteq P^n \subseteq H_n^4$ 우아함 ### 부족점 1. **직경 미정확 결정**: - 상하한만 제시 $4n - 7 \leq \text{diam}(P^n) \leq 2^{\lceil n/2 \rceil} - 1$ - 범위 간격 크고, 특히 큰 $n$에 대해 2. **알고리즘 분석 부재**: - 최적 해 계산 알고리즘 복잡도 미논의 - 실제 구현이나 의사코드 미제공 - 폐형식 공식 존재하지만 계산 복잡 3. **추광 제한적**: - 4-기둥과 이진 홀짝 제약만 연구 - 다른 제약 유형이나 기둥 수의 체계적 이론 미탐색 4. **실제 응용 부재**: - 순수 이론 연구, 실제 응용 미논의 - 실제 문제(스케줄링, 자원 할당)와의 연결 미설정 5. **일부 증명 간략**: - 일부 정리(예: 정리 10) 증명이 개요적 - 폐형식 공식 도출 과정 완전히 전개되지 않음 6. **수치 실험 제한적**: - $n = 14$까지만 계산 - 대규모 수치 검증 부재 - 다른 방법과의 실제 실행 시간 비교 부재 ### 영향력 **분야에 대한 기여**: 1. 제약 하노이 타워 문제의 새 연구 방향 개척 2. 제약 최적화의 새 이론적 사례 제공 3. 하노이 그래프 족의 이론 체계 풍부화 **실용적 가치**: 1. 이론적 가치가 실용적 가치보다 높음 2. 제약 스케줄링, 자원 할당 문제 연구 영감 가능 3. 반지수 성장 분석 방법이 다른 제약 문제에 적용 가능 **재현성**: 1. 이론 추론 검증 가능 2. 재귀 관계 프로그래밍 용이 3. 그래프 구성 알고리즘 명확 4. 코드 구현 부재하나 원리 명확 ### 적용 시나리오 1. **이론 연구**: - 조합 최적화 이론 - 재귀 알고리즘 분석 - 제약 만족 문제 2. **교육 응용**: - 재귀 관계의 교육 사례 - 그래프 이론 성질의 종합 예시 - 제약 최적화의 입문 자료 3. **잠재적 응용**: - 자원 제약이 있는 작업 스케줄링 - 유형 제한이 있는 저장소 관리 - 병렬 컴퓨팅의 부하 균형 4. **확장 연구**: - 다른 제약 유형의 하노이 타워 - 다중 기둥 제약 문제 - 제약 그래프의 스펙트럼 이론 ## 참고 문헌 논문은 23편의 중요 문헌을 인용하며, 주요 문헌은: 1. **Bousch (2014)**: 4-기둥 하노이 타워 최적 해 증명 2. **Hinz, Klavžar & Petr (2018)**: 《The Tower of Hanoi - Myths and Maths》, 하노이 타워 문제의 권위 있는 전문서 3. **Frame (1941) & Stewart (1941)**: Frame-Stewart 알고리즘 원본 논문 4. **Hinz & Parisse (2002, 2012)**: 하노이 그래프의 평면성과 착색 성질 5. **Arett & Dorée (2010)**: 하노이 그래프의 착색과 계수 6. **Klavžar 등 (2001, 2013)**: 하노이 그래프의 조합 성질과 Sierpiński 그래프 7. **Mehiri (2024)**: 저자의 제약 하노이 그래프에 관한 선행 연구 --- **종합 평가**: 이는 새로운 하노이 타워 변형을 체계적으로 연구한 고품질 이론 논문이다. 이론 분석이 심화되고 완전하며, 그래프 이론 특성화가 포괄적이고, 결과가 일정한 깊이와 아름다움을 갖는다. 주요 부족점은 추광성과 실용성이 제한적이고 일부 기술 세부사항을 더 충분히 할 수 있다는 점이다. 논문은 조합 최적화와 그래프 이론 분야에 명확한 기여를 하며, 제약 최적화 문제에 새로운 이론적 관점을 제공한다.