A Census of New Snake-in-the-Box Records

기술 요약: 새로운 스네이크 인 더 박스(Snake-in-the-Box) 기록 조사

문제 정의
본 논문은 1958년 코츠(Kautz)가 오류 검출 코드의 맥락에서 처음 제안한 "스네이크 인 더 박스(snake-in-the-box)" 문제를 다룬다. 이 문제는 하이퍼큐브 그래프 $Q_n$ 내에서 가장 긴 유도된(induced, 또는 chordless) 경로인 "스네이크(snake)"를 찾는 것을 목표로 한다. $Q_n$에서 정점은 길이 $n$인 이진 문자열을 나타내며, 간선은 정확히 하나의 좌표가 다른 문자열들을 연결한다. 스네이크는 서로 다른 정점들의 수열로 정의되는데, 연속된 정점들은 서로 인접하며, 인접하지 않은 두 정점 사이에는 간선이 존재하지 않아야 한다. 이러한 경로의 최대 길이를 $a(n)$이라 명명한다.

본 논문은 또한 관련 구조인 "코일(coils)"( $Q_n$ 내의 유도된 사이클)의 최대 길이 $b(n)$과 "대칭 코일(symmetric coils)"(고정된 XOR 연산을 통해 사이클의 전반부가 후반부를 거울처럼 반영하는 코일)의 최대 길이 $c(n)$에 대해서도 고찰한다. $n \le 8$인 차원에서는 $a(n)$과 $b(n)$의 정확한 값이 알려져 있고, $c(n)$은 $n \le 7$까지 알려져 있으나, $n \ge 9$(대칭 코일의 경우 $n \ge 8$)인 경우에는 다양한 계산 탐색을 통해 도출된 하한값(lower bounds)만이 존재할 뿐 문제는 여전히 미해결 상태로 남아 있다.

방법론 및 접근 방식
저자들은 9차원에서 13차원 사이의 더 긴 스네이크, 코일, 대칭 코일을 찾기 위해 지속적인 계산적 노력을 기울였다. 본문에 구체적인 새로운 알고리즘 아키텍처가 상세히 기술되어 있지는 않으나, 유전 알고리즘, 인구 기반 진화 탐색, 순열 기반 구성, 몬테카를로 트리 탐색 등을 포함했던 기존 방식들보다 진보된 성과임을 밝히고 있다.

저자들의 접근 방식은 기록적인 길이의 경로를 생성하고 검증하는 데 집중한다. 저자들은 경로를 따라 뒤집히는 0부터 시작하는 인덱스의 좌표 번호들을 순서대로 나열한 전이 수열(transition sequence)이라는 표준 표기법을 사용한다. 연구 결과의 타당성을 보장하기 위해, 저자들은 컴퓨터로 검증 가능한 데이터셋을 제공한다. 또한, 기록 길이에 해당하는 스네이크들의 솔루션 공간에 대한 센서스(census, 조사)를 수행하여, 서로 동등하지 않은(inequivalent) 스네이크의 개수를 산출한다. 여기서 동등성은 $n!$개의 좌표 순열, $2^n$개의 평행 이동(XORing), 그리고 경로 역전(path reversal)을 포함하는 $Q_n$의 대칭성에 의해 결정된다.

주요 기여 및 결과
본 논문의 주요 기여는 9차원에서 13차원 사이의 $a(n)$, $b(n)$, $c(n)$에 대한 새로운 하한값을 확립하여 기존의 기록을 경신한 것이다.

• 스네이크 길이 ($a(n)$): 저자들은 9차원에서 13차원 모든 차원에서 이전의 최적 기록보다 더 긴 스네이크를 제시한다.

  • $n=9$: 새로운 길이 191 (기존 190에서 개선). 저자들은 이 길이의 서로 동등한 스네이크가 1,311개임을 확인했다.
  • $n=10$: 새로운 길이 379 (기존 376에서 개선).
  • $n=11$: 새로운 길이 746 (기존 737에서 개선).
  • $n=12$: 새로운 길이 1,476 (기존 1,465에서 개선).
  • $n=13$: 새로운 길이 2,922 (기존 2,900에서 개선).
  • 개선 폭은 이전 기록 대비 +1에서 +22에 달한다.

• 코일 길이 ($b(n)$): 본 논문은 9, 10, 11차원에서 가장 긴 코일에 대한 개선된 하한값을 보고하며, 각각 192, 374, 732라는 새로운 길이를 제시한다.

• 대칭 코일 길이 ($c(n)$): 10차원과 11차원에 대해 개선된 하한값이 제공되었으며, 새로운 길이는 각각 370과 726이다.

저자들은 $Q_9$에서의 길이 191 스네이크에 대한 구체적인 예시로 전체 전이 수열을 나열하였다. 저자들은 수백만 개의 샘플링된 길이 191 스네이크 중에서 $n=9$에 대해 정확히 131개의 대칭 클래스가 발견되었음을 언급하며, 다른 클래스가 존재하지 않을 것이라는 추측을 제시하였으나, $n \ge 10$에 대해서는 그러한 완전성 주장을 하지 않았다.

의의 및 주장
본 논문은 주로 스네이크 인 더 박스 문제의 알려진 경계값을 경험적으로 진전시켰다는 점에서 의의를 갖는다. 9차원에서 13차원까지의 모든 차원에서 이전보다 엄격히 더 긴 스네이크를 제공함으로써, 저자들은 하이퍼큐브 내 유도된 경로의 최대 가능 길이에 대한 하한값을 더욱 좁혔다.

본 연구는 이러한 새로운 기록들에 대한 종합적인 데이터셋을 포함하는 "센서스(census)" 역할을 하며, 모든 고유한 기록 길이 스네이크의 전이 수열을 제공한다. 이 데이터셋은 독립적인 검증이 가능하도록 컴퓨터 검증 가능한 형식으로 공개된다. 저자들은 자신의 연구를 이전 연구자들(Ace, Echols, Meyerson 등)이 구축한 계산적 계보의 연장선상으로 규정하며, 해당 차원들에 대한 문제를 해결했거나 새로운 하한값의 최적성을 증명하려 하기보다는, 이 조합 최적화 문제에서 계산적으로 달성 가능한 한계를 밀어붙이는 데 초점을 맞추고 있다.